The pattern followed by palindromic numbers is analysed. Then an algorithm is provided, which implements this pattern in order 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
- Pattern in palindromic numbers
- Iterative algorithm
- The nth palindromic number
- Using n as an array of digits
- Deriving the method
- Links
- See also

- 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 it has 0 as the very first of them, and of 0 digit.

Below is the analysis of the pattern followed by palindromic numbers for the cases of

Starting from:k=5, m=2, p=10001ORk=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 shiftright once, to l=m-1, and add once: next is: 11011 (add=110) 110011 (add=110)We go backto 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 againfor 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 399993Eventually 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×10^{l}.

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*16

You should convert the result back to the given base B in order to see it as a palindromic number. You can use the following formula:

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

where floor(x) = largest integer smaller than or equal to x.

The 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 B

```
#******************************************************************
# 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+1)) ) // (B**l)
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
```

rank,n palindrome,p 1 0 2 1 3 2 .. .. 11 11 12 22 13 33 .. .. 20 101 21 111 22 121Let

Let the string of digits of p, in the base B, be:

p

The first half (from the left) of the string of digits of p, that is

p

is obtained to be

= n - B

The remaining right-half is obtained by copying the string of digits of the left-half to its right. This is done in reverse order such that at the end, p will indeed appear as a palindromic number. Essentially:

- if first half is (n - B
^{t-2}), then**k = 2t - 3**, and so p = p_{k-1}... p_{(k/2+1)}**p**... p_{(k/2)}p_{(k/2+1)}_{k-1} - if first half is (n - B
^{t-1}), < B^{t-1}, then**k = 2t - 2**, and so p = p_{k-1}... p_{(k/2+1)}**p**p_{(k/2)}p_{(k/2)}_{(k/2+1)}... p_{k-1} - if first half is (n - B
^{t-1}), >= B^{t-1}, then**k = 2t - 1**, and so p = p_{k-1}... p_{(k/2+1)}**p**... p_{(k/2)}p_{(k/2+1)}_{k-1}

1) If n = 357 and B = 10, then the first half of p is obtained to be = 357 - 10

2) If n = 107 and B = 10, then the first half of p is obtained to be = 107 - 10

- If n has only one digit then p = n - 1.
- If the first half of p is to be n - 10
^{t-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 first half of p is to be n - 10
^{t-1}, < 10^{t-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 first half of p is to be n - 10
^{t-1}, >= 10^{t-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.

```
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
}
```

There isWe realise that the first palindromic number1palindromic number of k=0 digit , which is p=0 at n=1. There are9palindromic numbers of k=1 digit , from p= 1 to p= 9. So p= 1 at n= 2. There are9palindromic numbers of k=2 digits, from p= 11 to p= 99. So p= 11 at n= 11. There are90palindromic numbers of k=3 digits, from p= 101 to p= 999. So p= 101 at n= 20. There are90palindromic numbers of k=4 digits, from p=1001 to p=9999. So p=1001 at n=110.

where [x] = floor(x) = largest integer smaller 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

There areConsider the table below:90palindromic numbers of k=4 digits, from p= 1001 to p= 9999. So p_{f}= 1001 at n_{f}= 110. There are900palindromic numbers of k=5 digits, from p= 10001 to p= 99999. So p_{f}= 10001 at n_{f}= 200. There are900palindromic numbers of k=6 digits, from p=100001 to p=999999. So p_{f}=100001 at n_{f}=1100.

case t n n-10What is of main interest is how n-10^{t-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 110 100001 6 6 4 1999 999 999999 6 case n-10^{t-2}4' 4 1099 999 99999 5

The reason why case 4 should instead use n-10

How to find the appropriate power of 10? The answer lies on the first palindromic number p

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.

- Math expression parsing algorithm
- Convert sorted list to complete BST
- Find maximum bipartite matching
- Generate permutations