Teaser 3037: Prime advent calendar
From The Sunday Times, 6th December 2020 [link] [link]
Last year I was given a mathematical Advent calendar with 24 doors arranged in four rows and six columns, and I opened one door each day, starting on December 1. Behind each door is an illustrated prime number, and the numbers increase each day. The numbers have been arranged so that once all the doors have been opened, the sum of the numbers in each row is the same, and likewise for the six columns. Given the above, the sum of all the prime numbers is as small as it can be.
On the 24th, I opened the last door to find the number 107.
In order, what numbers did I find on the 20th, 21st, 22nd and 23rd?
[teaser3037]
Jim Randell 6:52 pm on 4 December 2020 Permalink |
I think this is the first Teaser in quite a while that has taken me more than a few minutes to solve. Fortunately all the numbers we are dealing with are different, so that simplifies things a bit.
My original program [link] was shorter, but less efficient (it runs in 3.4s). The following Python 3 program is longer, but runs in only 81ms.
Run: [ @repl.it ]
Solution: The numbers on the 20th, 21st, 22nd, 23rd were: 73, 79, 83, 101.
One possible layout is shown below, but there are many others:
Each row sums to 270. Each column sums to 180. Altogether the numbers sum to 1080.
I let my program look for solutions with a higher sum, and it is possible to construct a calendar for every set of primes whose sum is a multiple of 24.
LikeLike
Frits 12:02 pm on 5 December 2020 Permalink |
@Jim, you can also remove 2 from primes (as column sum needs to be even (row sum, 1.5 * column sum, must be a whole number) and there is only 1 even prime in primes).
With this, your first reported T,R,C combination can be discarded as R may not be odd (sum of 6 odd numbers is even).
I also have the same first solution but it takes a long time (mainly in checking column sums).
I first tried a program with SubstitutedExpression but I had problems with that.
LikeLike
Jim Randell 5:18 pm on 5 December 2020 Permalink |
@Frits: Thanks. I realised that 2 wasn’t going to be involved in final grid. But if you exclude it at the start, and only allow even row and column sums, then the runtime of my program goes down to 58ms. (And the internal runtime is down to 14ms).
LikeLike
Frits 8:17 pm on 5 December 2020 Permalink |
@Jim,
A further improvement could be to skip checking subsets (line 45) when testing sum 1080 as the number of primes to be used is fixed.
Sum of primes from 3 to 107 is 1369 (for 27 primes)
1369 – 1080 = 289 which can only be formed by 3 primes with (89, 97 and 103 ).
The 24 remaining primes can be used to do the rows and cols logic.
LikeLike
Jim Randell 10:15 pm on 5 December 2020 Permalink |
@Frits: I’m not sure I understand. In my program the sets of primes are tackled in sum order (to ensure we find the set with the lowest sum), so only one set of primes with sum 1080 will be checked (as there is only one set that sums to 1080).
LikeLike
Frits 11:46 pm on 5 December 2020 Permalink |
You can analyze that 1080 is the first sum to check (sum has to be a multiple of 24).
So you don’t need to execute line 45 if you first have a separate check for 1080 (with the 24 primes) and you do find an answer for it.
The disadvantage is that it will make the code less concise.
LikeLike
Frits 11:51 pm on 5 December 2020 Permalink |
Meaning:
LikeLike
Frits 10:17 am on 6 December 2020 Permalink |
A little bit different and less efficient.
LikeLike
Jim Randell 2:30 pm on 6 December 2020 Permalink |
@Frits: I don’t think you want to use a
set()
at line 70. Theset()
will remove duplicates, but you are not guaranteed to get the numbers out in increasing order. In this case we know that there are no duplicates, and we definitely want to consider the numbers in increasing order (so we can be sure we have found the smallest).Changing the brackets to () or [] will do, but I think there are clearer ways to write the loop.
LikeLike
Frits 7:18 pm on 6 December 2020 Permalink |
@Jim. Thanks.
I normally run python programs with PyPy and PyPy preserves the order of dictionaries and sets.
Running with Python solved the sum 1152 and not for 1080.
LikeLike
Jim Randell 11:10 am on 7 December 2020 Permalink |
@Frits: OK. I knew about the PyPy’s behaviour for
dict()
, but not forset()
.FWIW: I try to post code that runs on as wide a variety of Pythons as possible. I currently check against CPython 2.7.18 and 3.9.0 (although sometimes I use features that only became available in Python 3).
LikeLike
GeoffR 10:43 am on 7 December 2020 Permalink |
I found a solution in MiniZinc, but the run time was very slow (just over 5 min)
LikeLike
Frits 1:33 pm on 8 December 2020 Permalink |
Finding a solution takes less than a second.
I used the fact that psum has to be a multiple of 24 and has a minimum/maximum of 1080/1344.
Biggest time gain seems to have come from replacing the psum definition from the sum of 24 variables to 6 times the sum of 4 variables.
LikeLike
GeoffR 9:48 pm on 8 December 2020 Permalink |
Thanks to Frits for his optimisation of my code to make it run a lot faster.
I have added an explanation of the range calculation for psum ie 1080..1344.
I also found I could tidy code further by just using psum mod24 == 0. It was not necessary to use a list of prime sums in this revised code. It ran in about 0.6 sec.
LikeLike
Frits 1:48 pm on 8 December 2020 Permalink |
Another program using many nested loops.
LikeLike
GeoffR 7:41 pm on 8 December 2020 Permalink |
I get an error on the Idle and Wing IDE’s when I try to run this code:
i.e Syntax Error: too many statically nested blocks
Is there an easy fix?
LikeLike
Jim Randell 7:59 pm on 8 December 2020 Permalink |
@Geoff: There is a limit of 20 nested loops in the standard Python interpreter. But the PyPy interpreter doesn’t have this limit, so you can use it to execute code with lots of nested loops.
LikeLike