sum-digits.py

#!/usr/bin/env python

# Find all nine-digit numbers whose digits are a permutation of the digits 1 to
# 9 and such that, taken independently:
#
# - the first digit is divisible by 1
# - the first two digits are divisible by 2
# - the first three digits are divisible by 3
# - and so on.
#
# Example: 381654729.
#
# - 3 is divisible by 1
# - 38 is divisible by 2
# - 381 is divisible by 3
# - and so on.

import time
start_time = time.time()

# Calculate all permutations of "positions" things".
def permutations(positions):
   perms = [ range(positions) ]
   for i in range(positions):
      new_perms = []
      for perm in perms:
         for j in range(i,positions):
            new_perm = perm[:]
            new_perm[i], new_perm[j] = perm[j], perm[i]
            new_perms.append(new_perm)
      perms = new_perms
   return perms

# Verify that the sequence "digits" satisfies the required property.
def verify(digits):
   total = 0
   for i in range(len(digits)):
      total = total * 10 + digits[i]
      if total % (i + 1) != 0:
         return False
   return True

# This version is fast.
def fast():
   perms = permutations(4)
   evens = { 0: 2, 1: 4, 2: 6, 3: 8 }
   odds = { 0: 1, 1: 3, 2: 7, 3: 9 }

   for even in perms:
      for odd in perms:
         digits = [
               odds[odd[0]],
               evens[even[0]],
               odds[odd[1]],
               evens[even[1]],
               5,
               evens[even[2]],
               odds[odd[2]],
               evens[even[3]],
               odds[odd[3]]
               ]

         if verify(digits):
            print "".join(map(str,digits))

# This version is slow, but it verifies that the answer from the first version
# does seem to be correct.
def slow():
   perms = permutations(9)
   for perm in perms:
      digits = [n+1 for n in perm]
      if verify(digits):
         print "".join(map(str,digits))
   return

# Run (and time) both versions.
if __name__ == "__main__":
   fast()
   print("--- %s seconds ---" % (time.time() - start_time))
   start_time = time.time()
   slow()
   print("--- %s seconds ---" % (time.time() - start_time))

   # Output:
   #   381654729
   #   --- 0.00159001350403 seconds ---
   #   381654729
   #   --- 1.1880800724 seconds ---