You're reading: cp's mathem-o-blog

The incredible palindromic hat-trick

Would you like to see something AMAZING?

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.

INCREDIBLE!

14 Responses to “The incredible palindromic hat-trick”

  1. Paul Coombes

    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?

    Reply
  2. Paul Coombes

    Why is it only after one has posted that one sees the typo? It should of course read 100 = 99 + 1 + 0

    Reply
  3. John

    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

    Reply
    • Paul Coombes

      Well spotted John. Another chance for fame crushed. I might have guessed it would be Mr. Resta that got there first :-)

      Reply
  4. Emiliano Brunetti

    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.

    Reply
    • Christian Lawson-Perfect

      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.

      Reply
  5. Ivan

    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

    Reply
  6. Tássio Naia

    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!!

    Reply

Leave a Reply to Paul Coombes

  • (will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Google+