Sunday Times Teaser 3053 – Endless Number

by BRG on March 26, 2021

by Danny Roth

Published Sunday March 28 2021 (link)

George and Martha have a telephone number consisting of nine digits; there is no zero and the others appear once each. The total of the digits is obviously 45, so that the number is divisible by nine. Martha noticed that, if she removed the last (ie, the least significant) digit, an eight-digit number would remain, divisible by eight. George added that you could continue this process, removing the least significant digit each time to be left with an n-digit number divisible by n right down to the end.

What is their telephone number?

From → Uncategorized

5 Comments Leave one →

Brian Gladman permalink


from itertools import permutations

# odd (even) digits go into odd (even) positions, 
# five goes into the middle position
for p in permutations('2468'):
  for q in permutations('1379'):
    n = nbr = int(''.join(i + j for i, j in 
                zip(q[:2] + ('5',) + q[2:], p + ('',))))
    for i in range(1, 7):
      n //= 10
      if n % (9 - i):
        break
    else:
      print(f"The telephone number is {nbr}")

from itertools import permutations

# odd (even) digits go into odd (even) positions,

# five goes into the middle position

for p in permutations('2468'):

for q in permutations('1379'):

n = nbr = int(''.join(i + j for i, j in

zip(q[:2] + ('5',) + q[2:], p + ('',))))

for i in range(1, 7):

n //= 10

if n % (9 - i):

break

else:

print(f"The telephone number is {nbr}")

Erling Torkildsen permalink

By trading shortcuts (from analysis) for a uniform routine, a recursive-like approach can be used:


# The leftmost (n = 1) possible digits are
s = [1, 3, 7, 9]
# The possible numbers with n + 1 digits are then 
for n in range(2, 10):
  t = list()
  for a in s:
    for b in range(1, 10):
      # Check that n-digit number is divisibility by n
      if (10 * a + b) % n == 0 and str(b) not in str(a):
        t.append(10 * a + b)
  s = t

# List of possible phone numbers. Hopefully one member..
print("Phone number(s):", s)

# The leftmost (n = 1) possible digits are

s = [1, 3, 7, 9]

# The possible numbers with n + 1 digits are then

for n in range(2, 10):

t = list()

for a in s:

for b in range(1, 10):

# Check that n-digit number is divisibility by n

if (10 * a + b) % n == 0 and str(b) not in str(a):

t.append(10 * a + b)

s = t

# List of possible phone numbers. Hopefully one member..

print("Phone number(s):", s)

Frits permalink

You can also consider only b’s which have the same type (odd/even) as n.

The same puzzle has already been published on this site:

New Scientist Puzzle 102

Reply

John Z permalink

A straightforward solution:


from itertools import permutations

# phone number is a b c d e f g h i
e = 5  # fifth digit must be 5

# consider permutations of the odd digits except 5 in odd digit positions
for a, c, g, i in permutations((1, 3, 7, 9)):
  # consider permutations of the even digits except 0 in even digit positions
  for b, d, f, h, in permutations((2, 4, 6, 8)):
    
    # Divisibility check; no need to test % 1, % 2, % 5, % 9                                          
    if not((abc := a * 100 + b * 10 + c) % 3 or 
           (abcd := abc * 10 + d) % 4 or        
            (abcdef := abcd * 100 + 50 + f) % 6 or 
           (abcdefg := abcdef * 10 + g) % 7 or
           (abcdefgh := abcdefg * 10 + h) % 8):
          
      print("phone number is:", a, b, c, d, e, f, g, h, i)

from itertools import permutations

# phone number is a b c d e f g h i

e = 5 # fifth digit must be 5

# consider permutations of the odd digits except 5 in odd digit positions

for a, c, g, i in permutations((1, 3, 7, 9)):

# consider permutations of the even digits except 0 in even digit positions

for b, d, f, h, in permutations((2, 4, 6, 8)):

# Divisibility check; no need to test % 1, % 2, % 5, % 9

if not((abc := a * 100 + b * 10 + c) % 3 or

(abcd := abc * 10 + d) % 4 or

(abcdef := abcd * 100 + 50 + f) % 6 or

(abcdefg := abcdef * 10 + g) % 7 or

(abcdefgh := abcdefg * 10 + h) % 8):

print("phone number is:", a, b, c, d, e, f, g, h, i)

Another solution that doesn’t use the imported ‘permutations’ function
but uses an ad hoc recursive function:


def find_phone_num(whatsleft, phn = 0, depth = 1):
  if depth == 9:
    yield phn * 10 + whatsleft.pop() # get the last digit 
  
  else:
    # consider possible next digits from set of digits not yet used (whatsleft) 
    for a in whatsleft:
      # does the prospective phone number meet the divisibility test?
      if not(phnt := phn * 10 + a)  % depth:
        # if so, go to next level
        yield from find_phone_num(whatsleft - {a}, phnt, depth + 1)
    
for x in find_phone_num(set(range(1, 10))):

  print("Phone number is", x)

def find_phone_num(whatsleft, phn = 0, depth = 1):

if depth == 9:

yield phn * 10 + whatsleft.pop() # get the last digit

else:

# consider possible next digits from set of digits not yet used (whatsleft)

for a in whatsleft:

# does the prospective phone number meet the divisibility test?

if not(phnt := phn * 10 + a) % depth:

# if so, go to next level

yield from find_phone_num(whatsleft - {a}, phnt, depth + 1)

for x in find_phone_num(set(range(1, 10))):

print("Phone number is", x)

John Z permalink

Yes, this ship sailed many moons ago but I kept tweaking.
This version is more computationally efficient but contains 2 additional lines of code to deal with the fifth digit which analysis shows must = 5 and separates the odd and even digits.
‘whatsleft’ is renamed ‘dr’


def find_phone_num(dr = ({2, 4, 6, 8}, {1, 3, 7, 9}), phn = 0, depth = 1):
  
# dr 'digits remaining' is a tuple containing two sets:
# the remaining even digits, the remaining odd digits except 5
# phn is the phone number to which one digit is added with each recursion
# depth = level of recursion = digit position

  # test if all digits have been placed according to criteria: depth = 10
  if depth == 10:
      yield phn # the 9 digit phone number
      
  elif depth == 5:
    # 5th digit must be 5; add it to phone number; skip % 5; go to next level
    yield from find_phone_num(dr, phn * 10 + 5, depth + 1)
       
  else:
    # consider possible next digits from sets of remaining even or odd digits  
    for d in dr[depth & 1]:
      # does the prospective phone number meet the divisibility test?
      if (phnt := phn * 10 + d) % depth == 0:
        # digit found 'd' is removed from the appropriate set; go to next level
        yield from find_phone_num((dr[0] - {d}, dr[1] - {d}), phnt, depth + 1)
        
    # digits exhausted: fall through bottom; drop back one level

  
for x in find_phone_num():

  print("Phone number is", ' '.join(str(x)))

def find_phone_num(dr = ({2, 4, 6, 8}, {1, 3, 7, 9}), phn = 0, depth = 1):

# dr 'digits remaining' is a tuple containing two sets:

# the remaining even digits, the remaining odd digits except 5

# phn is the phone number to which one digit is added with each recursion

# depth = level of recursion = digit position

# test if all digits have been placed according to criteria: depth = 10

if depth == 10:

yield phn # the 9 digit phone number

elif depth == 5:

# 5th digit must be 5; add it to phone number; skip % 5; go to next level

yield from find_phone_num(dr, phn * 10 + 5, depth + 1)

else:

# consider possible next digits from sets of remaining even or odd digits

for d in dr[depth & 1]:

# does the prospective phone number meet the divisibility test?

if (phnt := phn * 10 + d) % depth == 0:

# digit found 'd' is removed from the appropriate set; go to next level

yield from find_phone_num((dr[0] - {d}, dr[1] - {d}), phnt, depth + 1)

# digits exhausted: fall through bottom; drop back one level

for x in find_phone_num():

print("Phone number is", ' '.join(str(x)))

Sunday Times Teaser 3053 – Endless Number

by Danny Roth

Published Sunday March 28 2021 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta