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, 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.

Contents:

  1. First palindromic number
  2. Pattern in palindromic numbers
  3. Iterative algorithm
  4. The nth palindromic number
  5. Using n as an array of digits
  6. Deriving the method
  7. Links
  8. See also

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 it 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 = floor((k-1)/2), where floor(x) = largest integer smaller 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 of 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.

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
      = floor( (N mod Bl+1) / Bl )
     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 B0 to Bm can be pre-computed and stored.

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

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 first half (from the left) 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 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:
Examples:
1) If n = 357 and B = 10, then the first half of p is obtained to be = 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 first half of p is obtained to be = 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 first 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:
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 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 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    110     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' both show that n-10t-2 should be used instead. Essentially, it is observed that (n-10t-1) or (n-10t-2) forms the first 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 merely a consequence of an observed pattern. Essentially the reason comes from the original reason why n is subtracted by a power of 10. Ultimately the purpose is to subtract n by the appropriate power of 10, such that the result is the first half of the corresponding value of p. The first 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 first half of pf, then n1 will also be subtracted by 10x so to form the first half of p1. This is because both n and the first 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.


Links

  1. http://en.wikipedia.org/wiki/Palindromic_number


See also