Ten-Digit Pandigital Numbers Divisible By 1 Through 9

April 15, 2016

This is easy. We begin by noting that the least common multiple of the digits 1 through 9 is 2520, and that the smallest ten-digit multiple of 2520 is 1000001520. Then we find all the ten-digit pandigital multiples of 2520 with a list comprehension:

(define xs
  (list-of n
    (n range 1000001520 10000000000 2520)
    (= (undigits (sort < (digits n))) 123456789)))

There are about 3.5 million ten-digit multiples of 2520, so it only takes a few seconds to generate them all and test them for pandigital-ness (is that a word?). Now we can answer questions about them:

> (length xs)
11460
> (car xs)
1234759680
> (cadr xs)
1234857960
> (cadr (reverse xs))
9876134520
> (car (reverse xs))
9876351240

Having a good Standard Prelude available makes this exercise trivial; our solution was easy to write, is easy to read, and works relatively quickly. We could make it much faster by calculating only the two smallest and two largest members of the set as the question requires, but it’s more fun to see the entire solution set, and doesn’t take too long. You can run the program at http://programmingpraxis.codepad.org/iNjfmAsg.

Advertisements

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: