A palindromic number (or numeric palindrome) is a number that reads the same when reversed. For example 0, 1, 333, 12321 are palindromes. But 123 is not a palindrome as when reversed it becomes 321. Leading zeros are not considered. For example 00100 cannot be taken as a palindrome since it is actually 100; when reversed it becomes 001 = 1.
The pattern followed by palindromic numbers is analysed, then an algorithm is provided that implements this pattern to generate all palindromic numbers in increasing order starting from any given palindromic number, taking constant time per number generated. Finally a purely mathematical method is derived that computes the nth palindromic number, in time proportional to the number of digits of n.
The first palindromic number of:
- 4 digits is 1001
- 3 digits is 101
- 2 digits is 11
- 1 digit is 1
- 0 digit is 0
Notice that 0 is considered to be a palindromic number with 0 digit, not 1 digit. The case of 0 is indeed interesting. Remember that leading zeros are not considered. As will be seen later numbering palindromic numbers is very simple yet has 0 as the very first of them, and of 0 digit.
Pattern in palindromic numbers
Let p be a palindromic number. Let k be the number of digits of p. Let m and l denote positions (or levels) on the string of digits of p, starting from position 0 from the lowest-significant-digit (from the right). l varies from 0 to m. For a certain value of k, m = middle position = [(k-1)/2], where [x] = floor(x) = largest integer less than or equal to x. p is operated on as a number and not a string.
Below is the analysis of the pattern followed by palindromic numbers for the cases k=5 and k=6. 'add' is the added value.
Starting from: k=5, m=2, p=10001 OR k=6, m=2, p=100001
next is: 10101 (add=0100) 101101 (add=1100)
keeps adding to: 10901 109901
So we keep adding till digit = 9. Here l=m.
We shift right once, to l=m-1, and add once:
next is: 11011 (add=110) 110011 (add=110)
We go back to the middle, to l=m, and add once:
next is: 11111 (add 0100) 111111 (add=1100)
keeps adding to: 11911 119911
We shift right again: 12021 (add=110) 120021 (add=110)
Each time we shift right, to l=m-1, we go back to the middle, to l=m:
we end up at: 19991 199991
Now we shift right twice, to l=m-2, and add once:
Next is: 20002 (add=11) 200002 (add=11)
We go again for l=m-1 and l=m as before,
and we end up at: 29992 299992
Again we shift right twice, to l=m-2, and add once:
next is: 30003 (add=11) 300003 (add=11)
We go again for l=m-1 and l=m as before,
and we end up at: 39993 399993
Eventually we end at: 99999 999999
Now we shift right 3 times, to l = m-3 = -1, which is an invalid position.
This marks the end of the current k. We now go to the next k.
Next is: 100001 (add=2) 1000001 (add=2)
On changing k, add=2. But usually, add = 11×10l.
Iterative algorithm
Let B denote the number base. In the previous analysis the base 10 was used. From now 'B' (not 10) will be used.
Note that for a base B different from 10, the result does not seem to be a palindromic number because it is the number converted to base 10. For example if the number was supposed to be ADDA in base B=16 then it is obtained as = A*163+D*162+D*161+A*160 = 10*163+13*162+13*161+10*160 = 44506. To convert the result back to given base B so to see it as a palindromic number, use the following:
The digit at a position l of a natural number N in a base B,
counting from l=0 from the lowest-significant-digit is = [N / Bl] mod B = (N // B^l) mod B
where [x] = floor(x) = (a // b).
The iterative algorithm is a direct interpretation of the pattern followed by palindromic numbers as was previously described. Below is the implementation in the Python programming language. The values of B0 to Bm can be pre-computed and stored in an array.
#******************************************************************
# Python code
# Iterative algorithm to generate all palindromic numbers
#******************************************************************
palindrome = 1 # set starting number
B = 10 # B = base used, default is base 10
k = 0 # k = number of digits of 'palindrome'
m = palindrome
while(m != 0): # find k
m //= B
k += 1
while(k <= 4):
print(palindrome)
m = (k-1)//2 # compute the middle position
l = m # get at the middle position
while(l >= 0): # l < 0 marks the end of the current k
# get the digit at position l (counting from l=0)
digit = ( palindrome // (B**l) ) % B
if (digit == B-1): # check if digit at l is the last digit 'B-1'
l -= 1 # if true then base case for l is reached
continue # so shift right, to a lower l position
add = B**l
if(l < k//2): # will evaluate to false only when k%2=1 and l=m
add += B**(l+1)
palindrome += add
print(palindrome)
l = m # get at the middle position
palindrome += 2 # base-case for changing the number of digits
k += 1
The nth palindromic number
Value of n =
n is described as the rank of p. The table below shows the ranking starting from n=1 where p=0.
Let t and k be the number of digits of n and p respectively.
Let the string of digits of p, in the base B, be:
pk-1 pk-2 ... p2 p1 p0
The left half of the string of digits of p, that is
pk-1 pk-2 ... p(k/2+1) p(k/2)
is obtained to be
= n - Bt-1 if n - Bt-1 >= Bt-2, or
= n - Bt-2 otherwise
The right half is obtained by copying the string of digits of the left half, in reverse order such that at the end p will indeed be a palindromic number. Essentially:
If left half is (n - Bt-2), then k = 2t - 3 and so p = pk-1 ... p(k/2+1)p(k/2) p(k/2+1) ... pk-1
If left half is (n - Bt-1), < Bt-1, then k = 2t - 2 and so p = pk-1 ... p(k/2+1)p(k/2) p(k/2) p(k/2+1) ... pk-1
If left half is (n - Bt-1), >= Bt-1, then k = 2t - 1 and so p = pk-1 ... p(k/2+1)p(k/2) p(k/2+1) ... pk-1
Examples:
If n = 357 and B = 10 then the left half of p is = 357 - 103-1 = 257. Since 257 > 103-1, we have k = 2(3)-1 = 5 and p = 25752.
If n = 107 and B = 10 then the left half of p is = 107 - 103-2 = 97. So we have k = 2(3)-3 = 3 and p = 979.
Using n as an array of digits
In order to find the nth palindromic number for large values of n, or to easily perform the copy of the left half of digits of p, it is convenient and even more efficient to use n (as well as p) as an array of digits. It is observed that:
If n has only one digit then p = n - 1.
If the left half of p is to be n - 10t-2, then the first two digits of n are = 10, which upon subtraction reduces to 09. The leading zero is discarded (so t-1 digits left). n is then copied from digit t-2 down to 1 (so t-2 digits copied). Therefore k = t-1 + t-2 = 2t-3.
If the left half of p is to be n - 10t-1, < 10t-1, then the first two digits of n are between 11 and 19 inclusive. Upon subtraction the first digit reduces to 0, which is discarded (so t-1 digits left). n is then copied from digit t-1 down to 1 (so t-1 digits copied). Therefore k = t-1 + t-1 = 2t-2.
If the left half of p is to be n - 10t-1, >= 10t-1, then the first two digits of n are >= 20. There is no leading zero to discard (so t-0 digits left). n is then copied from digit t-2 down to 0 (so t-1 digits copied). Therefore k = t-0 + t-1 = 2t-1.
The code below implements the algorithm in JavaScript.
function get_p_from_n (n) // get n and return p both as arrays
{
var i, j;
var p = n;
var t = n.length;
if(t==1) { p[0] -= 1; } // if n has only one digit
else if(p[0]=='1' && p[1]=='0') // if first two digits == 10
{
p[0] = ' ';
p[1] = '9'; // n - 10^(t-2) => 10-1 = 9
for (j=t, i=t-2; i>=1; i--, j++) // copy from t-2 down to 1
p[j] = p[i]; // so k = t-1 + t-2 = 2t-3
}
else if(p[0]=='1') // if 11 <= first two digits <= 19
{
p[0] = ' '; // n - 10^(t-1) => 1-1 = 0
for (j=t, i=t-1; i>=1; i--, j++) // copy from t-1 down to 1
p[j] = p[i]; // so k = t-1 + t-1 = 2t-2
}
else // if first two digits >= 20
{
p[0] -= 1; // n - 10^(t-1)
for (j=t, i=t-2; i>=0; i--, j++) // copy from t-2 down to 0
p[j] = p[i]; // so k = t-0 + t-1 = 2t-1
}
return p;
}
Deriving the method
The mathematical method used to find the nth palindromic number is now derived. This derivation is more about observing the pattern in palindromic numbers and not performing a mathematical analysis. The default base B=10 is used.
There is 1 palindromic number of k=0 digit , which is p=0 at n=1.
There are 9 palindromic numbers of k=1 digit , from p= 1 to p= 9. So p= 1 at n= 2.
There are 9 palindromic numbers of k=2 digits, from p= 11 to p= 99. So p= 11 at n= 11.
There are 90 palindromic numbers of k=3 digits, from p= 101 to p= 999. So p= 101 at n= 20.
There are 90 palindromic numbers of k=4 digits, from p=1001 to p=9999. So p=1001 at n=110.
We realise that the first palindromic number pf of k digits is at
nf = 10[k/2] + 10[(k-1)/2] (1)
where [x] = floor(x) = largest integer less than or equal to x.
Now focus is placed on three specific values of k. The values 4, 5 and 6 are chosen. These will correspond to 2 specific values of the number of digits t of n. The analysis to be performed will obtain p given n. It should be clear from equation (1) above that the analysis is valid for all values of k.
There are 90 palindromic numbers of k=4 digits, from p= 1001 to p= 9999. So pf= 1001 at nf= 110.
There are 900 palindromic numbers of k=5 digits, from p= 10001 to p= 99999. So pf= 10001 at nf= 200.
There are 900 palindromic numbers of k=6 digits, from p=100001 to p=999999. So pf=100001 at nf=1100.
Consider the table below:
case t n n-10t-1 p k
1 3 110 10 1001 4
2 3 199 99 9999 4
3 3 200 100 10001 5
4 4 1099 99 99999 5
5 4 1100 100 100001 6
6 4 1999 999 999999 6
case n-10t-2
4' 4 1099 999 99999 5
What is of main interest is how n-10t-1 relates to the corresponding value of p. That is, how p is obtained from n-10t-1. In this regard, notice that case 4 and case 4' together show that n-10t-2 should be used instead. Essentially it is observed that (n-10t-1) or (n-10t-2) forms the left half of the digits of p. It should be clear that the table only shows the extreme cases of n, but then the statement is true for any n.
The reason why case 4 should instead use n-10t-2 is more than just a consequence of an observed pattern. Essentially the reason comes from the original reason why n is subtracted by a power of 10. The purpose is to subtract n by the appropriate power of 10, such that the result is the left half of the corresponding value of p. The left half of p is targeted because it changes in units of 1, just like n does.
How to find the appropriate power of 10? The answer lies on the first palindromic number pf of k digits. Essentially, given p1 at n1 and pf at nf , if n1 > nf then we expect that p1 > pf. Since pf forms a base case for all p1 of k digits, nf also forms a base case for all n1. In other words, if nf is subtracted by 10x so to form the left half of pf, then n1 will also be subtracted by 10x so to form the left half of p1. This is because both n and the left half of p change in units of 1.
Care is taken in this method because, for a single number of digits t of n, there can be two number of digits k of p. So t alone cannot be used to know what k will be. Also, t alone cannot be used to know the appropriate power of 10 needed.