# Archive for December, 2008

## 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 = 2.3.5.7.17.19 and 98670 = 2.3.5.11.13.23,
82110 = 2.3.5.7.17.23 and 81510 = 2.3.5.11.13.19,
91170 = 2.3.5.7.19.23 and 72930 = 2.3.5.11.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.

## 4009 – Three Rings by Franc

Posted by Listen With Others on 13 December 2008

by Shirley Curran

Monday: We can cope, on a good day, with AZED. The Speccie, Grauniad and co. are our regulars, but we aren’t in the Listener League – we follow the impenetrable discussions with awe. Still, I set straightforward circular ones, so this circular grid looks tempting – we can always write a mini blog for LWO about the desperate floundering of complete beginners.

Three Rings – that looks hopeful – a circus. The inventor? Barnum – Phineas Taylor Barnum – forty letters in the venue of his début THE SCUDDER MUSEUM NEW YORK CITY – brilliant. We’ll work on that – has to be his last two names in the inner circle. A few easy clues in circle two confirm that we’re on the right track – ACROBAT, CLOWN, FIRE-EATER – but we’re stuck there, can’t see any jugglers or trapeze artists and we don’t know what order to put them in. (Animals appeared for us on Tuesday, and even then, we were struggling with the fact that some were plural and some singular – we thought the poor lonely monkey was perhaps a King in ‘moneys!)

Delighted with ourselves, we solve a dozen radials and, after a bit of a quandary over what the ‘jumble’ means we complete some blocks of four. Why the quandary? ORANGE clearly goes inwards and ONAGER is the jumble but it is also an anagram of orange and all the words we have so far found (except CHORAL) have possible anagrams – so are we looking for anagrams? We decide not, but clearly we need those rings to tell us which way to feed our words in. We’re on the point of abandoning.

Tuesday: A few desultory, frustrated dabbles and more breakthroughs – the fourth circle begins to yield – FRATELLINI, MAJOR, …

Then disaster! The LE we have in two consecutive centre slots precludes Barnum and even Bailey won’t fit with what we have further round. So we set off on our second wild goose chase. Philip Astley is the British circus inventor – 12 letters – great! We produce about half the radials but they are still a list at the side of the page. How do we slot them in?

The JESTER (35) clears the way for us. His J in the second circle has to intersect with JUMBO (yes, we got the dumbo clue – not surprisingly!) and, at last we’re in business. Ring two is almost complete BUT Philip Astley is a no no. It’s the ULE in the inner circle that leads us to try JULES on the Internet and hey presto, we have LEOTARD and THE CIRQUE NAPOLEON IN PARIS. (Shouldn’t we have seen that at once? – We do live in France!) The rest is a matter of fitting it all together.

It isn’t all plain sailing. By Tuesday evening we are left with six radials to complete and a confusing space in our circus families – who are these ?CON??LLOS? We stay up late juggling letters until we have a single letter space to complete and one last impenetrable clue – and do we put OOLITE or OOLITH in our jumble?

Conclusion – if we managed, it must have been far easier than usual but we did enjoy it. Now we understand rumours that teams of people work together. And it’s back to the Sun Junior Coffee Break 8 by 8 for us.

shirleycurran@orange.fr