# Generating palindromic numbers

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.

## First palindromic number

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

So we keep adding till digit = 9. Here l=m.

We shift right once, to l=m-1, and add once:

We go back to the middle, to l=m, and add once:

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:

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:

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.

```

## 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).

Click on the expression below to evaluate it with the online calculator:
f(44506, 16); f(N, B) = (N<B) ? N : ( f(N // B, B) ., (N mod 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

if(l < k//2):           # will evaluate to false only when k%2=1 and l=m

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.
```  rank,n  palindrome,p
1       0
2       1
3       2
..      ..
11      11
12      22
13      33
..      ..
20      101
21      111
22      121
```
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:
1. 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.
2. 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 -= 1; }                 // if n has only one digit

else if(p=='1' && p=='0')         // if first two digits == 10
{
p = ' ';
p = '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=='1')                      // if 11 <= first two digits <= 19
{
p = ' ';                         // 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 -= 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.