The incredible palindromic hat-trick

I’ve made another one of my interactive online maths doodads. You should have a go at it right now. It doesn’t require any effort on your part, other than coming up with a positive integer.

Isn’t that incredible?

The trick is based on the paper “Every positive integer is a sum of three palindromes” by Javier Cilleruelo, Florian Luca and Lewis Baxter. That’s a superb fact, and one that was very hard to prove. And the authors didn’t just do it in base 10: they show that it’s true for any base from 5 upwards.

Cor!

So obviously, when I discovered this theorem, I had to try it out for myself, and I immediately thought it would make a great interactive toy. The problem is that the paper is forbiddingly complicated. As easy as the theorem statement is to understand, the proof is fiddly in equal measure.

This proof by cases goes four levels deep, and then has the audacity to throw in a couple of extra decisions. The impertinence!

The proof consists of an algorithm which takes any positive integer, and is shown to produce three palindromes which sum to that integer. For numbers 7 digits or larger, the algorithm’s moderately straightforward. However, for smaller numbers, it’s a horrendous proof by cases that really tested my motivation to see the whole thing through.

It took me a couple of days of snatched time between work and parenting duties to implement the whole algorithm in JavaScript, and then another night and a shower before I tracked down the missing case in Algorithm I.3 ($\delta_{m-1}=0$ is allowed, and I’m going to stick by that!).

While in the depths of will-it-ever-work despair, I found out that one of the co-authors, Lewis Baxter, has put online a page that performs the trick for you, just like I was intending to do. That was very helpful when I was trying to work out whether I or the paper had gone wrong, but three days in I was in no mood to quit. So I didn’t quit, and finally it looked like I’d implemented the algorithm correctly.

Now, proofs that claim to work for all $n$ are well and good, but I wanted to check at least the “small numbers” that had such fiddly solutions. So, I set my computer off running the algorithm on every number up to 1000000, and on a few hundred thousand randomly-chosen larger ones.

And it worked!

I decided this incredible theorem deserves a hype man, so everyone knows just how mind-blowingly cool it is. I spiffed up my web interface with bright colours, a lot of patter, and an ostentatious amount of whizzy text. A moron in a hurry will be in no doubt that this is a very cool result.

Try the incredible palindromic hat-trick now.

I hope I didn’t overdo it with the whizzy text.