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.
Assuming that the proof (after your explanation I am certainly not going to try reading it) shows that there is at least one set of three palindromic numbers that sum to any given n, then it would be a safe bet to assume that there may be more than one set in some cases.
This makes me think that there is a new sequence for OEIS to be created where P(n) is the number of distinct sets of three palindromic numbers that add up to n.
For example
100 = 99 + 1 + 0
100 = 88 + 11 + 1.
100 = 77 + 22 + 1
100 = 66 + 33 + 1
100 = 55 + 44 + 1
P(100) = 5?
The result has been extended to bases 3 and 4 (although without an algorithm, unless someone has produced one since). It is not true in base 2 – that sometimes requires 4 palindromes.
Paper at https://arxiv.org/pdf/1706.10206.pdf , one of the authors posted about it at http://recursed.blogspot.co.uk/2017/07/using-decision-method-to-prove-new.html , I found out about it in the first place from https://mathlesstraveled.com/2018/04/11/more-on-sums-of-palindromes/
Cool! Thanks for that. I subscribe to The Math Less Traveled, so I must have missed that post.
Why is it only after one has posted that one sees the typo? It should of course read 100 = 99 + 1 + 0
Paul’s sequence is already there, as A261132. 100 actually has 9 representations: 55+44+1, 66+33+1, 77+22+1, 88+11+1, 88+6+6, 88+7+5, 88+8_4, 88+9+3, 99+1+0
Well spotted John. Another chance for fame crushed. I might have guessed it would be Mr. Resta that got there first :-)
I am afraid your tool has a bug, with 207468 it does not work as it should: it gives out 207468 = 200002+ (-1969-1)+7777. Or else, we have a different understanding of a palindrome number is.
Whoops! You’re right, there was a bug. And that meant there was a bug in my testing code, because I thought I’d checked every number up to 7 digits! Should be fixed now.
Really nice blog post! I am having a go at implementing the algorithm too.
There are two different ways of doing 2023: 1881+131+11 (your way and the paper’s Lemma 4.4iii), or 1881+141+1 (the paper’s authors’ website’s way, which does not seem to follow the published algorithm).
Ivan
Same with 2100: pal3algo returns 1991+101+8, you return 1881+131+88.
My applet now matches the paper for those cases that Ivan noticed.
Thanks :) Sorry to be pedantic. I’m really enjoying working (slowly) through your paper.
AMAZING! Would you mind if I made a translation your palindromic hat-trick page (in portuguese) available? Of course credits and links in the page would be preserved and point to you and your website. Great fun!!
Go ahead!
Hi Christian: What a rare treat!!! I am not mathematician (although I love math) but a palindrome fan. I am interested in all types of palindromes, letter-unit and word-unit palindromes, line-unit poems, abbreviation palindromes, musical palindromes, palindromic squares, palindromic DNA sequences, and, would you believe it, palindromic bingo, and of course, number palindromes. I share my findings with my daughter and my twin granddaughters. I used your hat trick for their birthday dates of and I can’t wait to show it to them at supper time. It is AMAZING!!! Thanks a million!
Absolutely lovely.