The Additive Palindrome Conjecture Is A Risky Venture

The additive palindrome conjecture is very welcoming and satisfying as far as the underlying concept is concerned. It starts with a simple algorithm that presents itself as follows:

1. You pick any positive integer with more than one digit.

2. You create a second integer by reversing the digits of the integer you picked above.

3. You add the two integers and see if the result is a palindrome.

4. If not, you consider the resulting sum as the new integer, create a second one by reversing its digits, and repeat the whole process until you arrive at a palindrome.

Before we proceed any further, let me clarify what a palindrome means. The word ‘palindrome’ refers to letters or words or sentences or numbers that reproduce themselves when you read forward or backward. In the context of this essay, we shall restrict ourselves to the concept of the numeric palindrome.

The following is an example of a numeric palindrome: 484. It reads the same when you try to read it forward or backward.

Now that we have covered what a palindrome means, let’s move on to what the additive palindrome conjecture says:

Any positive integer will lead to a palindrome when subject to the additive palindrome algorithm (outlined above) at some finite iteration.

The question then becomes: Can we prove this? This is exactly what I tried to describe in the title as a risky venture. Before we find out why, let us try and understand how the algorithm behaves for different integers.

This essay is supported by Generatebg

---

The Additive Palindrome Algorithm for Sums of Digits

When it comes to any arbitrary positive integer, as far as the sum of its digits is less than 10, the additive palindrome algorithm will result in a palindrome in the very first step. Here are a couple of examples of this fact:

This is partly because of the nature of the number system we follow (the decimal system). Similarly, we can work out how many steps would be required for different sums of integer digits. For instance, if the sum of the digits adds to 10, then we would arrive at a palindrome after 2 steps of the additive palindrome algorithm. Here is a table for the number of steps required for different sums (the title image is an example for 13):

Notice how 17 requires an unusual number of steps to arrive at a palindrome. Angela Dunn pointed out this anomaly in 1980. It turns out that this is just the beginning of the challenge with the additive palindrome conjecture.

---

The Additive Palindrome Algorithm Beyond Simple Sums of Digits

Charles W. Trigg published an article titled “Palindromes by Addition” in 1967. In this article, he treated the additive palindrome conjecture more rigorously. By way of brute-force computation, he found 249 positive integers that are below 1000, for which he arrived at no palindromes after 100 iterative steps.

Later on, this phenomenon came to be known as “The 196 Problem.” The reason for this is that 196 is the smallest integer among the 249 that Trigg had noted down. Harry J. Saal tried to brute force this problem in 1975 at the Israel Scientific center and did not arrive at any palindrome even after 237,310 steps. Fast forward to 2020, Michael Piepgras continued the grand battle without success.

“By the way — on the 196-Problem I am actually at iteration 1.559.028.251 (645325000 digits) without finding a palindrome. “

— Michael Piepgras (2020)

Besides these challenges, unless we can come up with a general proof (we do have an infinite number of integers after all), the conjecture remains unestablished.

Final Thoughts

The concept of Palindromes is questionable when it comes to genuine real-world applications. Yet, there is something about palindromes that drives us to sink in so much computational cost into understanding them further.

From what I understand, human beings associate perfect symmetry with beauty and art. Needless to say, this inculcates a strong sense of fascination in most of us. This could explain why we are so driven by the notion of palindromes.

With everything said and done, all hope is not lost. Heiko Harborth proved that the additive palindrome conjecture does not hold for number notations which use bases that are powers of 2 (referenced below). For any other number system, the conjecture remains unproved!

---

References and Credit: Charles W. Trigg, Angela Dunn, Jason Doucette, Heiko Harborth, and Martin Gardner.

If you’d like to get notified when interesting content gets published here, consider subscribing.

Further reading that might interest you: How To Really Solve This Combinatorics Puzzle? and How To Execute The Quadratic Equation Magic Trick?

If you would like to support me as an author, consider contributing on Patreon.