Algorithms 1: 196/reverse-then-add, and more

I've decided that I'm going to start a series of posts on algorithms. It's been too long for me since I've studied data structures and algorithms, so I'm going to get Knuth's books and work my way through them, posting summaries/reviews/interesting Knuthbits (they're like tidbits, only more Knuthy) here. I will also be going over random algorithms and other things of interest that I've found over the years, because why not?

As an introduction to this series of posts, I'd like to talk about the 196-algorithm. It's also known as the reverse-then-add algorithm. In this post, I will be discussing the algorithm itself, and a few properties I've recently found of the numbers in the algorithm, and then in the next post I will talk about the code for the program I've mentioned below. The essential idea is this:

1) Take any positive number
2) Reverse the digits in the number
3) Add the numbers from 1 and 2 together
4) Repeat

Eventually, following those steps, you will probably get a palindrome number, which is to say a number whose digits are the same written forward as they are backward.

I've always been fascinated by this algorithm because I love words, and palindromes are super-interesting in written form, to me. I also have a strong interest in synesthesia and other neurologically bizarre-but-really-cool conditions. The reason this is relevant is that I wondered the following question: For a number-color synesthete (they see numbers as colors, and often not just numbers, but all "graphemes", or symbols which represent something written out), what do palindromic numbers look like? Do they look like a gradient that goes from one color to another? Is it a series of images that travel from one end of reality to the other? (It's not always specifically colors, but often stark, vivid images that they see.) I may have to ask V.S. Ramachandran this very question, because if anyone would know, it's surely him!

So, I set out to formulate what they might see with a long palindromic number. I also wanted to see if maybe there was a chance that a number-color synesthete would be able to identify whether or not a number was a palindrome faster than someone without synesthesia, and felt a program which let them see the algorithm working would be a pretty good way to test the idea. In-so-doing, I stumbled upon a few really interesting properties of the algorithm and of numbers contained in the 196 series.

The reason 196 is relevant is because it is what's called a Lychrel number; it is, in fact, the first candidate Lychrel number (a number that is proposed to be a Lychrel, but there's no proof for it yet). Wikipedia has a decent page on these, but basically, they are numbers which, when this algorithm is run, do not appear to ever converge to a palindrome. It is conjectured that they never will, but it's never been proven, either, and last I checked, this is one of the unsolved proofs of mathematics.

First, I'll show you a few normal numbers run through the algorithm and you can see them become palindromes. I had some trouble deciding on a format; if you prefer a different one in the future, let me know in the comments. The format is: Starting number: {iterations} = palindrome number

2: {4} = 4
6: {12, 33} = 33
19: {110, 121} = 121 (this one is interesting because the 0 at the end means the resulting reversed number is one fewer digits than the other)
21300: {21612} = 21612

The set notation here is not coincidental; I chose this because the sets of numbers which lead to the palindrome number can have very interesting properties. As mentioned, if we start with 196, it appears that the cardinality (size, to non-mathematicians) of the set is infinite. Here are the first several numbers of the 196 set:

196: {887, 1675, 7436, 13783, 52514, 94039, 187088, 1067869...} = ???

On Friday, October 18th, 2013, I was looking at these numbers and wondering how we might determine any that ARE Lychrel numbers, but that are not strictly in the set above (outside of brute-force). In retrospect, it's incredibly easy, and I believe I found a paper at least implying that it can be done, but haven't been able to read the paper yet to know, so I thought I'd write my own findings here. Furthermore, after a bit more research, there do seem to be other numbers that aren't able to be produced by the following, and are not within the 196 set specifically (879 is an example).

The construction goes as follows: Take any Lychrel number and, starting on one side, add one to the digit. Starting on the other side, subtract one from the digit. You can continue this method to produce more, unique Lychrel's, and interestingly, for the next step in the process, they will produce the next number within the 196 set. This is a fairly trivial proof. You don't even have to do the same operation each time you move to a new digit, as long as you're doing the opposite one to the match on the other side.

This proof relies on the fact that all numbers have an odd or even number of digits; it is a piecemeal algebraic proof.

Suppose you have some number with digits (X₀) (X₁) (X₂)...(X_n)

I put the digits into parentheses because it's annoying to look at numbers this way otherwise. This number has one of two properties. It has either an even number of digits, or an odd number of digits. If n is even (corresponding to an odd number of digits, since we're starting at zero), then:

1) It has a pivot number in the middle around which the number could be a palindrome, e.g. 11911
2) The pivot number cannot be changed and necessarily maintain the values of the result (I won't prove this unless this comes to a paper; it just seems fairly easy to see that if it's less than 4 and you move it to a 5, you're changing the next digit to the left, so it can throw a big wrench in the works)

Conversely, if n is odd, it has no pivot number.

Consider a number of three digits:

1) (X₀) (X₁) (X₂)

This is a palindrome if X₀ = X₂ regardless of what X₁ is (it's the pivot number). Reversed, it is simply (X₂) (X₁) (X₀).

Digits in base 10 must always be strictly less than 10 and greater than or equal to 0. The result of running the algorithm on the above may have to carry values throughout, so I'll include a + C value for that, which then it looks like:

2) (C₀) (X₀ + X₂ + C₁) (X₁ + X₁ + C₀) (X₀ + X₂) 

Due to this, it's easy to see that the resulting number is not necessarily a palindrome, but it's also trivially easy to see how to construct the other numbers. Note that I use C₀ twice in the equation because both times, if there's a carry, the value from (X₀ + X₂) will be the same both times, and strictly never more than one (that's true of any digits carried here, as the highest sum of any numbers in the set is 19, or 9 + 9 + 1 carried from before).

If we add one to the first digit and subtract one from the last digit, or vice versa, as long as the resulting digit is less than 10 or greater than or equal to 0, we've made a valid operation which will result in the same number as above. Here is the starting number using this construction:

3) (X₀ + 1) (X₁) (X₂ - 1)

Now, running the algorithm, we get:

4) (C₀) (X₀ + 1 + X₂ - 1 + C₁) (X₁ + X₁ + C₀) (X₂ - 1 + X₀ + 1)

Simplify by canceling the + 1 - 1 values, and you have the exact same number as before. Obviously, any number which can be constructed this way can have it repeated and you can use higher numbers as well, so long as the restriction that the resulting digit is strictly less than 10 or greater than or equal to 0 is enforced. The reason for that requirement is simple: Otherwise, you could accidentally force a carry where normally there would be none (imagine adding 9 to a 9 at the front of the digit, causing it to go over, and subtracting 9 from the final digit, causing it to go...negative? Or something crazy anyway).

Using the above proof, you can easily show that there are infinitely many Lychrel numbers which do not appear directly in the 196 set, but which, when the 196 algorithm is run on any one of them, will automatically produce the next number in the 196 set, and even further that any number you run this on will always converge to the next number in the starting number's set.

What's interesting about this algorithm is that you can do almost unlimited things with it. You can add one to the first digit, subtract one from the last, add three to the next one, subtract three from the second to last, and so on. You can skip all the way to the numbers around the pivot point if there is one (or to the ones next to each other in the middle) and add one to one of them, and subtract one from the other.

Finally, you can see via the construction that this works for numbers of any length, so long as it's more than one digit. With one digit, it's the pivot number and changing it inherently changes the palindromicity of the successive number, depending on if the changed value is greater than or equal to, or strictly less than 5.

Next time, I'll show some screenshots generated from my program and delve into how I very simply codified the algorithm, and more advanced ways of doing so for high-performance machines that will just run the algorithm over and over without requiring a human to look at it running.

Thanks for reading! Let me know what you think in the comments.