Enigmatic Code

Programming Enigma Puzzles

Enigma 1692: Key factors

From New Scientist #2859, 7th April 2012 [link]

Clever logic should enable you to find the nine-figure number that I have in mind. It consists of the digits 1 to 9 in some order, and in the number each digit is next to another that differs from it by one.

In just one case a digit has both neighbours differing from it by one. Furthermore, the solution is exactly divisible by more than three-quarters of the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 and 12.

What is the nine-figure number?

[enigma1692]

Advertisements

2 responses to “Enigma 1692: Key factors

  1. Jim Randell 3 April 2012 at 10:20 pm

    Here’s my initial solution in Python. It runs in 316ms.

    from itertools import permutations
    from enigma import concat
    
    for d in permutations(range(1, 10)):
      # the first two digits must differ by 1
      if abs(d[0] - d[1]) != 1: continue
      # likewise the last two digits
      if abs(d[7] - d[8]) != 1: continue
    
      # for the rest, count how many neighbours differ by 1
      c = list((1 if abs(d[i-1] - d[i]) == 1 else 0) +
               (1 if abs(d[i] - d[i+1]) == 1 else 0) for i in range(1, 8))
      # only one should have 2 neighbours that differ by 1
      if c.count(2) != 1: continue
      # and the rest should only have 1 neighbour that differs by 1
      if c.count(1) != 6: continue
    
      # what is the number?
      n = int(concat(*d))
    
      # find the divisors
      ds = list(i for i in range(1, 13) if n % i == 0)
      # there should be more than 9 of them
      if len(ds) < 10: continue
    
      print(n, ds)
    

    Solution: The number is 436578912.

    • Jim Randell 4 April 2012 at 8:17 am

      Here’s a faster program that uses recursion. It runs in 54ms.

      from enigma import concat
      
      # the 9-digit number must be even, so let's accumulate the digits in reverse
      
      digits = set(range(1, 10))
      
      # flag is set when we've got a digit that differs by 1 from both neighbours
      def solve(ds, flag=False):
        # are we done?
        if len(ds) == 9:
          # check the final digit differs by 1 from the previous one
          if abs(ds[7] - ds[8]) != 1: return
          # and that we have exactly one digit that differs by 1 from both neighbours
          if flag ^ (abs(ds[6] - ds[7]) != 1): return
          # so, what is the number (remember the digits are in reverse order)
          n = int(concat(*reversed(ds)))
          # find the divisors
          l = list(i for i in range(1, 13) if n % i == 0)
          if len(l) > 9: print(n, l)
        # last digit must be even
        elif len(ds) == 0:
          for d in digits:
            if d % 2: continue
            solve([d])
        # penultimate digit must differ from the last by one
        elif len(ds) == 1:
          for d in digits.intersection((ds[0] - 1, ds[0] + 1)):
            solve(ds + [d])
        # try adding another digit
        else:
          for d in digits.difference(ds):
            # count the neighbours of the previous digit
            n = (1 if abs(ds[-2] - ds[-1]) == 1 else 0) + (1 if abs(ds[-1] - d) == 1 else 0)
            # must be 1 or 2 (if 2 hasn't already been used)
            if not(n == 1 or (n == 2 and not flag)): continue
            solve(ds + [d], flag or (n == 2))
      
      solve([])
      

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: