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.