Ten-Digit Pandigital Numbers Divisible By 1 Through 9

April 15, 2016

Today’s exercise solves somebody’s homework problem — but not too much, since he had to write his program in Java:

Find the two smallest ten-digit pandigital numbers (numbers that contain all the digits from 0 through 9) that are divisible by the numbers 1 through 9. Then find the two largest pandigital numbers that are divisible by the numbers 1 through 9.

Your task is to solve the homework problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

15 Responses to “Ten-Digit Pandigital Numbers Divisible By 1 Through 9”

  1. Simple in perl as well…

    print join "\n", @{[ grep { '0123456789' eq join q(), sort split m{}, $_ } map { $_ * 2_520 } 390_000 .. 4_000_000 ]}[0,1,-2,-1],q();
    
  2. Dr. Z said

    function is_divisible_by_all_digits(x::Int64)
    for z = 2:9
    if x % z != 0
    return false
    end
    end

    return true
    end

    function find_all_pandigitals()
    X = collect(permutations([1,2,3,4,5,6,7,8,9,0]))[1:end-362880]
    N = length(X)
    y = Array(Int64, N)

    for i = 1:N
    x = X[i]
    y[i] = x[end]

    for j = 1:9
    y[i] += x[end-j] * 10^j
    end
    end

    return y
    end

    function main()
    Z = Array(Int64, 2, 2)
    p = find_all_pandigitals()
    # N = length(p)
    y = []

    for x in p
    if is_divisible_by_all_digits(x)
    push!(y, x)
    end
    end

    M, ind = findmin(y)
    Z[1,1] = M
    y[ind] = 9999999999999999999
    M = minimum(y)
    Z[1,2] = M
    y[ind] = 0
    M, ind = findmax(y)
    y[ind] = 0
    Z[2,1] = M
    M = maximum(y)
    Z[2,2] = M
    return Z
    end

    Memory used: 1.158 GB
    Execution time: a bit less than 3.5 sec

  3. matthew said

    This should get them high marks if the relevant library functions exist in Java. Needs C++14 (for auto lambda parameters).

    #include <iostream>
    #include <algorithm>
    int main() {
      int a[] = {1,2,3,4,5,6,7,8,9};
      int b[] = {2,3,1,5,4,6,2,3,1};
      while(std::next_permutation(a,a+9)) {
        if ((10*a[7]+a[8])%4) continue;
        if (std::inner_product(a,a+9,b,0)%7) continue;
        std::for_each(a,a+9,[](auto d){ std::cout << d; });
        std::cout << "0" << "\n";
      }
    }
    

    Like the suggested solution, generates all 11460 solutions (in 0.018 seconds apparently). Note that there is no conversion to or from strings.

  4. matthew said

    Perhaps I should explain that a bit: as noted, we want multiples of 9*8*7*5 = 2520 = 252 * 10, so just generate permutations of 1-9 and put a 0 on the end to get the 10 factor. All pandigital numbers are divisible by 9 (sum of digits is 45) so don’t need to check for that. Just leaves 4 and 7: 4 is easy and the inner product is a wacky test for divisibility by 7 I got from https://www.math.hmc.edu/funfacts/ffiles/10005.5.shtml

  5. Dr. Z said

    That changes things. If that’s the case, my script can accomplish the task in a bit more than 1.3sec (same memory usage though)

  6. matthew said

    Have fun…

    You might want to have a look at: https://en.support.wordpress.com/code/posting-source-code/ – if your language (Julia?) isn’t there then ‘language=”text”‘ will preserve indentation as well.

  7. Dr. Z said

    Thank you Matthew. Fortunately, this language, unlike Python, doesn’t lose its shit if identation fails :-)

  8. Paul said

    Generate all permutations of 1-9 and check if the numbers are divisible bu 252.

    for p in permutations("123456789"):
        i = int("".join(p))
        if not i % 252:
            res.append(i * 10)
    print(res[:2])
    print(res[-2:])
    
  9. matthew said

    Can’t resist some micro-optimization: a hand-rolled integer conversion function (with an explicit length, so we can use it with strings without a NUL terminator) is nice & quick (notice that all those auto’s mean that the only thing specifying the return type of toint is the UL suffix on the 0 initial value – we can do all this with ints, but only just). Runtime now about 8ms.

    #include <stdio.h>
    #include <algorithm>
    int main() {
      char a[] = "1234567890\n";
      auto toint = [](auto p,auto k) {
        auto g = [](auto n, auto d){ return 10*n+d-'0'; };
        return std::accumulate(p,p+k,0UL,g);
      };
      while(std::next_permutation(a,a+9)) {
        if (toint(a+7,2)%4 == 0 && toint(a,9)%7 == 0) {
          fwrite(a,1,sizeof(a)-1,stdout);
        }
      }
    }
    
  10. Ernie said

    for Matthew: Can’t you eliminate line 8 by substituting 28 for 4 on line 7 (in your first version)?

  11. matthew said

    @Ernie: Thanks for asking (and glad someone is paying attention) – I could indeed do that, but it would make the program slower – the first check is much faster than the second and eliminates approx 75% of the cases (same for the first clause on line 10 of the second version).

  12. Paul said

    @matthew. This Python code runs well below 1 ms. It only calculates the requested 4 numbers. Of course, in C you should be able to do this a lot faster.

    asc =  "123456789"
    desc = "987654321"
    
    perms_asc = (int("".join(p)) for p in permutations(asc))
    perms_desc = (int("".join(p)) for p in permutations(desc))
    ans_asc = (i*10 for i in perms_asc if i % 252 == 0)
    ans_desc = (i*10 for i in perms_desc if i % 252 == 0)
    res_asc = list(islice(ans_asc, 2))
    res_desc = list(islice(ans_desc, 2))
    
    print(res_asc)
    print(res_desc)
    
  13. matthew said

    @Paul: Well, I would hope just generating 4 solutions rather than all 11460 would be faster. Good point though: C++ doesn’t have a nice compact way of doing on-demand data streams like Python-style generators or Haskell-style lazy lists, though you can do some fun things with iterators & no doubt there is something in Boost.

  14. Globules said

    A Haskell version.

    import Data.Bits
    import Data.Word
    
    -- Candidate numbers in increasing and decreasing order.
    -- 
    -- Base is the smallest number divisible by 1 through 9.  All candidates will
    -- be multiples of this value.
    --
    -- Low and high will constrain our search, being the smallest and largest 10
    -- digit numbers that are multiples of base.
    candidates :: ([Int], [Int])
    candidates = let base = 2*2*2 * 3*3 * 5 * 7
                     low  = quot 1023456789 base * base
                     high = quot 9876543210 base * base
                 in ([low, low + base .. high], [high, high - base .. low])
    
    isPandigital :: Int -> Bool
    isPandigital = go (0x03ff :: Word16)
      where go set 0 = set == 0
            go set n = let (q, r) = n `quotRem` 10
                       in go (set `clearBit` r) q
    
    main :: IO ()
    main = do
      let (incr, decr) = candidates
      putStrLn $ "Smallest: " ++ show (take 2 (filter isPandigital incr))
      putStrLn $ " Largest: " ++ show (take 2 (filter isPandigital decr))
    
    $ ./pandig 
    Smallest: [1234759680,1234857960]
     Largest: [9876351240,9876134520]
    
  15. matthew said

    I just reallized that my reply to @Ernie up above isn’t quite right – the check for divisibility by 4 is essential in the first solution as the inner-product test is specifically just for divisibility by 7; it’s non-essential in the second solution though.

    Anyway, here’s another Haskell solution: directly generate a list of pandigital numbers and take the intersection with multiples of 252 (with a multiplication by 10 at the end as before):

    import Data.List
    import Data.List.Ordered
    
    pandigital n [] = [n]
    pandigital n s = concatMap (\a->pandigital (10*n+a) (delete a s)) s
    
    main = print $ take 2 (map (*10) (isect (pandigital 0 [1..9]) [0,252..]))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: