Sunday Times Teaser 3311 – Calling From Home


from itertools import combinations
from collections import defaultdict
from math import prod

# primes below 50
prms = [2, 3, 5, 7]
prms += [n for n in range(11, 50, 2) if all(n % p for p in prms)]

# return true if integer <n> is a palindrome
is_palindrome = lambda n: (t := str(n)) == t[::-1]
  
# index solutions on the parity of the total cost
sols = defaultdict(list)

# choose the values for the four prime call lengths
for p4 in combinations(prms, 4):
  # ensure that an exact hour can be spent in calls
  if not 59 <= sum(p4) <= 64:
    continue
  # check that the product of the primes is a palindrome ...
  if not is_palindrome((m := prod(p4))):
    continue
  # ... and that the sum of its digits is an odd single digit number
  if (ds := sum(int(d) for d in str(m))) > 9 or not (ds & 1):
    continue
  print(f"Call lengths {(1,) + p4}")
  # the two tariffs for  each call (t2 < t1)
  for t2, t1 in combinations(range(1, 10), 2):
    # the total cost is a palindrome
    costs = 5 * t1 + sum(m - 5 for m in p4 if m > 5) * t2
    if is_palindrome(costs):
      sols[costs & 1].append((costs, m))
      print(f"   {t1 = }, {t2 = }, {costs = :3}")

# output the unique result  
for sol in sols.values():
  if len(sol) == 1:
    print(f"\nThe palindromes are {sol[0][0]} and {sol[0][1]}.")

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

from itertools import combinations

from collections import defaultdict

from math import prod

# primes below 50

prms = [2, 3, 5, 7]

prms += [n for n in range(11, 50, 2) if all(n % p for p in prms)]

# return true if integer <n> is a palindrome

is_palindrome = lambda n: (t := str(n)) == t[::-1]

# index solutions on the parity of the total cost

sols = defaultdict(list)

# choose the values for the four prime call lengths

for p4 in combinations(prms, 4):

# ensure that an exact hour can be spent in calls

if not 59 <= sum(p4) <= 64:

continue

# check that the product of the primes is a palindrome ...

if not is_palindrome((m := prod(p4))):

continue

# ... and that the sum of its digits is an odd single digit number

if (ds := sum(int(d) for d in str(m))) > 9 or not (ds & 1):

continue

print(f"Call lengths {(1,) + p4}")

# the two tariffs for each call (t2 < t1)

for t2, t1 in combinations(range(1, 10), 2):

# the total cost is a palindrome

costs = 5 * t1 + sum(m - 5 for m in p4 if m > 5) * t2

if is_palindrome(costs):

sols[costs & 1].append((costs, m))

print(f" {t1 = }, {t2 = }, {costs = :3}")

# output the unique result

for sol in sols.values():

if len(sol) == 1:

print(f"\nThe palindromes are {sol[0][0]} and {sol[0][1]}.")

Reply

John Z. permalink


from itertools import combinations
from math import prod

# generate primes numbers which can sum to 60
p = (2, 3, 5, 7)
p += tuple(i for i in range(3, 48, 2) if all(i % x for x in p))

# lists of palindromic costs indexed by even (0) / odd (1)
costs = [[], []]
# get combinations of 4 prime numbers
for ts in combinations(p, 4):
  # do they sum to total of call minutes taking into account rounding up?
  if 59 < sum(ts) < 66:
    # get the string of the product of the primes
    pr = str(pts := prod(ts))
    # is it palindromic? do its digits sum to l odd digit?
    if pr == pr[::-1] and (sd := sum(map(int, pr))) < 10 and sd & 1: 
      # consider per minute charge and per call charge
      for pm, pc in combinations(range(1, 10), 2):
        # add per call charges + per minute charges to get total cost 
        cost = 5 * pc + sum(pm * (t - 5) for t in ts if t > 5)
        # is cost palindromic
        if str(cost) == str(cost)[::-1]:
          # insert the 2 palindromes into list based on odd / even
          costs[cost & 1] += [[pts, cost]]

# unique pair of palindromes
p2 = [c for c in costs if len(c) == 1][0][0]

print('Palindromes:', *sorted(p2))

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

from itertools import combinations

from math import prod

# generate primes numbers which can sum to 60

p = (2, 3, 5, 7)

p += tuple(i for i in range(3, 48, 2) if all(i % x for x in p))

# lists of palindromic costs indexed by even (0) / odd (1)

costs = [[], []]

# get combinations of 4 prime numbers

for ts in combinations(p, 4):

# do they sum to total of call minutes taking into account rounding up?

if 59 < sum(ts) < 66:

# get the string of the product of the primes

pr = str(pts := prod(ts))

# is it palindromic? do its digits sum to l odd digit?

if pr == pr[::-1] and (sd := sum(map(int, pr))) < 10 and sd & 1:

# consider per minute charge and per call charge

for pm, pc in combinations(range(1, 10), 2):

# add per call charges + per minute charges to get total cost

cost = 5 * pc + sum(pm * (t - 5) for t in ts if t > 5)

# is cost palindromic

if str(cost) == str(cost)[::-1]:

# insert the 2 palindromes into list based on odd / even

costs[cost & 1] += [[pts, cost]]

# unique pair of palindromes

p2 = [c for c in costs if len(c) == 1][0][0]

print('Palindromes:', *sorted(p2))

Reply

BRG permalink

Here is an alternative approach.


from itertools import combinations, product
from collections import defaultdict

# return true if integer <n> is a palindrome
is_palindrome = lambda n: (t := str(n)) == t[::-1]

# factor <n> into its prime factors
def prime_factors(n):
  i = 2
  while i * i <= n:
    if n % i:
      i += 1
    else:
      n //= i
      yield i
  if n > 1:
    yield(n)

# index solutions on the parity of the total cost
sols = defaultdict(list)

# consider palindromes of up to 7 digits
for n in range(2, 8):
  nd = (n + 1) // 2
  # consider the digits for the palindrome
  for ds in product(range(10), repeat=nd):
    # no leading zeros
    if ds[0] == 0 or n == 7 and ds[0] > 3:
      continue
    # create the palindrome
    ns = ds + ds[::-1][(1 if n & 1 else 0):]
    m = int(''.join(str(d) for d in ns))
    # the sum of its digits is an odd single digit number
    if (ds := sum(int(d) for d in str(m))) > 9 or not (ds & 1):
      continue
    # factor the palindrome
    p4 = tuple(prime_factors(m))
    if not (len(p4) == len(set(p4)) == 4 and p4[-1] < 50):
      continue
    print(f"Call lengths {(1,) + p4}")
    # the two tariffs for  each call (t2 < t1)
    for t2, t1 in combinations(range(1, 10), 2):
      # the total cost is a palindrome
      costs = 5 * t1 + sum(m - 5 for m in p4 if m > 5) * t2
      if is_palindrome(costs):
        sols[costs & 1].append((costs, m))
        print(f"   {t1 = }, {t2 = }, {costs = :3}")

# output the unique result  
for sol in sols.values():
  if len(sol) == 1:
    print(f"\nThe palindromes are {sol[0][0]} and {sol[0][1]}")

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

from itertools import combinations, product

from collections import defaultdict

# return true if integer <n> is a palindrome

is_palindrome = lambda n: (t := str(n)) == t[::-1]

# factor <n> into its prime factors

def prime_factors(n):

i = 2

while i * i <= n:

if n % i:

i += 1

else:

n //= i

yield i

if n > 1:

yield(n)

# index solutions on the parity of the total cost

sols = defaultdict(list)

# consider palindromes of up to 7 digits

for n in range(2, 8):

nd = (n + 1) // 2

# consider the digits for the palindrome

for ds in product(range(10), repeat=nd):

# no leading zeros

if ds[0] == 0 or n == 7 and ds[0] > 3:

continue

# create the palindrome

ns = ds + ds[::-1][(1 if n & 1 else 0):]

m = int(''.join(str(d) for d in ns))

# the sum of its digits is an odd single digit number

if (ds := sum(int(d) for d in str(m))) > 9 or not (ds & 1):

continue

# factor the palindrome

p4 = tuple(prime_factors(m))

if not (len(p4) == len(set(p4)) == 4 and p4[-1] < 50):

continue

print(f"Call lengths {(1,) + p4}")

# the two tariffs for each call (t2 < t1)

for t2, t1 in combinations(range(1, 10), 2):

# the total cost is a palindrome

costs = 5 * t1 + sum(m - 5 for m in p4 if m > 5) * t2

if is_palindrome(costs):

sols[costs & 1].append((costs, m))

print(f" {t1 = }, {t2 = }, {costs = :3}")

# output the unique result

for sol in sols.values():

if len(sol) == 1:

print(f"\nThe palindromes are {sol[0][0]} and {sol[0][1]}")

Reply

JohnZ permalink

Brian here is a version of your code above with simplification of lines 24 – 37 taking into account that for a palindrome to sum to an odd number, it must have an odd number of digits


from itertools import combinations
from collections import defaultdict

# return true if integer  is a palindrome
is_palindrome = lambda n: (t := str(n)) == t[::-1]

# factor  into its prime factors
def prime_factors(n):
  i = 2
  while i * i <= n:
    if n % i:
      i += 1
    else:
      n //= i
      yield i
  if n > 1:
    yield n

# index solutions on the parity of the total cost
sols = defaultdict(list)

# consider palindromes of up to 7 digits (ie. '1573' + '751') 
for n in range(1, 10000, 2):
  ds = str(n)
  # create the palindrome (must have an odd number of digits to sum to odd)
  ns = ds + ds[::-1][1:]
  # the sum of its digits is an odd single digit number
  if sum(map(int, ns)) not in (1, 3, 5, 7, 9):
    continue
  m = int(ns)
  # factor the palindrome
  p4 = tuple(prime_factors(m))
  if not (len(p4) == len(set(p4)) == 4 and p4[-1] < 50):
    continue
  print(f"Call lengths {(1,) + p4}")
  # the two tariffs for  each call (t2 < t1)
  for t2, t1 in combinations(range(1, 10), 2):
    # the total cost is a palindrome
    costs = 5 * t1 + sum(m - 5 for m in p4 if m > 5) * t2
    if is_palindrome(costs):
      sols[costs & 1].append((costs, m))
      print(f"   {t1 = }, {t2 = }, {costs = :3}")

for sol in sols.values():
  if len(sol) == 1:
    print(f"\nThe palindromes are {sol[0][0]} and {sol[0][1]}")

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

from itertools import combinations

from collections import defaultdict

# return true if integer is a palindrome

is_palindrome = lambda n: (t := str(n)) == t[::-1]

# factor into its prime factors

def prime_factors(n):

i = 2

while i * i <= n:

if n % i:

i += 1

else:

n //= i

yield i

if n > 1:

yield n

# index solutions on the parity of the total cost

sols = defaultdict(list)

# consider palindromes of up to 7 digits (ie. '1573' + '751')

for n in range(1, 10000, 2):

ds = str(n)

# create the palindrome (must have an odd number of digits to sum to odd)

ns = ds + ds[::-1][1:]

# the sum of its digits is an odd single digit number

if sum(map(int, ns)) not in (1, 3, 5, 7, 9):

continue

m = int(ns)

# factor the palindrome

p4 = tuple(prime_factors(m))

if not (len(p4) == len(set(p4)) == 4 and p4[-1] < 50):

continue

print(f"Call lengths {(1,) + p4}")

# the two tariffs for each call (t2 < t1)

for t2, t1 in combinations(range(1, 10), 2):

# the total cost is a palindrome

costs = 5 * t1 + sum(m - 5 for m in p4 if m > 5) * t2

if is_palindrome(costs):

sols[costs & 1].append((costs, m))

print(f" {t1 = }, {t2 = }, {costs = :3}")

for sol in sols.values():

if len(sol) == 1:

print(f"\nThe palindromes are {sol[0][0]} and {sol[0][1]}")

Reply

BRG permalink

Yes, I missed that issue. Starting with the palindrome is a lot slower than the earlier alternative. However the speed can be competitive, albeit with a lot of additional code


from itertools import combinations
from collections import defaultdict

# return true if integer <n> is a palindrome
is_palindrome = lambda n: (t := str(n)) == t[::-1]

# factor <n> into its prime factors
def prime_factors(n):
  i = 2
  while i * i <= n:
    if n % i:
      i += 1
    else:
      n //= i
      yield i
  if n > 1:
    yield(n)

# partition an integer <v> into the sum of <n> 
# non-negative integers in all orders
def split(v, n, vs=()):
  if n == 1:
    yield vs + (v,)
  else:
    for i in range(v + 1):
      yield from split(v - i, n - 1, vs + (i,))

# index solutions on the parity of the total cost
sols = defaultdict(list)

# consider palindromes of up to 7 digits
# the middle digit of the palindrome
for md in range(1, 10, 2):
  # the number of left/right hand digits
  for nl in range(1, 4):
    # the sum of the left/right hand digits
    for ls in range(1, (11 - md) // 2):
      # split the sum into the number of digits needed
      for lds in split(ls, nl):
        if not lds[0]:
          continue
        pal = lds + (md,) + lds[::-1]
        m = int(''.join(str(x) for x in pal))
        p4 = tuple(prime_factors(m))
        if not (len(p4) == len(set(p4)) == 4 and p4[-1] < 50):
          continue
        print(f"Call lengths {(1,) + p4}")
        # the two tariffs for  each call (t2 < t1)
        for t2, t1 in combinations(range(1, 10), 2):
          # the total cost is a palindrome
          costs = 5 * t1 + sum(m - 5 for m in p4 if m > 5) * t2
          if is_palindrome(costs):
            sols[costs & 1].append((costs, m))
            print(f"   {t1 = }, {t2 = }, {costs = :3}")

# output the unique result  
for sol in sols.values():
  if len(sol) == 1:
    print(f"\nThe palindromes are {sol[0][0]} and {sol[0][1]}")

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

from itertools import combinations

from collections import defaultdict

# return true if integer <n> is a palindrome

is_palindrome = lambda n: (t := str(n)) == t[::-1]

# factor <n> into its prime factors

def prime_factors(n):

i = 2

while i * i <= n:

if n % i:

i += 1

else:

n //= i

yield i

if n > 1:

yield(n)

# partition an integer <v> into the sum of <n>

# non-negative integers in all orders

def split(v, n, vs=()):

if n == 1:

yield vs + (v,)

else:

for i in range(v + 1):

yield from split(v - i, n - 1, vs + (i,))

# index solutions on the parity of the total cost

sols = defaultdict(list)

# consider palindromes of up to 7 digits

# the middle digit of the palindrome

for md in range(1, 10, 2):

# the number of left/right hand digits

for nl in range(1, 4):

# the sum of the left/right hand digits

for ls in range(1, (11 - md) // 2):

# split the sum into the number of digits needed

for lds in split(ls, nl):

if not lds[0]:

continue

pal = lds + (md,) + lds[::-1]

m = int(''.join(str(x) for x in pal))

p4 = tuple(prime_factors(m))

if not (len(p4) == len(set(p4)) == 4 and p4[-1] < 50):

continue

print(f"Call lengths {(1,) + p4}")

# the two tariffs for each call (t2 < t1)

for t2, t1 in combinations(range(1, 10), 2):

# the total cost is a palindrome

costs = 5 * t1 + sum(m - 5 for m in p4 if m > 5) * t2

if is_palindrome(costs):

sols[costs & 1].append((costs, m))

print(f" {t1 = }, {t2 = }, {costs = :3}")

# output the unique result

for sol in sols.values():

if len(sol) == 1:

print(f"\nThe palindromes are {sol[0][0]} and {sol[0][1]}")

Reply

John Z. permalink

Using Brian’s alternate approach, stop the search if one parity has one cost and the other more than one. This reduces execution time significantly while adding only two lines of code.


from itertools import combinations, count
from collections import defaultdict

# return true if integer  is a palindrome
is_palindrome = lambda n: (t := str(n)) == t[::-1]

# factor  into its prime factors
def prime_factors(n):
  i = 2
  while i * i <= n:
    if n % i:
      i += 1
    else:
      n //= i
      yield i
  if n > 1:
    yield n

# index solutions on the parity of the total cost
sols = defaultdict(list)

# consider palindromes of up to 7 digits (ie. '1573' + '751') 
for n in count(1, 2):
  ds = str(n)
  # create the palindrome (must have an odd number of digits to sum to odd)
  ns = ds + ds[-2::-1] # slice from -2 to 0 reversed
  # the sum of its digits is an odd single digit number
  if sum(map(int, ns)) not in (1, 3, 5, 7, 9):
    continue
  m = int(ns)
  # factor the palindrome
  p4 = tuple(prime_factors(m))
  if not (len(p4) == len(set(p4)) == 4 and p4[-1] < 50):
    continue
  print(f"Call lengths {(1,) + p4}")
  # the two tariffs for  each call (t2 < t1)
  for t2, t1 in combinations(range(1, 10), 2):
    # the total cost is a palindrome
    costs = 5 * t1 + sum(m - 5 for m in p4 if m > 5) * t2
    if is_palindrome(costs):
      sols[costs & 1].append((costs, m))
      print(f"   {t1 = }, {t2 = }, {costs = :3}")
      if len(sols) > 1:
        # stop search if one parity has one cost and the other more than one
        if (ls := sorted(map(len,sols.values())))[0] == 1 and ls[1] > 1:

          for sol in sols.values():
            if len(sol) == 1:
              print(f"\nThe palindromes are {sol[0][0]} and {sol[0][1]}")
              exit()

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

from itertools import combinations, count

from collections import defaultdict

# return true if integer is a palindrome

is_palindrome = lambda n: (t := str(n)) == t[::-1]

# factor into its prime factors

def prime_factors(n):

i = 2

while i * i <= n:

if n % i:

i += 1

else:

n //= i

yield i

if n > 1:

yield n

# index solutions on the parity of the total cost

sols = defaultdict(list)

# consider palindromes of up to 7 digits (ie. '1573' + '751')

for n in count(1, 2):

ds = str(n)

# create the palindrome (must have an odd number of digits to sum to odd)

ns = ds + ds[-2::-1] # slice from -2 to 0 reversed

# the sum of its digits is an odd single digit number

if sum(map(int, ns)) not in (1, 3, 5, 7, 9):

continue

m = int(ns)

# factor the palindrome

p4 = tuple(prime_factors(m))

if not (len(p4) == len(set(p4)) == 4 and p4[-1] < 50):

continue

print(f"Call lengths {(1,) + p4}")

# the two tariffs for each call (t2 < t1)

for t2, t1 in combinations(range(1, 10), 2):

# the total cost is a palindrome

costs = 5 * t1 + sum(m - 5 for m in p4 if m > 5) * t2

if is_palindrome(costs):

sols[costs & 1].append((costs, m))

print(f" {t1 = }, {t2 = }, {costs = :3}")

if len(sols) > 1:

# stop search if one parity has one cost and the other more than one

if (ls := sorted(map(len,sols.values())))[0] == 1 and ls[1] > 1:

for sol in sols.values():

if len(sol) == 1:

print(f"\nThe palindromes are {sol[0][0]} and {sol[0][1]}")

exit()

Reply

John Z. permalink

An amalgam of the two methods with various tweaks. The last two of three conditions in the ‘if’ statement of line 28 appear to be redundant but this is hard to prove, so: belt and braces.


from itertools import combinations, count

# two bespoke product of list/tuple functions; one recursive, one linear
#prod = lambda m, p = 1: prod(m[1:], m[0] * p) if m else p # recursive

prod = lambda m, p = 1: [p := p * a for a in m][-1] # linear

# generate primes numbers which can sum to 60
p = (2, 3, 5, 7)
p += tuple(i for i in range(11, 48, 2) if all(i % x for x in p))

# index solutions on the parity (0, 1) of the total cost
sols = {0: [], 1: []}

# consider left half of palindromes; central digit must be odd to sum to odd
for n in count(1, 2):
  ds = str(n)
  # create the palindrome (must have an odd number of digits to sum to odd)
  ns = ds + ds[-2::-1] # slice: all except last digit, reversed
  # the sum of its digits is an odd single digit number
  if sum(map(int, ns)) not in (1, 3, 5, 7, 9):
    continue
  m = int(ns)
  # find some or all factors of palindrome from list of primes above
  p4 = tuple(a for a in p if m % a == 0)
  # are conditions met: 4 prime calls; sum of times ~60; product is palindrome
  if len(p4) != 4 or not 59 < sum(p4) < 64 or prod(p4) != m:
    continue
  print(f"Call lengths {(1,) + p4}")
  # the two tariffs for  each call (t2 < t1)
  for t2, t1 in combinations(range(1, 10), 2):
    # the total cost 
    costs = 5 * t1 + sum(m - 5 for m in p4 if m > 5) * t2
    # is the total cost a palindrome
    if (t := str(costs)) == t[::-1]:
      sols[costs & 1].append((costs, m))
      print(f"   {t1 = }, {t2 = }, {costs = :3}")
      # stop search if one parity has exactly 1 cost and the other more than 1
      if (ls := sorted(map(len,sols.values())))[0] == 1 and ls[1] > 1:
        # solution is the value of the parity-key that has 1 cost (the least)
        sol = min(sols.values(), key = len)
        print(f"\nThe palindromes are {sol[0][0]} and {sol[0][1]}")
        exit()

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

from itertools import combinations, count

# two bespoke product of list/tuple functions; one recursive, one linear

#prod = lambda m, p = 1: prod(m[1:], m[0] * p) if m else p # recursive

prod = lambda m, p = 1: [p := p * a for a in m][-1] # linear

# generate primes numbers which can sum to 60

p = (2, 3, 5, 7)

p += tuple(i for i in range(11, 48, 2) if all(i % x for x in p))

# index solutions on the parity (0, 1) of the total cost

sols = {0: [], 1: []}

# consider left half of palindromes; central digit must be odd to sum to odd

for n in count(1, 2):

ds = str(n)

# create the palindrome (must have an odd number of digits to sum to odd)

ns = ds + ds[-2::-1] # slice: all except last digit, reversed

# the sum of its digits is an odd single digit number

if sum(map(int, ns)) not in (1, 3, 5, 7, 9):

continue

m = int(ns)

# find some or all factors of palindrome from list of primes above

p4 = tuple(a for a in p if m % a == 0)

# are conditions met: 4 prime calls; sum of times ~60; product is palindrome

if len(p4) != 4 or not 59 < sum(p4) < 64 or prod(p4) != m:

continue

print(f"Call lengths {(1,) + p4}")

# the two tariffs for each call (t2 < t1)

for t2, t1 in combinations(range(1, 10), 2):

# the total cost

costs = 5 * t1 + sum(m - 5 for m in p4 if m > 5) * t2

# is the total cost a palindrome

if (t := str(costs)) == t[::-1]:

sols[costs & 1].append((costs, m))

print(f" {t1 = }, {t2 = }, {costs = :3}")

# stop search if one parity has exactly 1 cost and the other more than 1

if (ls := sorted(map(len,sols.values())))[0] == 1 and ls[1] > 1:

# solution is the value of the parity-key that has 1 cost (the least)

sol = min(sols.values(), key = len)

print(f"\nThe palindromes are {sol[0][0]} and {sol[0][1]}")

exit()

Reply

Sunday Times Teaser 3311 – Calling From Home

by Andrew Skidmore

Published Sunday March 08 2026 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta