Counting Palindromes By Adding 1
One morning, while walking, I saw a building with the number 13231, and I identified that number as a palindrome (a number that is the same when the digits are read forwards and backwards) and thought, “What number palindrome is that?”
To see what I mean by that, here is a list of the first 22 palindromes:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121…
The “palindrome number” of any palindrome will be where it is found in this list. For example, I will call 0 the first palindrome, 1 the second, 9 the tenth, 11 the eleventh, and 22 the twelfth, and so on. This numbering is equivalent to the number of palindromes less than or equal to the palindrome. For example, 131 has these 23 palindromes less than or equal to it:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131
Therefore, 131 is the 23rd palindrome. This same logic can extend to our target number (13 231), but requires a much longer list. To count the palindromes less than or equal to 13231, I first counted the one-digit, two-digit, three-digit, and four-digit palindromes, giving me the number of palindromes below 10000. After this, I simply had to add the number of palindromes between 10000 and 13231, which should be easier to find.
One-digit palindromes are easy — there are 10, the numbers 0–9. Two-digit palindromes are almost as easy; we can start the number with any digit but 0 (because then it would no longer be two-digit), and the second number must be the same as the first. This leaves us 9 two-digit palindromes: 11, 22, 33, 44, 55, 66, 77, 88, and 99.
With three-digit palindromes, the first and last digits must be the same, while the middle digit can be anything. As before, the first (and last) digit cannot be 0, leaving us with 9 choices for a starting (and ending) digit. The middle digit, however, has no limitations; it can be any of the 10 digits from 0–9. The total number of palindromes can be seen as (number of choices for first digit) x (number of choices for middle digit), where solving gives 9 x 10 = 90 three-digit palindromes.
Four-digit palindromes are exactly the same: 9 choices for the first and last digit, 10 choices for the middle two (which must be the same). Again multiplying, this gives us 90 four-digit palindromes.
This, gives us the total number of palindromes below 10000. 10 one-digit + 9 two-digit + 90 three-digit + 90 four-digit = 199 palindromes below 10000. To get the the answer to our original question, we have to add the number of palindromes between 10000 and 13231, listed below.
10001, 10101, 10201, 10301, 10401, 10501, 10601, 10701, 10801, 10901, 11011, 11111, 11211….
Interesting… if you look at the first three digits (which are reflected into the last three), they seem to be counting up. In fact, it makes sense that they are because we are always looking for the next palindrome, which is just the next natural number and the number’s reflection! This gives us an easy answer to how many palindromes are between 10000 and 13231; simply take the first three digits (the repeated part of the palindromes) and count the numbers in that range. To do this, simply subtract 100 from 132 and add 1. This means there are 33 palindromes between 10000 and 13231 (including 13231).
Our final answer is then the 199 palindromes below 10,00 + the 33 above = 232 palindromes less than or equal to 13231. Thus 13231 is the 232nd palindrome, a fitting number that itself is the 33rd palindrome, which itself is the 13th.
Now the curious among you may be asking if there is a an easier way to find this answer, and, of course, the answer is yes. We found the palindrome number of 13231, but what about any other number?
Let us move away from a specific example and instead think about a palindrome P that we wish to find the palindrome number of. To be clear, the value we are looking for is the number of palindromes less than or equal to P.
Similar to the example above, it is easier to break this counting down into finding the palindromes with a certain number of digits and adding these up until we get close to P. For example, we added the number of one, two, three, and four-digit palindromes to get the number of palindromes under 10000, which is the largest multiple of 10 under 13231. This method will get us much closer to our target and will make calculation easier.
We know the number of palindromes with one digit is 10, two digits is 9, three digits is 90, and four digits is also 90. Counting five-digit palindromes is easy too, 9 choices for the first (and last) digit, 10 choices for the second (and fourth) digit, and 10 choices for the middle digit, giving 9 x 10 x 10 = 900 five-digit palindromes. Identically, we can calculate that there are also 900 six-digit palindromes.
So our sequence so far is: 10, 9, 90, 90, 900, 900…
This pattern of number of palindromes per digit is very interesting. It seems that the numbers repeat twice (excluding the two at the start), and then scale by 10. The scaling behavior can be confirmed by noticing that each digit of a palindrome has a reflected copy on the other end of the number (1654561), so adding two more digits adds one more pair of these digits, giving 10 choices for the new digit and increasing the total number of palindromes by 10 times.
The repeated behavior of this sequence is explained by thinking of the ‘base number’ of a palindrome, the number that is being being reflected. For example, the base number of 13255231 is 1325, and the base number of 121 is 12. Every palindrome has a base number, and every base number can be made into two palindromes. The base number 1325 can be made into 13255231 or 1325231, depending on if the middle digit is ‘shared’ between the base and its reflection. This idea of shared and unshared palindromes will become extremely helpful. In this case, it is obvious that there are the same number of 7-digit and 8-digit palindromes because they all come from the same four-digit base numbers. This same logic applies to the number of (2n-1)-digit palindromes and (2n)-digit palindromes.
But that still leaves the question of the start of the sequence — Why are there 10 one-digit palindromes and not 9? The answer is 0. We normally think of 0 as a one-digit number, but it doesn’t really fit in, as we normally do not allow palindromes to start with 0. This results in us having an extra one-digit number, and doesn't affect much else.
Our sequence of number of palindromes has now been confirmed to follow the patterns we identified, and starts: 10, 9, 90, 90, 900, 900, 9000, 9000… We also know that any palindrome with an odd number of digits is ‘shared’ while with even number of digits it is ‘unshared.’
For example, let’s say P is 5839229385. This palindrome has 10 digits and is unshared, as seen by the duplicate 2s in the middle. To find the total number of palindromes less than or equal to our palindrome P, we can add together the number of shared and unshared palindromes below P. To get the number of shared palindromes below P, we need to add all of the numbers in our pattern corresponding to odd-length (but with less than 10 digits) palindromes: 10, 90, 900, 9000, and 90000. Adding these together gives us 100000, a remarkably nice number of shared palindromes. Generalizing this, this number is always a power of ten, with the number of digits being one more than half the number of digits in the palindrome (if the palindrome is unshared).
To find the number of unshared palindromes less than or equal to P, we will use a different method. The base number of our example (5839229385), is 58392. Any base number below 58392 will correspond to a palindrome below P if we construct it as unshared, and any base number above 58392 will correspond to a palindrome above P. We can use this fact to see that there are, in fact, 58392 (the base number) unshared palindromes less than or equal to P. Generalizing again, the base number for an unshared palindrome is exactly half the length of the palindrome itself.
Adding together the 100000 shared palindromes below P and the 58392 unshared palindromes below or equal to P, we get that P is the 158392nd palindrome. Generalizing this, when we have any unshared palindrome, if you add a 1 to the beginning of the base number of a palindrome, you have the number of that palindrome. Testing this, 1331 is the 113th palindrome, 845548 is the 1845th palindrome, and 11 is the 11th palindrome. This, however, does not work for shared palindromes.
For unshared palindromes, “1” + the base number is the palindrome number.
Do not worry, shared palindromes have a similar (and nearly as easy) method of finding their number. For this, we will consider 0 to be two-digits, as it makes our math slightly easier and won’t affect results. Our new palindromes by length pattern is: 9, 10, 90, 90, 900..., the same but with the first two elements switched.
To find the number of unshared palindromes below a shared palindrome P with a number of digits D, we add the numbers corresponding to unshared (and thus even-length) items in the patten that are below D digits: 10, 90, 900, 9000, etc. Again, we always get a multiple of 10 with a length of (D-1)/2.
To find the number of shared palindromes less than or equal to a shared palindrome P, it is exactly the same as the process to find the number of unshared palindromes less than or equal to a a unshared palindrome — that is, it is equal to the base number. This time, however, the base number has (D+1)/2 digits.
Again, we find ourselves adding a power of ten to the base number of the palindrome, but it is no longer a nice concatenation. Instead of simply placing the 1 in front of the base number, the power of 10 lines up to add a one to the first digit of the base number. Trying this, 34543 is the 445th palindrome, 9 is the 10th palindrome, and 13231 is the 232nd palindrome.
For shared palindromes, the base number with 1 added to the first digit is the palindrome number.
With that, I think I’ve thoroughly covered my original question, and found a satisfying piece of math to go along with it!
