Sunday Times Teaser 2841 – Crenellation Aggregation

by Stephen Hogg

Published 5th March 2017 (link)

The castle’s crenellated outer walls formed a pentagon, and on a family visit we decided to count the crenels. My son counted the number on each side and found that these totals on each side were five consecutive two figure numbers. My daughter and wife started together and then one of them walked clockwise around the walls and the other walked anticlockwise. They each counted the crenels they passed until they met. Their totals were two different prime numbers (with no prime number between the two). I consulted the tourist leaflet and found that the total number of crenels was in fact the product of three prime numbers.

How many crenels were there in total?

5 Comments Leave one →

Brian Gladman permalink


from number_theory import Primes

# if the middle value in the five consecutive values is N, the sum
# of the five values is 5 times N; and, since this is also the sum
# of two consecutive odd primes, it is also a multiple of 2 and 10

# the third prime factor of the number of crenellations
for nbr in Primes().range(6, 49):
  # the total number of crenellations
  cren = 10 * nbr
  # a prime number generator
  pr = Primes().range()
  # look for two consecutive primes with this sum
  p, q = 0, next(pr)
  while not p + q > cren:
    p, q = q, next(pr)
    if p + q == cren:
      print(f'There were {cren} crenels (sum({2*nbr-2}..{2*nbr+2})'
            f' = {p} + {q} = 2 x 5 x {nbr}).')

from number_theory import Primes

# if the middle value in the five consecutive values is N, the sum

# of the five values is 5 times N; and, since this is also the sum

# of two consecutive odd primes, it is also a multiple of 2 and 10

# the third prime factor of the number of crenellations

for nbr in Primes().range(6, 49):

# the total number of crenellations

cren = 10 * nbr

# a prime number generator

pr = Primes().range()

# look for two consecutive primes with this sum

p, q = 0, next(pr)

while not p + q > cren:

p, q = q, next(pr)

if p + q == cren:

print(f'There were {cren} crenels (sum({2*nbr-2}..{2*nbr+2})'

f' = {p} + {q} = 2 x 5 x {nbr}).')

Jim Randell permalink

Here’s my solution.

It considers pairs of consecutive primes, and runs in 39ms.


from enigma import Primes, tuples, printf

# the total number can be expressed as:
#
# t = 5n + 10 (10 <= n <= 95, so 60 <= t <= 485)
# t = p1 + p2 (p1, p2 are consecutive primes)
# t = q1 * q2 * q3 (q1, q2, q3 are primes)

# consider primes less than 485
primes = Primes(485)

# consider consecutive pairs of primes
for (p1, p2) in tuples(primes, 2):
  # form the total
  t = p1 + p2
  if t < 60: continue
  if t > 485: break

  # check it can be expressed as 5n + 10
  (n, r) = divmod(t - 10, 5)
  if r != 0: continue

  # check it is the product of three prime numbers
  qs = primes.factor(t)
  if len(qs) != 3: continue

  printf("{t} = +({n}..{n4}) = {p1} + {p2} = *{qs}", n4=n + 4)

from enigma import Primes, tuples, printf

# the total number can be expressed as:

# t = 5n + 10 (10 <= n <= 95, so 60 <= t <= 485)

# t = p1 + p2 (p1, p2 are consecutive primes)

# t = q1 * q2 * q3 (q1, q2, q3 are primes)

# consider primes less than 485

primes = Primes(485)

# consider consecutive pairs of primes

for (p1, p2) in tuples(primes, 2):

# form the total

t = p1 + p2

if t < 60: continue

if t > 485: break

# check it can be expressed as 5n + 10

(n, r) = divmod(t - 10, 5)

if r != 0: continue

# check it is the product of three prime numbers

qs = primes.factor(t)

if len(qs) != 3: continue

printf("{t} = +({n}..{n4}) = {p1} + {p2} = *{qs}", n4=n + 4)

We could use a bit of analysis to reduce the range of primes we consider, but it doesn’t seem worth it.

The enigma.py library is available at [ https://www.magwag.plus.com/jim/enigma.html ].

geoffrounce permalink

Here is a variation, based on the above approach of starting with adjacent primes:


from number_theory import Primes, factors

# minimum total for five consecutive 2-digit numbers = 10 + 11 + 12 + 13 + 14 =  60
# maximum total for five consecutive 2-digit numbers = 95 + 96 + 97 + 98 + 99 = 485

# form a set holding the totals of five consecutive numbers
nt_set = set()
for n in range(10, 96):
  nt = n + (n + 1) + (n + 2) + (n + 3) + (n + 4)
  nt_set.add(nt)

# consider primes less than the maximum two-digit total
primes = tuple(Primes(485))

# consider the sums of two adjacent primes
for i in range(len(primes) - 1):
  p1, p2 = primes[i], primes[i + 1]
  t = p1 + p2

  # check that the total of two adjacent primes is in the set of
  # sums of five consecutive numbers and has three prime factors
  if t in nt_set and len(list(factors(t))) == 3:
    print('Number of crenels = ', t)
    print('Adjacent prime numbers = ', p1, p2)
    print('Three prime factors = ', list(factors(t)))

from number_theory import Primes, factors

# minimum total for five consecutive 2-digit numbers = 10 + 11 + 12 + 13 + 14 = 60

# maximum total for five consecutive 2-digit numbers = 95 + 96 + 97 + 98 + 99 = 485

# form a set holding the totals of five consecutive numbers

nt_set = set()

for n in range(10, 96):

nt = n + (n + 1) + (n + 2) + (n + 3) + (n + 4)

nt_set.add(nt)

# consider primes less than the maximum two-digit total

primes = tuple(Primes(485))

# consider the sums of two adjacent primes

for i in range(len(primes) - 1):

p1, p2 = primes[i], primes[i + 1]

t = p1 + p2

# check that the total of two adjacent primes is in the set of

# sums of five consecutive numbers and has three prime factors

if t in nt_set and len(list(factors(t))) == 3:

print('Number of crenels = ', t)

print('Adjacent prime numbers = ', p1, p2)

print('Three prime factors = ', list(factors(t)))

geoffrounce permalink

The only unknowns in this teaser so far are the five consecutive 2-digit numbers.

If 5n + 10 = 410, then n = 80.

The five consecutive 2-digit numbers, therefore, are 80, 81, 82, 83 and 84.

Reply

Trevor Kirsten permalink

I used simple prime no. generators to solve from scratch.
It would be appreciated if anyone could shorten or make it more efficient.


# (i)   t = p1 + p2 (consecutive primes, :. t is even)
# (ii)  t = 5(n + 2) (n is even, 10 <= n <= 94, 60 <= t <= 480)
# (iii) t = 2 * 5 * x (x is prime, 7 <= x <= 47)

for x in range(7, 48, 2):                # this does (iii)
  for y in range(3, int(x ** .5 + 1), 2):
    if x % y == 0:
      break
  else:
      t = 10 * x
      
      c = [7]                            # this does (i)
      for a in range(11, int(t / 2) + 10, 2):
        for b in range(3, int((t / 2 + 10) ** .5 + 1), 2):
          if a % b == 0:
            break
        else:
          c += [a]
          p= c[-2] + c[-1]
          if p == t:
            print(t)

# (i) t = p1 + p2 (consecutive primes, :. t is even)

# (ii) t = 5(n + 2) (n is even, 10 <= n <= 94, 60 <= t <= 480)

# (iii) t = 2 * 5 * x (x is prime, 7 <= x <= 47)

for x in range(7, 48, 2): # this does (iii)

for y in range(3, int(x ** .5 + 1), 2):

if x % y == 0:

break

else:

t = 10 * x

c = [7] # this does (i)

for a in range(11, int(t / 2) + 10, 2):

for b in range(3, int((t / 2 + 10) ** .5 + 1), 2):

if a % b == 0:

break

else:

c += [a]

p= c[-2] + c[-1]

if p == t:

print(t)

It runs pretty fast (less than a millisecond).

Sunday Times Teaser 2841 – Crenellation Aggregation

by Stephen Hogg

Published 5th March 2017 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta