princeofsudan

ProjectEuler#43 Sub-string divisibility

Apr 5th, 2013
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.60 KB | None | 0 0
  1. #The number, 1406357289, is a 0 to 9 pandigital number because it is made up
  2. #of each of the digits 0 to 9 in some order, but it also has a rather
  3. #interesting sub-string divisibility property.
  4.  
  5. #Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way,
  6. #we note the following:
  7.  
  8. #    d2d3d4=406 is divisible by 2
  9. #    d3d4d5=063 is divisible by 3
  10. #    d4d5d6=635 is divisible by 5
  11. #    d5d6d7=357 is divisible by 7
  12. #    d6d7d8=572 is divisible by 11
  13. #    d7d8d9=728 is divisible by 13
  14. #    d8d9d10=289 is divisible by 17
  15.  
  16. #Find the sum of all 0 to 9 pandigital numbers with this property.
  17.  
  18.  
  19. import itertools
  20.  
  21.  
  22. def generatePerm(nDigits):
  23.     #tupleList is sorted asc
  24.     tupleList = list(itertools.permutations(range(nDigits),nDigits))
  25.     intList = []
  26.     for i in tupleList: #Convert tuples list generated to ints list
  27.         digitStr = ''
  28.         for j in i:
  29.             digitStr += str(j)
  30.         if int(digitStr[0])!= 0: #add to ints list only numbers not starting  
  31.             intList.append(int(digitStr)) #with 0
  32.     return intList
  33.  
  34. intList = generatePerm(10)
  35. divisableList = []
  36. count = 0
  37. for i in intList:
  38.     if int(str(i)[1]+str(i)[2]+str(i)[3])%2 == 0 and\
  39.        int(str(i)[2]+str(i)[3]+str(i)[4])%3 == 0 and\
  40.        int(str(i)[3]+str(i)[4]+str(i)[5])%5 == 0 and\
  41.        int(str(i)[4]+str(i)[5]+str(i)[6])%7 == 0 and\
  42.        int(str(i)[5]+str(i)[6]+str(i)[7])%11 == 0 and\
  43.        int(str(i)[6]+str(i)[7]+str(i)[8])%13 == 0 and\
  44.        int(str(i)[7]+str(i)[8]+str(i)[9])%17 == 0:
  45.         divisableList.append(i)
  46.         count += i
  47.  
  48. print divisableList
  49. print count
Advertisement
Add Comment
Please, Sign In to add comment