New Scientist: Enigma 45

This is the item published in the New Scientist #2853 Feedback section about my solution to Enigma Puzzle 45.

It only took 32 years to solve Enigma No 45. The version of the weekly New Scientist puzzle that was set in the issue of 3 January 1980 - a problem in linear algebra - was, it seemed, too difficult even for New Scientist's notoriously clever readers. The deadline for responses passed and, two weeks later on 17 January, Enigma's editor announced: "No correct solutions were received for Enigma No 45."

And that's how things stood until December 2011, when Jim Randell emailed New Scientist to say: "I was browsing through Google Books and I came across Enigma 45..." He promptly had a go at the puzzle himself and found "a solution that satisfies the conditions".

"What I'd like to know," said Jim, "is whether mine is the first correct solution you've received for this puzzle - albeit almost 32 years late."
We forwarded Jim's email on to the mathematical genius who regularly checks readers' solutions for Enigma puzzles.

He said that Jim had indeed got the answer right, and added that he had used "a reasonably straightforward computer program" to do the checking. "Presumably the reason no one got this answer 32 years ago," he surmised, "was because of the lack of computers then."

Our congratulations go to Jim Randell, who will be awarded an Enigma prize - at the 2012 rate, not the 1980 one. His solution to the puzzle is published in this week's Enigma on page 35.

And on page 35:

Answer to 45 Six squares - harder: P=434657, Q=420968, R=150568
The winner Jim Randell of Bristol, UK

Retrocomputing Enigma 45

A few months ago I launched Enigmatic Code - a place to post programmatic solutions to New Scientist's Enigma Puzzles.

As well as solving contemporary puzzles I found that Google Books has archives of back issues of New Scientist dating back to the 70's and 80's, and in my search for early Enigma puzzles I came across Enigma 45: Six squares - harder. Which involves finding non-negative integers P, Q, R such that P+Q, P+R, Q+R, P-Q, P-R and Q-R are all perfect squares.

After a couple of false starts - the solution clearly wasn't as small as I'd hoped - I came up with an algorithm to attack the problem in a reasonable amount of time.

However, when I checked my solution against the one published in the following issue of New Scientist I saw that the answer I had got wasn't the same as the solution they were expecting. But we had been asked to minimise the sum P+Q+R and my answer had a smaller sum than the published solution.

Curiously in New Scientist #1190 it is noted that no correct entries were received for this puzzle. "Shame on you!", they said. So I sent an email with my solution to ask if I was the first correct entry, albeit 32 years too late.

In the current issue of New Scientist (#2853) they published a short item in the Feedback section about this story, and they have awarded me a £15 prize for solving the puzzle!

If you're thinking it's a little unfair to unleash 2011 computing power on a 1980's problem, I decided to put a more contemporary machine up to the challenge. The BBC Micro was launched at the end of 1981 (although I don't think I would have been using them until probably '82 or '83), and I did quite a lot of programming on them at school, so I stood a fair chance of being able to get a program together to attack the problem.

So, I downloaded BeebEm3, and managed to get a BBC BASIC program together to solve the problem. The hardest part was trying to input the program, as the keymap of the emulator doesn't match the layout of my laptop keyboard. Nevertheless I managed to get my program typed in and running. (See image above).

It took about 40 minutes to run, and the Emulator said it was running at a speed of around 17, which I'm assuming means it's running at 17x the speed of a real BBC Micro. If so, that would mean that a contemporary-ish home computer could have solved the problem in under 12 hours (in BASIC!). Admittedly it's not up to the 255ms runtime of my present day Python solution, but it would be a bit of a poor reflection on 32 years of computing development if it was. (Note: I found that the TIME command reports the elapsed time as it would be on a real machine (presumably it's derived directly from the CPU clock), so I augmented the program to report elapsed timing and it seems the program would take 5h2m to find the smallest solution and and additional 2h17m to find the published solution on an actual BBC Micro).

Note: It turns out this problem was posed by Italian mathematician Pietro Mengoli in 1674, and the smallest solution was discovered by Euler a century later, probably without the benefit of even a BBC Micro.

Note: I've now received my physical copy of New Scientist #2853 and I've reproduced the article (and the illustration) on my own blog: New Scientist: Enigma 45.