Sunday Times Teaser 2489 – No Title

by Victor Bryant

Published June 6 2010 (link)

Your task today is to put more than two digits evenly spaced around a circle so that:

Any three adjacent digits clockwise form a prime number.

Any three adjacent digits anti-clockwise form a prime number.

If a digit occurs in the circle, then it occurs a prime number of times;

The total of all the digits around the circle is a prime.

What is the total of all the digits?

One Comment Leave one →

Brian Gladman permalink


from itertools import count
from collections import defaultdict
from number_theory import Primes, is_prime

# since all three digit sequences around the circle are
# prime, the digits can only be 1, 3, 7 or 9; since the
# three digit sequences are scanned in both directions, 
# we need primes that are also primes when their digits
# are reversed; the digits that can follow each 3 digit
# prime are determined by the prime's last two digits

# map the leading two digits of allowable three digit
# primes to their possible third digits
d2_3 = defaultdict(set) 
for p in Primes().list(100, 1000):
  sp = str(p)
  if set(sp) <= set('1379') and is_prime(int(sp[::-1])):
    dgts = tuple(int(x) for x in str(p))
    d2_3[dgts[:2]].add(dgts[2])

# find sequences around a circle of length <n> for which
# every three digit sequence in either direction is prime
def compose(dgts, n, d2_3):  
  if len(dgts) == n:
    # only return sequences that wrap around correctly
    if dgts[0] in d2_3[dgts[-2:]] and dgts[1] in d2_3[(dgts[-1], dgts[0])]:
      yield dgts
  else:
    # extend the sequence
    for d in d2_3[dgts[-2:]]:
      yield from compose(dgts + (d,), n, d2_3)

# consider increasing length sequences
for n in count(3):
  # consider all possible initial two values 
  for d2 in sorted(d2_3.keys()):
    # and find sequences that give all three digit sequences 
    # around the circle in either direction as prime
    for s in compose(d2, n, d2_3):
      # the sum of the values must be prime and each digit must occur
      # a prime number of times
      if is_prime(sum(s)) and all(is_prime(s.count(d)) for d in set(s)):
        print(f'sum = {sum(s)}, sequence = {s}.')
        exit(0)

from itertools import count

from collections import defaultdict

from number_theory import Primes, is_prime

# since all three digit sequences around the circle are

# prime, the digits can only be 1, 3, 7 or 9; since the

# three digit sequences are scanned in both directions,

# we need primes that are also primes when their digits

# are reversed; the digits that can follow each 3 digit

# prime are determined by the prime's last two digits

# map the leading two digits of allowable three digit

# primes to their possible third digits

d2_3 = defaultdict(set)

for p in Primes().list(100, 1000):

sp = str(p)

if set(sp) <= set('1379') and is_prime(int(sp[::-1])):

dgts = tuple(int(x) for x in str(p))

d2_3[dgts[:2]].add(dgts[2])

# find sequences around a circle of length <n> for which

# every three digit sequence in either direction is prime

def compose(dgts, n, d2_3):

if len(dgts) == n:

# only return sequences that wrap around correctly

if dgts[0] in d2_3[dgts[-2:]] and dgts[1] in d2_3[(dgts[-1], dgts[0])]:

yield dgts

else:

# extend the sequence

for d in d2_3[dgts[-2:]]:

yield from compose(dgts + (d,), n, d2_3)

# consider increasing length sequences

for n in count(3):

# consider all possible initial two values

for d2 in sorted(d2_3.keys()):

# and find sequences that give all three digit sequences

# around the circle in either direction as prime

for s in compose(d2, n, d2_3):

# the sum of the values must be prime and each digit must occur

# a prime number of times

if is_prime(sum(s)) and all(is_prime(s.count(d)) for d in set(s)):

print(f'sum = {sum(s)}, sequence = {s}.')

exit(0)

Sunday Times Teaser 2489 – No Title

by Victor Bryant

Published June 6 2010 (link)

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta