Teaser 2690: Leaving present
From The Sunday Times, 13th April 2014 [link]
When maths teacher Adam Up reached the age of 65, he asked his colleagues for some spring bulbs as a leaving present. So they gave him some packs of bulbs with, appropriately enough, each pack containing 65 bulbs.
Adam planted all the bulbs in clumps of different sizes, the number of bulbs in each clump being a prime number. Furthermore, these prime numbers overall used each of the ten digits exactly once. Had he been given any fewer packs this would have been impossible.
How many bulbs were there in the smallest and largest clumps?
[teaser2690]
GeoffR and 
Hugh Casement and 
Frits and 
John Crabtree, 
S2T2 
Jim Randell 10:42 am on 6 December 2022 Permalink |
I implemented a multiset exact cover algorithm [[
mcover()]] when I revisited Enigma 1712. And the same function can be used to solve this puzzle.As we are looking for the smallest number of packs we can start by considering primes up to 65, to see if the problem can be solved using a single pack, and if not we can then add primes between 66 and 130 into the mix, and so on until we find a number of packs that provides solutions.
The following Python program runs in 56ms. (Internal run time is 3.7ms).
Run: [ @replit ]
from enigma import (irange, primes, inf, nsplit, multiset, mcover, printf) # incremental multiple N = 65 # target digit contents (each digit once) tgt = multiset.from_seq(irange(0, 9), count=1) # start with 0 multiples k = 0 m = dict() # map primes to digit content for p in primes.irange(2, inf): # have we finished a chunk? k_ = p // N if k_ > k: k = k_ kN = k * N # look for covers using this collection of primes n = 0 for ss in mcover(m, tgt, (lambda ss: sum(ss) > kN)): # check for required sum if sum(ss) == kN: # output solution printf("{ss} -> {k} * {N}", ss=sorted(ss)) n += 1 # are we done? if n > 0: printf("[{n} solutions]") break # add primes that are subsets of the target into the list ds = multiset.from_seq(nsplit(p)) if ds.issubset(tgt): m[p] = dsSolution: The smallest clump had 5 bulbs. The largest clump had 401 bulbs.
There are 2 ways to achieve the solution with 9 packs of 65 bulbs (= 585 bulbs in total):
LikeLike
GeoffR 7:02 pm on 6 December 2022 Permalink |
The only way I could find a solution in MiniZinc was to assume the ten digit pattern of the primes i.e. 1,2,2,2,3. There has to be at least one 3-digit prime with zero as the middle digit.
% A Solution in MiniZinc include "globals.mzn"; % Using a 1,2,2,2,3 digit prime pattern var 1..9:A; var 1..9:B; var 1..9:C; var 1..9:D; var 1..9:E; var 1..9:F; var 1..9:G; var 1..9:H; var 0..9:I; var 1..9:J; var 10..99:BC = 10*B + C; var 10..99:DE = 10*D + E; var 10..99:FG = 10*F + G; var 100..999:HIJ = 100*H + 10*I + J; predicate is_prime(var int: x) = x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) ((i < x) -> (x mod i > 0)); constraint sum([is_prime(A), is_prime(BC), is_prime(DE), is_prime(FG), is_prime(HIJ)]) == 5; constraint card( {A,B,C,D,E,F,G,H,I,J}) == 10; % There are 65 bulbs in each pack constraint (A + BC + DE + FG + HIJ) mod 65 == 0; constraint increasing([A,BC,DE,FG,HIJ]); solve satisfy; output ["Smallest clump = " ++ show(A) ++ " , Largest clump = " ++ show(HIJ) ++ "\n" ++ "[A,BC,DE,FG,HIJ] = " ++ show([A,BC,DE,FG,HIJ] )]; % Smallest clump = 5 , Largest clump = 401 % [A,BC,DE,FG,HIJ] = [5, 29, 67, 83, 401] % ---------- % Smallest clump = 5 , Largest clump = 401 % [A,BC,DE,FG,HIJ] = [5, 23, 67, 89, 401] % ---------- % ==========Out of interest I then adapted the program to check a different prime digit pattern, which was 2,2,3,3 for the ten digits. All the answers used 18 packs of 65 bulbs, exactly double the original solution using 9 packs of 65 bulbs = 585
LikeLike