New Scientist Puzzle 102 – Passport to Success

by BRG on March 1, 2021

by Zoe Mensch

From New Scientist #3323, 27th February 2021

My nine-digit passport number has some remarkable properties. Not only does it use all the digits from 1 to 9, but if I label the number ABCDEFGHI, then:

A is divisible by 1
AB is divisible by 2
ABC is divisible by 3
ABCD is divisible by 4
ABCDE is divisible by 5
ABCDEF is divisible by 6
ABCDEFG is divisible by 7
ABCDEFGH is divisible by 8
ABCDEFGHI is divisible by 9

You could program a computer to find this passport number, but there are shortcuts to figuring it out with a pen and paper. For example, a number is only divisible by 3 if its digits add up to a multiple of 3 (e.g.: 372 is divisible by 3 because 3+7+2 = 12). And a number is only divisible by 4 if its last two digits form a number that is also a multiple of 4 (hence 9324 is divisible by 4 because 24 also is).

What is my passport number?

From → Uncategorized

2 Comments Leave one →

Brian Gladman permalink


from itertools import permutations

E = 5
# permute the even digits
for B, D, F, H in permutations((2, 4, 6, 8)):
  
  if (D + E + F) % 3:
    continue
  
  # permute the odd digits (except five) for A and C
  for A, C, in permutations((1, 3, 7, 9), 2):
    
    # check for division by three and four
    if (A + B + C) % 3 or (10 * C + D) % 4:
      continue
    
    # permute the remaining odd digits
    for G, I in permutations({1, 3, 7, 9}.difference((A, C))):
      
      # check for division by seven, eight and nine
      n7 = 10 * (10 * (10 * (10 * (10 * (10 * A + B) + C) + D) + E) + F) + G
      n8 = 10 * n7 + H
      n9 = 10 * n8 + I
      if n7 % 7 or n8 % 8 or n9 % 9:  
        continue

      print(n9)

from itertools import permutations

E = 5

# permute the even digits

for B, D, F, H in permutations((2, 4, 6, 8)):

if (D + E + F) % 3:

continue

# permute the odd digits (except five) for A and C

for A, C, in permutations((1, 3, 7, 9), 2):

# check for division by three and four

if (A + B + C) % 3 or (10 * C + D) % 4:

continue

# permute the remaining odd digits

for G, I in permutations({1, 3, 7, 9}.difference((A, C))):

# check for division by seven, eight and nine

n7 = 10 * (10 * (10 * (10 * (10 * (10 * A + B) + C) + D) + E) + F) + G

n8 = 10 * n7 + H

n9 = 10 * n8 + I

if n7 % 7 or n8 % 8 or n9 % 9:

continue

print(n9)

Now with a speed improvement spotted by Frits.

Frits permalink


from itertools import permutations
 
E = 5
# C is odd so D can only be 2 or 6 as CD % 4 must be 0
# consider FGH being 4y8 or 8y4: FGH % 8 can't be 0 for odd y's
# disallow B=2 and B=6 as they lead to resp. 4y8 and 8y4
for B in [4, 8]:
  # D and F are even, E is 5 and (D + E + F) % 3 == 0
  # so D + F can only be 10 and thus B + H must also be 10
  (H, D, F) = (10 - B, B - 2, 12 - B)
  FxH = 100 * F + H
  # odd numbers
  for A, C, G, I in permutations((1, 3, 7, 9)):
    # if B = 4 and A = 3 or 9 then (A + B + C) can't be a multiple of 3 
    # if B = 4 then values (1, 7) for A lead to resp. values (7, 1) for C
    if B == 4 and A + C != 8: continue
    if (A + B + C) % 3: continue 
    FGH = FxH + 10 * G
    if FGH % 8: continue
    n7 = 100 * (10 * (10 * (10 * (10 * A + B) + C) + D) + E)  + FGH // 10
    if n7 % 7:  continue
    # sum(1..9) = 45 is divisible by 9 so don't check modulo 9
    print(10 * (10 * n7 + H) + I)

from itertools import permutations

E = 5

# C is odd so D can only be 2 or 6 as CD % 4 must be 0

# consider FGH being 4y8 or 8y4: FGH % 8 can't be 0 for odd y's

# disallow B=2 and B=6 as they lead to resp. 4y8 and 8y4

for B in [4, 8]:

# D and F are even, E is 5 and (D + E + F) % 3 == 0

# so D + F can only be 10 and thus B + H must also be 10

(H, D, F) = (10 - B, B - 2, 12 - B)

FxH = 100 * F + H

# odd numbers

for A, C, G, I in permutations((1, 3, 7, 9)):

# if B = 4 and A = 3 or 9 then (A + B + C) can't be a multiple of 3

# if B = 4 then values (1, 7) for A lead to resp. values (7, 1) for C

if B == 4 and A + C != 8: continue

if (A + B + C) % 3: continue

FGH = FxH + 10 * G

if FGH % 8: continue

n7 = 100 * (10 * (10 * (10 * (10 * A + B) + C) + D) + E) + FGH // 10

if n7 % 7: continue

# sum(1..9) = 45 is divisible by 9 so don't check modulo 9

print(10 * (10 * n7 + H) + I)

New Scientist Puzzle 102 – Passport to Success

by Zoe Mensch

From New Scientist #3323, 27th February 2021

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta