Sunday Times Teaser 3177 – Prime Birthday Card

by BRG on August 11, 2023

by Bill Kinally

Published Sunday August 13 2023 (link)

On her 11th birthday, Ann’s older brother Ben gave her a card on which he had drawn a 5×5 square grid with a different prime number in each of the cells. Every 5-cell row, column and diagonal had the same sum and, noting that 1 is not a prime, he used primes that made this sum as small as possible. The centre cell contained Ann’s age. All but one of the primes containing a digit 7 were on the two diagonals, the largest of these being in the bottom right corner. Two cells in the far right column contained a digit 5 as did two cells of the 4th row down. Four of the cells in the middle row contained a digit 3, and the largest prime on the grid was in the same column as two single digit primes.

What are the five prime numbers on the top row of the card?

From → Uncategorized

3 Comments Leave one →

BRG permalink


from itertools import count, combinations, permutations

# decompose <t> into <k> numbers from <ns>
def decompose(t, k, ns, s=[]):
  if k == 0:
    yield ()
  elif k == 1:
    if t in ns:
      yield s + [t]
  else:
    for n in ns:
      if t - n >= 3:
        yield from decompose(t - n, k - 1, ns.difference([n]), s + [n])

# odd primes below 11^2 
pr = [3, 5, 7, 11]
pr += [x for x in range(13, 121, 2) if all(x % p for p in pr)]

# the magic square variable definitions
# A B C D E
# F G H I J
# K L M N O
# P Q R S T
# U V W X Y

def solve(magic, prm):
  # consider primes that have '7' digits for the diagonals
  prms = set(prm) - {(M := 11)}
  p7s = {p for p in prms if '7' in str(p)}
  if not (0 < len(p7s) < 10):
    return
  n7 = len(p7s)
  # pick the non-diagonal prime
  for t in p7s:
    p7r = p7s - {t}
    Y = max(p7r)
    # the needed sum of the other (non '7') diagonal primes 
    rem = 2 * (magic - 11) - sum(p7r) 
    for oth in decompose(rem, 9 - n7, prms - p7r):
      # place the primes into the diagonals
      for p7 in permutations(p7r.union(oth) - {Y}, 7):
        s8 = set(p7).union([Y])
        A, G, S, E, I, Q, U = p7
        # check one diagonal 
        if A + G + M + S + Y != magic:
          continue

        # consider primes with '3' digits for the middle row   
        p3s = {p for p in prms if '3' in str(p)}          
        for p4 in permutations(p3s - s8, 4):
          if sum(p4) + M != magic:
            continue
          K, L, N, O = p4

          # consider the fifth column
          pr12 = prms.difference(p7 + p4 + (Y,))
          for J, T in decompose(magic - (E + O + Y), 2, pr12):
            if sum('5' in str(s) for s in (E, J, O, T, Y)) != 2:
              continue

            # consider the fourth row
            pr10 = pr12.difference((J, T))
            for P, R in decompose(magic - (Q + S + T), 2, pr10):
              if sum('5' in str(s) for s in (P, Q, R, S, T)) != 2:
                continue

              # now complete the first column and then the second row
              F = magic - (A + K + P + U)
              H = magic - (F + G + I + J)
              if F == H or not {F, H} < pr10.difference((P, R)):
                continue

              # complete the first row ...
              pr6 = pr10 - {P, R, F, H}
              for B, C, D in permutations(pr6, 3):
                if A + B + C + D + E != magic:
                  continue

                # ... and the last row
                for V, W, X in permutations(set(pr6).difference((B, C, D))):
                  if U + V + W + X + Y != magic:
                    continue

                  # form the magic square in row and column order
                  msq = [(A, B, C, D, E), (F, G, H, I, J), (K, L, M, N, O), 
                         (P, Q, R, S, T), (U, V, W, X, Y)]
                  cols = list(zip(*msq))

                  # check column sums
                  if any(sum(e) != magic for e in cols):
                    continue
                  assert all(sum(e) == magic for e in msq)

                  # the maximum prime is in a column with two primes < 10 
                  if sum(1 for c in cols if max(prms) in c
                         if sum(p < 10 for p in c) >= 2) == 1:
                    yield msq

# the number of primes being considered
for n in count(25):
  # consider possible combinations of these primes
  for prms in combinations(pr[:n], 25):
    # find primes that can be split into five equal sums
    magic, r = divmod(sum(prms), 5)
    if not r:
      for ms in solve(magic, prms):
        print(f"{ms[0]} {magic = } max_prime = {max(prms)}\n")
        for m in ms:
          print(''.join([f"{str(x):>4}" for x in m]))
        print()
        exit()

100

101

102

103

104

105

106

107

108

109

110

111

112

113

from itertools import count, combinations, permutations

# decompose <t> into <k> numbers from <ns>

def decompose(t, k, ns, s=[]):

if k == 0:

yield ()

elif k == 1:

if t in ns:

yield s + [t]

else:

for n in ns:

if t - n >= 3:

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

# odd primes below 11^2

pr = [3, 5, 7, 11]

pr += [x for x in range(13, 121, 2) if all(x % p for p in pr)]

# the magic square variable definitions

# A B C D E

# F G H I J

# K L M N O

# P Q R S T

# U V W X Y

def solve(magic, prm):

# consider primes that have '7' digits for the diagonals

prms = set(prm) - {(M := 11)}

p7s = {p for p in prms if '7' in str(p)}

if not (0 < len(p7s) < 10):

return

n7 = len(p7s)

# pick the non-diagonal prime

for t in p7s:

p7r = p7s - {t}

Y = max(p7r)

# the needed sum of the other (non '7') diagonal primes

rem = 2 * (magic - 11) - sum(p7r)

for oth in decompose(rem, 9 - n7, prms - p7r):

# place the primes into the diagonals

for p7 in permutations(p7r.union(oth) - {Y}, 7):

s8 = set(p7).union([Y])

A, G, S, E, I, Q, U = p7

# check one diagonal

if A + G + M + S + Y != magic:

continue

# consider primes with '3' digits for the middle row

p3s = {p for p in prms if '3' in str(p)}

for p4 in permutations(p3s - s8, 4):

if sum(p4) + M != magic:

continue

K, L, N, O = p4

# consider the fifth column

pr12 = prms.difference(p7 + p4 + (Y,))

for J, T in decompose(magic - (E + O + Y), 2, pr12):

if sum('5' in str(s) for s in (E, J, O, T, Y)) != 2:

continue

# consider the fourth row

pr10 = pr12.difference((J, T))

for P, R in decompose(magic - (Q + S + T), 2, pr10):

if sum('5' in str(s) for s in (P, Q, R, S, T)) != 2:

continue

# now complete the first column and then the second row

F = magic - (A + K + P + U)

H = magic - (F + G + I + J)

if F == H or not {F, H} < pr10.difference((P, R)):

continue

# complete the first row ...

pr6 = pr10 - {P, R, F, H}

for B, C, D in permutations(pr6, 3):

if A + B + C + D + E != magic:

continue

# ... and the last row

for V, W, X in permutations(set(pr6).difference((B, C, D))):

if U + V + W + X + Y != magic:

continue

# form the magic square in row and column order

msq = [(A, B, C, D, E), (F, G, H, I, J), (K, L, M, N, O),

(P, Q, R, S, T), (U, V, W, X, Y)]

cols = list(zip(*msq))

# check column sums

if any(sum(e) != magic for e in cols):

continue

assert all(sum(e) == magic for e in msq)

# the maximum prime is in a column with two primes < 10

if sum(1 for c in cols if max(prms) in c

if sum(p < 10 for p in c) >= 2) == 1:

yield msq

# the number of primes being considered

for n in count(25):

# consider possible combinations of these primes

for prms in combinations(pr[:n], 25):

# find primes that can be split into five equal sums

magic, r = divmod(sum(prms), 5)

if not r:

for ms in solve(magic, prms):

print(f"{ms[0]} {magic = } max_prime = {max(prms)}\n")

for m in ms:

print(''.join([f"{str(x):>4}" for x in m]))

print()

exit()

John Z permalink

Your first line which I assume is:

Python

from itertools import count, combinations, permutations

1
2
3

from itertools import count, combinations, permutations

is missing.

Reply
- BRG permalink
  
  Thanks John,
  
  Corrected now.
  
  Reply

Sunday Times Teaser 3177 – Prime Birthday Card

by Bill Kinally

Published Sunday August 13 2023 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta