Sunday Times Teaser 3072 – Dial M for Marriage

by BRG on August 6, 2021

by Danny Roth

Published Sunday August 08 2021 (link)

George and Martha work in a town where phone numbers have seven digits. “That’s rare!” commented George. “If you look at your work number and mine, both exhibit only four digits of the possible ten (0-9 inclusive), each appearing at least once. Furthermore, the number of possible phone numbers with that property has just four single-digit prime number factors (each raised to a power where necessary) and those four numbers are the ones in our phone numbers.”

“And that is not all!” added Martha. “Both numbers have their highest digits first, working their way down to the lowest, and both give perfect numbers [1] when their digits are summed.”

What are two phone numbers?

[1] A perfect number equals the sum of its factors, eg, 6 = 1 + 2 + 3

From → Uncategorized

6 Comments Leave one →

Brian Gladman permalink


# represent an integer <n> as the sum 
# of <m> unordered positive integers
def split(n, m, seq=()):
  if m == 1:
    yield seq + (n,)
  else:
    for i in range(1, n - m + 2):
      yield from split(n - i, m - 1, seq + (i,))

# collect solutions
sol = set()

# consider all ways of repeating four different digits
# (each at least once) to give seven digits in total
for m4 in split(7, 4):
      
  # form the digits of possible phone numbers from single
  # digit primes in the correct (high to low) order
  dgts = sum(([d] * m for d, m in zip((7, 5, 3, 2), m4)), [])
  
  # and keep only those that sum to give a perfect number
  # (only 28 is possible)
  if sum(dgts) == 28:
    
    sol.add(''.join(str(x) for x in dgts))

a, b, *r = sorted(sol)
if not r:
  print(f"The telephone numbers are {a} and {b}.")

# represent an integer <n> as the sum

# of <m> unordered positive integers

def split(n, m, seq=()):

if m == 1:

yield seq + (n,)

else:

for i in range(1, n - m + 2):

yield from split(n - i, m - 1, seq + (i,))

# collect solutions

sol = set()

# consider all ways of repeating four different digits

# (each at least once) to give seven digits in total

for m4 in split(7, 4):

# form the digits of possible phone numbers from single

# digit primes in the correct (high to low) order

dgts = sum(([d] * m for d, m in zip((7, 5, 3, 2), m4)), [])

# and keep only those that sum to give a perfect number

# (only 28 is possible)

if sum(dgts) == 28:

sol.add(''.join(str(x) for x in dgts))

a, b, *r = sorted(sol)

if not r:

print(f"The telephone numbers are {a} and {b}.")

or using my number_theory library:


from number_theory import frobenius_solve

sol = []
# express the only possible perfect number (28) as the sum of
# seven non-zero digits that are multiples of the four single
# digit primes (2, 3, 5 and 7) with at least one of each
for s in frobenius_solve((7, 5, 3, 2), 28, min_m=1, m_sum=7):
  # form the digit sequence in non-increasing order
  dgts = sum(([d] * m for d, m in zip([7, 5, 3, 2], s)), [])
  sol.append(''.join(str(x) for x in dgts))
print(f"The telephone numbers are {sol[0]} and {sol[1]}.")

from number_theory import frobenius_solve

sol = []

# express the only possible perfect number (28) as the sum of

# seven non-zero digits that are multiples of the four single

# digit primes (2, 3, 5 and 7) with at least one of each

for s in frobenius_solve((7, 5, 3, 2), 28, min_m=1, m_sum=7):

# form the digit sequence in non-increasing order

dgts = sum(([d] * m for d, m in zip([7, 5, 3, 2], s)), [])

sol.append(''.join(str(x) for x in dgts))

print(f"The telephone numbers are {sol[0]} and {sol[1]}.")

Frits permalink


from functools import reduce

# convert digits sequence to number
d2n = lambda s: reduce(lambda x, y: 10 * x + y, s)

# decompose number <t> into <k> non-increasing numbers from <ns>
# so that sum(<k> numbers) equals <t>
def decompose(t, k, ns, s=[-99], minval=0):
  if k == 1:
    # check that all ns elements have been used
    if t in ns and t <= s[-1] and len(set(s + [t])) == len(ns):
      yield s + [t]
  else:
    for n in ns:
      if n <= s[-1] and t - n >= (k - 1) * minval: 
        yield from decompose(t - n, k - 1, ns, s + [n], minval)

# minimum 7 digits = 7+5+3+2+2+2+2 = 23, maximum 7 digits = 7+7+7+7+5+3+2 = 38
# find perfect numbers between 23 and 38
# -- even perfect number have to end in 1, base 9 
# -- no odd perfect numbers are known (numbers have been checked up to 10^1500)
perfnums = [28]   

for pn in perfnums:
  # start decomposition with 4 known elements
  lst = list(decompose(pn - 17, 3, [7, 5, 3, 2], [5, 3, 2, 7], 2))
  if len(lst) > 1:
    for x in lst:
      print(d2n(sorted(x, reverse=True)), "->", pn)

from functools import reduce

# convert digits sequence to number

d2n = lambda s: reduce(lambda x, y: 10 * x + y, s)

# decompose number <t> into <k> non-increasing numbers from <ns>

# so that sum(<k> numbers) equals <t>

def decompose(t, k, ns, s=[-99], minval=0):

if k == 1:

# check that all ns elements have been used

if t in ns and t <= s[-1] and len(set(s + [t])) == len(ns):

yield s + [t]

else:

for n in ns:

if n <= s[-1] and t - n >= (k - 1) * minval:

yield from decompose(t - n, k - 1, ns, s + [n], minval)

# minimum 7 digits = 7+5+3+2+2+2+2 = 23, maximum 7 digits = 7+7+7+7+5+3+2 = 38

# find perfect numbers between 23 and 38

# -- even perfect number have to end in 1, base 9

# -- no odd perfect numbers are known (numbers have been checked up to 10^1500)

perfnums = [28]

for pn in perfnums:

# start decomposition with 4 known elements

lst = list(decompose(pn - 17, 3, [7, 5, 3, 2], [5, 3, 2, 7], 2))

if len(lst) > 1:

for x in lst:

print(d2n(sorted(x, reverse=True)), "->", pn)

GeoffR permalink


# for saving telephone numbers
nbrs = []

# consider 7-digit numbers with the specified digit patterns ...
for n in range(7532222, 7777532 + 1):
  
  # ... that use only the four digits 2, 3, 5 and 7
  if set(str(n)) == set('2357'):
    
    # extract the digits ...
    dgts = [int(x) for x in str(n)]
    # ... which must sum to a perfect number (only 28
    # is possible) and digits are in non-increasing order 
    if sum(dgts) == 28 and sorted(dgts) == dgts[::-1]:
      nbrs.append(n)

print(f"The telephone numbers are {nbrs[0]} and {nbrs[1]}.")

# for saving telephone numbers

nbrs = []

# consider 7-digit numbers with the specified digit patterns ...

for n in range(7532222, 7777532 + 1):

# ... that use only the four digits 2, 3, 5 and 7

if set(str(n)) == set('2357'):

# extract the digits ...

dgts = [int(x) for x in str(n)]

# ... which must sum to a perfect number (only 28

# is possible) and digits are in non-increasing order

if sum(dgts) == 28 and sorted(dgts) == dgts[::-1]:

nbrs.append(n)

print(f"The telephone numbers are {nbrs[0]} and {nbrs[1]}.")

John Z permalink


# The four single digit primes are 2, 3, 5, 7.
# There are no other single digit primes so the phone numbers contain only these
# The first 4 perfect numbers  are 6, 28, 496
# The 7 digit phone numbers digits can sum to a minimum of:
# 7 + 5 + 3 + 1 * 4 = 23
# and can sum to a maximum of :
# 7 * 4 + 5 + 3 + 2 = 38
# The digits therefore must sum to the perfect number 28


# Any digit can be repeated up to 4 times in the seven digit phone number

# consider number of digits that are 7
for d7 in range(1, 5):
  # dc = number of digits in phone number so far
  dc = d7
  
  for d5 in range(1, 6 - dc):
    dc = d7 + d5
    
    for d3 in range(1, 7 - dc):
      dc = d7 + d5 + d3
      
      d2 = 7 - dc

      # do digits sum to the perfect number 28?
      if d2 * 2 + d3 * 3 + d5 * 5 + d7 * 7 == 28:
        
        # print with digits highest to lowest
        print("phone number", '7 ' * d7 + '5 ' * d5 + '3 ' * d3 + '2 ' * d2)

# The four single digit primes are 2, 3, 5, 7.

# There are no other single digit primes so the phone numbers contain only these

# The first 4 perfect numbers are 6, 28, 496

# The 7 digit phone numbers digits can sum to a minimum of:

# 7 + 5 + 3 + 1 * 4 = 23

# and can sum to a maximum of :

# 7 * 4 + 5 + 3 + 2 = 38

# The digits therefore must sum to the perfect number 28

# Any digit can be repeated up to 4 times in the seven digit phone number

# consider number of digits that are 7

for d7 in range(1, 5):

# dc = number of digits in phone number so far

dc = d7

for d5 in range(1, 6 - dc):

dc = d7 + d5

for d3 in range(1, 7 - dc):

dc = d7 + d5 + d3

d2 = 7 - dc

# do digits sum to the perfect number 28?

if d2 * 2 + d3 * 3 + d5 * 5 + d7 * 7 == 28:

# print with digits highest to lowest

print("phone number", '7 ' * d7 + '5 ' * d5 + '3 ' * d3 + '2 ' * d2)

Frits permalink

Simple and efficient (allthough not directly tuned to 28).

Reply

John Z permalink

Here’s a slightly more compact solution


from itertools import product

# generate the digit multipliers for 7, 5, 3, 2
for d in product((1, 2, 3, 4), repeat = 4):

  # check if 7 digits in all and they sum to perfect number 
  if sum(d) == 7 and d[0] * 7 + d[1] * 5 + d[2] * 3 + d[3] * 2 == 28:
    print('phone # ' + d[0] * '7 ' + d[1] * '5 ' + d[2] * '3 ' + d[3] * '2 ')

from itertools import product

# generate the digit multipliers for 7, 5, 3, 2

for d in product((1, 2, 3, 4), repeat = 4):

# check if 7 digits in all and they sum to perfect number

if sum(d) == 7 and d[0] * 7 + d[1] * 5 + d[2] * 3 + d[3] * 2 == 28:

print('phone # ' + d[0] * '7 ' + d[1] * '5 ' + d[2] * '3 ' + d[3] * '2 ')

Sunday Times Teaser 3072 – Dial M for Marriage

by Danny Roth

Published Sunday August 08 2021 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta