Teaser 3223: Shaping up
From The Sunday Times, 30th June 2024 [link] [link]
Clark wondered how many different shapes he could draw with identical squares joined edge to edge and each shape containing the same number of squares. He only drew five different shapes containing four squares, for example, because he ignored rotations and reflections:
He drew all of the different shapes containing 1, 2, 3, 4, 5 and 6 squares and wrote down the total number of different shapes in each case. He took the six totals in some order, without reordering the digits within any total, and placed them end to end to form a sequence of digits which could also be formed by placing six prime numbers end to end.
In ascending order, what were the six prime numbers?
[teaser3223]
S2T2 
Jim Randell 4:53 pm on 28 June 2024 Permalink |
This is fairly straightforward, if you know how many free n-polyominoes there are of the required sizes. [@wikipedia]
This Python program runs in 70ms. (Internal runtime is 4.1ms).
from enigma import (irange, primes, subsets, concat, uniq, ordered, printf) # number of n-polyominoes (n = 1..6) [see: OEIS A000105] ns = [1, 1, 2, 5, 12, 35] # can we split a string into k primes? def solve(s, k, ps=list()): if k == 1: p = int(s) if p in primes: yield ps + [p] elif k > 0: for n in irange(1, len(s) + 1 - k): p = int(s[:n]) if p in primes: yield from solve(s[n:], k - 1, ps + [p]) # collect answers (ordered sequence of primes) ans = set() # consider possible concatenated sequences for s in uniq(subsets(ns, size=len, select='P', fn=concat)): # can we split it into 6 primes? for ps in solve(s, 6): ss = ordered(*ps) printf("[{s} -> {ps} -> {ss}]") ans.add(ss) # output solution(s) for ss in sorted(ans): printf("answer = {ss}")Solution: The 6 prime numbers are: 2, 2, 5, 5, 11, 13.
(Although note that they are not 6 different prime numbers).
The number of free n-polyominoes for n = 1..6 is:
(i.e. there is only 1 free monomino, going up to 35 free hexominoes).
And we don’t have to worry about polyominoes with holes, as they don’t appear until we reach septominoes (7-ominoes).
We can order these numbers as follows:
and this string of digits can be split into 6 prime numbers as follows:
In fact, we can order the numbers into 24 different strings of digits that can be split into primes, but they all yield the same collection of primes.
LikeLike