4010 – Euclid’s Algorithm by Aedites – Setter’s Blog
Posted by Listen With Others on 19 December 2008
After I constructed my first puzzle Special Agent’s Cipher over Christmas 1997 (which was published as number 3567 and has been included in the recent collection of Listener puzzles), I thought that it would be interesting to construct a numerical puzzle using a circular grid, and a month later I constructed the first version of Euclid’s Algorithm.
One property of a circular grid is that the cells in the inner circles intersect with more than one radial entry, and thus the clues could relate to each intersecting pair of entries. As a mathematician I tend to think of the integers in terms of their prime factorisations, so a natural function to consider is the “highest common factor”, and to make things simple entries could be restricted to integers with no repeated factors. After a little experimentation I came up with a five-ring grid using 40 radial entries with the nice property that there were 26 five-long circular entries, which could be labelled by the letters of the alphabet, and the clues could be the highest common factors. This would give a nice “inverse” problem: whereas it is easy to compute the highest common factor of two integers using Euclid’s algorithm, it would be relatively hard to reconstruct the set of original integers with only fragments of information on their factors.
The next problem was the entry point. There are 20 five-digit decimal numbers with six distinct factors, but only one five-digit octal number, 72516, or 30030 in decimal, so I decided to complete the puzzle in octal. I placed this number in one of the radial entries and arranged for the five intersecting circular entries to include the first six primes so that it could be recovered easily. I was able to complete the grid using only numbers constructed from the first 20 primes, and I could arrange that about 70% of the intersecting entries had at least one factor in common and that all the primes occurred at least once, so that there was a reasonable solution path. This grid is shown below.
I submitted this puzzle to the Listener Crossword, and in due course the first editor replied that he had enjoyed solving it, but that the large number of decimal-octal conversions needed would be very tedious for a solver without a scientific calculator. Thus it was not really suitable for publication in its current form.
I therefore produced a second version using decimal entries in April 2003. This meant that I needed to construct a more complicated entry point. An obvious solution was to have two intersecting entries, both of which had six factors. If attention is restricted to pairs with exactly three factors in common, there are three possible pairs:
67830 = 188.8.131.52.17.19 and 98670 = 184.108.40.206.13.23,
82110 = 220.127.116.11.17.23 and 81510 = 18.104.22.168.13.19,
91170 = 22.214.171.124.19.23 and 72930 = 126.96.36.199.13.17.
If one of the members of a pair is placed in the inner ring, then each cell intersects with four radial entries. Suppose a, b and c represent the primes 2, 3 and 5. If the cell contains an even digit, then “a” must occur in all four clues, and not at all if the digit is odd. Similarly if the cell contains a 5 or 0, all four clues must contain “c”. In contrast “b” representing 3 will occur at random in the clues. Of the six possible entries only 81510 contains the digit 5 so this was placed in an entry in the inner ring, and 82110 was placed in an intersecting radial entry. With the restriction of factors to the first 20 primes, there are 2489 five-digit integers (2.8% of the total) without repeated factors. I was unable to construct a satisfactory grid using just these and had to include 79 as a factor in one of the radial entries.
John Grimshaw had written to me about my previous puzzle 3567 mainly because The Times had omitted the down clues, which gave solvers an interesting challenge; the down clues were published a week later! As in this puzzle, the clues were factorisations and one of his comments was that, if the solver counted the occurrences of the different letters in the clues and wrote the letters down in decreasing order of frequency, these were likely to correspond closely with the primes written in the natural order. To avoid this short cut to the solution, only a third of the entries in this puzzle are even, and I avoided numbers divisible by 3 wherever possible. Instead I looked for entries which contained large factors (using numbers with only three factors), intending that all the primes should occur in at least one clue. I was able to achieve a grid where all but two of the primes used in the puzzle occurred in the clues. The table below, which counts the frequency of occurrence of each prime in the 66 entries and in the 200 clues, shows that a solver can make no obvious deductions from the latter list of counts.