Or 317:<\/p>\n
- \n
- 317 reversed is 713. <\/li>\n
- 317+713=1030.<\/li>\n
- 1030 reversed is 301.<\/li>\n
- 1030 + 301 = 1331, so we have a palindromic number after two steps.<\/li>\n<\/ol>\n
You can play the same game in different number bases. For example, in base 8, we can start with 013 (11 in base-10): in one reverse+add, it becomes 44 (36 in base-10).<\/p>\n
For most numbers, you get a palindrome in just a few steps. But for some numbers, in some number bases, you don’t. If you can’t ever get to a palindrome by doing reverse+add starting from a number, then that number is called a Lychrel number<\/em>.<\/em><\/p>\n
The process of exploring Lychrel numbers has picked up a lot of devotees, who’ve developed a whole language for talking about it:<\/p>\n
- \n
- chain<\/dt>\n
- A chain<\/em> is the sequence of numbers produced by reverse+add starting with some number, and possibly converging on a palindromic number.<\/dd>\n
- seed<\/dt>\n
- The seed<\/em> of a chain is the smallest number that can start that chain. For example, in the example above, we looked at the chain [217, 1030, 1331]. 217 is the seed – even though you could start a chain at 1030, 1030 would never be considered a seed, because it can be the product of a reverse+add on a smaller number.<\/dd>\n
- kin<\/dt>\n
- Two numbers are kin numbers<\/em> if they’re part of a chain that started at the same seed. If a number is a lychrel number, then (obviously) so are all of its kin.<\/dd>\n<\/dl>\n
The question that haunts Lychrel enthusiasts is, will you always<\/em> eventually get a palindrome? That is, do Lychrel numbers actually exist?<\/p>\n
In base-2, we know the answer to that: not all numbers will produce a palindrome; there are base-2 Lychrel numbers. The smallest base-22 Lychrel number is 22 – or 10110 in binary. We can look at its reverse add sequence, and see intuitively why it will never produce a palindrome:<\/p>\n
- \n
- 10110<\/li>\n
- 100011<\/li>\n
- 1010100<\/li>\n
- 1101001<\/li>\n
- 10110100 (10, 11, 01, 00)<\/li>\n
- 11100001<\/li>\n
- 101101000<\/li>\n
- 110010101<\/li>\n
- 1011101000 (10, 111, 01, 000)<\/li>\n
- 110010101<\/li>\n
- 1101000101<\/li>\n
- 10111010000<\/li>\n
- 0b11000101101<\/li>\n
- 0b101111010000 (10, 1111, 01, 0000)<\/li>\n<\/ol>\n
Starting at step 5, we start seeing a pattern in the sequence, where we have recurring values where that have a pattern of 10, followed by
-1s, followed by 01, followed by
We can find similar sequences in any power-of-two base – base 4, 8, 16, etc. So in power-of-two bases, there are Lychrel numbers. But: are there Lychrel numbers in our familiar base-10?<\/p>\n
We think so, but we’re not sure. No one has been able to prove it either way. But we’ve got some numbers, which we call Lychrel candidates<\/em>, that we think<\/em> are probably Lychcrel numbers. The smallest one is 196 – which is why this whole discussion is sometimes called the 196 problem, or the 196 algorithm.<\/p>\n
People have written programs that follow the Lychrel thread from 196, trying to see if it reaches a palindrome. So far, the record for exploring the 196 Lychrel thread carries it through more than a billion iterations, producing a non-palindromic number with more than 6 million digits.<\/p>\n
That’s pretty impressive, given that the longest Lychrel thread for any number smaller than 196 is the thread of 24 steps, starting with 89 (which produces the palindromic number 8,813,200,023,188).<\/p>\n
From my perspective, one thing that interests me about this is its nature as a computational problem. As a problem, it’s really easy to implement. For example, here’s a complete implementation in Ratchet, a Scheme-based programming language. (I used ratchet because it features infinite-precision integers, which makes it easier to write.)<\/p>\n
\n(define (reverse-number n)\n (string->number (list->string (reverse (string->list (number->string n))))))\n\n(define (palindromic? n)\n (equal? n (reverse-number n)))\n\n(define (reverse-add n)\n (+ n (reverse-number n)))\n\n(define (find-palindrome seed)\n (define (noisy-find-palindrome n count)\n (if (palindromic? n)\n n\n (begin\n (printf \"At iteration ~v, candidate=~v~n\" count n)\n (noisy-find-palindrome (reverse-add n) (+ count 1)))))\n (noisy-find-palindrome seed 0))\n<\/pre>\n
I literally threw that together in less than five minutes. In that sense, this is a really, really easy problem to solve. But in another sense, it’s a very hard problem: there’s no way to really speed it up.<\/p>\n
In modern computing, when we look at a problem that takes a lot of computation to solve, the way that we generally try to approach it is to throw more CPUs at it, and do it in parallel. For most problems that we come across, we can find some reasonable way to divide it into parts that can be run at the same time; then by having a bunch of computers work on those different parts, we can get a solution pretty quickly.<\/p>\n
For example, back in the early days of this blog, I did some writing about the Mandelbrot set, and one variant of it that I find particularly interesting, called the Buddhabrot. The Buddhabrot is interesting because it’s a fractal visualization which isn’t naively zoomable. In a typical Mandelbrot set visualization, you can pick a small region of it that you want to see in more detail, and focus your computation on just that part, to get a zoomed in view on that. In the Buddhabrot, due to the chaotic nature of the computation, you can’t<\/em>. So you just compute the Buddhabrot at a massive size, and then you compress<\/em> it. When you want to see a region in more detail, you un-compress. To make that work, buddhabrot’s are frequently computed at resolutions like 1 million by 1 million pixels. That translates to enough complex floating point computations to compute several trillion values. That’s a big task. But in modern environments, that’s routine enough that a friend of mine at Google wrote a program, just for kicks, to compute a big buddhabrot image, and ran it on an experimental cluster.<\/p>\n
If that kind of computational capability can be exploited just for kicks, why is it that the best effort at exploring the Lychrel thread for 196 only covers 6 million digits?<\/p>\n
The answer is that there’s a way of computing the Buddhabrot in parallel. You can throw 10,000 CPUs at it for a couple of days, and get an amazing Buddhabrot image. But for the Lychrel thread, there’s no good way to do it in parallel.<\/p>\n
For each additional number in the thread, you need to rearrange and add a couple of million digits. That’s a lot of work, but it’s not crazy. On any halfway decent computer, it won’t take long. To get a sense, I just whipped up a Python program that generated 1,000,000 random pairs of digits, and added them up. It took under 8 seconds – and that’s half-assed code written using a not-particularly fast interpreted language on a not-particularly-speedy laptop. A single iteration of the Lychrel thread computation even for a million-digit candidate doesn’t take that long – it’s on the order of seconds. <\/p>\n
The catch is that the process of searching a Lychrel thread is intrinsically serial: you can’t have different CPUs computing the next thread element for different values: you don’t know the next value until you’ve finished the previous one. So even if it took just 1 second to do the reverse+add for million digit numbers, it would takes a long time to actually explore the space. If you want to explore the next million candidates, at 2 seconds per iteration, that will take you around 3 weeks!<\/p>\n
Even if you don’t waste time by using a relatively slow interpreter like Python – even if you use carefully hand-optimized code using an efficient algorithm, it would take months at the very least to explore a space of billions of elements of the 196 thread! And to get beyond what anyone has done, you’ll probably need to end up doing years of computation, even with a very fast modern computer – because you can’t parallelize it.<\/p>\n