Enigmatic Code

Programming Enigma Puzzles

Enigma 1643: Divisibility test

From New Scientist #2809, 23rd April 2011 [link]

abcdefghij is a 10-digit number containing one each of the digits 0 to 9 in some order (a ≠ 0). With the exception of the letter which represents zero, a divides abcdefghij, b divides bcdefghij, c divides cdefghij and so on to the end.

What are the largest and smallest 10-digit numbers with this property?

[enigma1643]

Advertisements

One response to “Enigma 1643: Divisibility test

  1. jimrandell 7 December 2011 at 7:33 pm

    Generating all possible permutations and finding the maximum and minimum numbers that satisfy the conditions takes the following Python program around 5.4s:

    from itertools import permutations
    from enigma import irange, printf
    
    def check(s):
      if s[0] == 0: return 0
      n = 0
      p = 1
      for d in reversed(s):
        n += d * p
        if d > 0 and n % d > 0: return 0
        p *= 10
      return n
    
    ns = []
    for s in permutations(irange(0, 9), 10):
      n = check(s)
      if n > 0: ns.append(n)
    
    printf("{n} solutions, max = {max}, min = {min}", n=len(ns), min=min(ns), max=max(ns))
    

    We can unroll the loop and do early rejection of numbers that fail the condition in the early digits. That’s a longer program, but runs in 163ms.

    However, if we set up the initial list correctly we can use the order that permutations are generated by Python to find only the first solution. Which gives us the maximum and minimum numbers in 31ms.

    from itertools import permutations
    from enigma import irange, printf
    
    def check(s):
      if s[0] == 0: return 0
      n = 0
      p = 1
      for d in reversed(s):
        n += d * p
        if d > 0 and n % d > 0: return 0
        p *= 10
      return n
    
    for s in permutations([1, 0, 2, 3, 4, 5, 6, 7, 8, 9]):
      n = check(s)
      if n > 0:
        printf("min = {n}")
        break
    
    for s in permutations([9, 8, 7, 6, 5, 4, 3, 2, 1, 0]):
      n = check(s)
      if n > 0:
        print("max = {n}")
        break
    

    Solution: The largest such number is 9876351240. The smallest is 1234897560.

Leave a Comment

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: