Sunday Times Teaser 3149 – Cube Route
by Andrew Skidmore
Published Sunday January 29 2023 (link)
I have a set of ten cards, each of which has a different digit written on it. All the cards have been used to make a set of prime numbers. After discarding the smallest prime, and without changing the order of any cards, I have placed the remaining primes in order of decreasing size to give a large number. It is possible, without changing the order of any cards, to break this number into a set composed entirely of cubes. Neither set contains a number with more than four digits.
List, in order of decreasing size, my set of prime numbers.
8 Comments
Leave one →
Here is a version that tackles the primes first:
This runs in about 300ms. But tackling the cubes first is much faster, running in less than 30ms on my PC:
I believe a worthwhile speed improvement can be attained by removing the variable ‘n2d’ from the functions ‘compose’, ‘cube_seq’ and ‘prime_seq’ as it is an external variable and is passed unchanged from initial call through all recursions levels. In addition, it is quite a large data structure.
remove from the arguments, not completely of course
slow but compact
Line 30 can be written more efficiently as:
Walrus notation could also be used to good effect in some places to avoid recalculations.
My take on tackling the cubes first:
The above runs in 500 microseconds on my system (solution found after 80 microseconds) using:
etc.
A slighty more compact cubes first version; but is it faster?