Generating Palindromes

August 29, 2014

The first hundred palindromic numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212, 222, 232, 242, 252, 262, 272, 282, 292, 303, 313, 323, 333, 343, 353, 363, 373, 383, 393, 404, 414, 424, 434, 444, 454, 464, 474, 484, 494, 505, 515, 525, 535, 545, 555, 565, 575, 585, 595, 606, 616, 626, 636, 646, 656, 666, 676, 686, 696, 707, 717, 727, 737, 747, 757, 767, 777, 787, 797, 808, 818, 828, 838, 848, 858, 868, 878, 888, 898, and 909.

Your task is to write a program that generates the palindromic numbers in order; use it to find the ten-thousandth palindromic number. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

16 Responses to “Generating Palindromes”

matthew said

August 29, 2014 at 9:44 PM

We can do this as an extension of the usual sort of tuple generation in lexical order algorithm. We do the tuple generation in the first half of our string, and reflect the result in the second half of the string: then we don’t need to worry about odd or even lengths; and we extend the string when the digits have all wrapped around. So, a get next palindrome function with C++ strings:

#include <iostream>
#include <string>
#include <cstdlib>

char minc = '0', maxc = '9';
void nextpalindrome(std::string &s)
{
  int len = s.length();
  for (int n = (len+1)/2; n > 0; n--) {
    if (s[n-1] < maxc) { 
      s[len-n] = s[n-1] = s[n-1]+1;
      return;
    } else {
      s[len-n] = s[n-1] = minc;
    }
  }
  // wrap around, so extend
  s[0]++;
  s.push_back(s[0]);
}

int main(int argc, char *argv[])
{
  int n = std::atoi(argv[1]);
  std::string s = "0";
  for (int i = 0; i < n-1; i++) {
    nextpalindrome(s);
  }
  std::cout << s << "\n";
}

kernelbob said

August 30, 2014 at 2:00 AM

I am jumping straight to the answer. Here is a function to find the n’th palindrome directly.

>>> def nth_palindrome(n):
...     if n <= 2:
...         return n - 1            # special case
...     sn = str(n)
...     drop = len(sn) - 1
...     if '11' <= sn <= '2':       # lexical - compare leading digits
...         rev_index = -1          # palindrome has even length:
...                                 # reverse all digits
...     else:
...         rev_index = -2          # palindrome has odd length:
...                                 # reverse all digits but least
...         if sn < '2':
...             drop -= 1
...     sp = str(n - 10**drop)
...     sp += sp[rev_index::-1]     # append reversed digits
...     return int(sp)
... 
>>> for i in range(5):
...     n = 10**2**i
...     print('palindrome %d is %d' % (n, nth_palindrome(n)))
... 
palindrome 10 is 9
palindrome 100 is 909
palindrome 10000 is 9000009
palindrome 100000000 is 900000000000009
palindrome 10000000000000000 is 9000000000000000000000000000009
>>>

It is loop free. It is not O(1) time, because the string operations are O(digits).

Nate said
August 30, 2014 at 2:44 AM
That is totally bananas. Good job kernelbob.
kernelbob said
August 30, 2014 at 4:34 AM
My solution is cryptic and probably too golfish. Let me try to explain.

You can generate all the palindromes of length n by generating the integers of length ⌈n/2⌉ from 10…0 through 99…9, then appending the reversed digits to each. If the palindrome has an even number of digits, then append all the digits. If it has an odd number of digits, append all but the least significant.

E.g., here are the palindromes of length 5 in order.

10001 10101 10201 10301 … 78987 79097 … 99999.

Define np(n) as the number of palindromes of length n. It is not hard to see, given how palindromes are constructed, that

np(2n) = 9 × 10ⁿ⁻¹
np(2n+1) = 9 × 10ⁿ

If you regard 0 as a palindrome of length 0, then those equations also hold for n = 0: np(0) = 1, np(1) = 9. (I think it’s a wart on the Arabic number system that zero can not be represented as the empty string, but I digress. (-: )

Define npu(n) as the number of palindromes of length up to n.

npu(2n) = 𝝨 for i = 0 to 2n of np(i)
= 1 + 9 + 9 + 90 + 90 + … + 90…0 + 90…0
= 1 + 99…9 + 99…9
= 199…9
= 2 × 10ⁿ – 1

npu(2n + 1) = npu(2n) + np(2n + 1)
= 2 × 10ⁿ – 1 + 9 × 10ⁿ
= 11 * 10ⁿ – 1

Define ifp(n) as the index of the first palindrome of length n.

ifp(n) = npu(n – 1)

Let’s look at the case where the m’th palindrome has even length 2n.

Define fhfp(2n) as the first half of the first palindrome of length 2n.

fhfp(2n) = 10…0
= 10ⁿ⁻¹

Now we can write an expression for the first half of the m’th palindrome, where ifp(2n) <= m < ifp(2n+1).

fhp(m) = fhfp(2n) + (m – ifp(2n))
= 10ⁿ⁻¹ + m – npu(2n – 1)
= m + 10ⁿ⁻¹ – 11*10ⁿ⁻¹
= m – 10 × 10ⁿ⁻¹
= m – 10ⁿ

(I admit it. I was surprised when it simplified down to that.)

The other half of the palindrome is constructed by appending the digits in reverse order.

That covers the even-length case. The odd length case is analogous, but with a little more bookkeeping.

(Please oh please, WordPress, don't $&~# the formatting…)

matthew said

August 30, 2014 at 4:48 AM

Nice. For all palindromes, here’s some Haskell using list comprehensions:

prefixes 0 = [[k] | k <-['1'..'9']]
prefixes n = [k:s | s <- prefixes (n-1), k <- ['0'..'9']]
p n = 
  [ reverse s ++ tail s | s <- prefixes n ] ++
  [ reverse s ++ s | s <- prefixes n ] ++ 
  p (n+1)
allpals = [[]] ++ p 0

main = do print (allpals !! 99999)

matthew said

August 30, 2014 at 4:53 AM

And here’s a C++ function for generating the next palindrome for a string (I submitted this previously, but WordPress seems to have lost the comment, apologies if it appears twice).

#include <iostream>
#include <string>
#include <cstdlib>

char minc = '0', maxc = '9';
void nextpalindrome(std::string &s)
{
  int len = s.length();
  for (int n = (len+1)/2; n > 0; n--) {
    if (s[n-1] < maxc) { 
      s[len-n] = s[n-1] = s[n-1]+1;
      return;
    } else {
      s[len-n] = s[n-1] = minc;
    }
  }
  s[0]++;
  s.push_back(s[0]);
}

int main(int argc, char *argv[])
{
  int n = std::atoi(argv[1]);
  std::string s = "0";
  for (int i = 0; i < n-1; i++) {
    nextpalindrome(s);
  }
  std::cout << s << "\n";
}

matthew said

August 30, 2014 at 5:17 AM

Another solution:

#include <iostream>
#include <string>
#include <cstdlib>

void nextpal(std::string &s)
{
  int len = s.length();
  for (int n = (len+1)/2; n > 0; n--) {
    if (s[n-1] < '9') { 
      s[len-n] = s[n-1] = s[n-1]+1;
      return;
    } else {
      s[len-n] = s[n-1] = '0';
    }
  }
  s[0]++;
  s.push_back(s[0]);
}

int main(int argc, char *argv[])
{
  int n = std::atoi(argv[1]);
  std::string s = "0";
  for (int i = 0; i < n-1; i++) {
    nextpal(s);
  }
  std::cout << s << "\n";
}

svenningsson said

August 30, 2014 at 11:36 AM

Another Haskell version, without using strings:

module Palindromic where

palindromicN 1 = [0..9]
palindromicN 2 = [ 10*n+n | n <- [1..9] ]
palindromicN k = [ extendPalindrome n p | n <- [1..9] , p <- palindromicN (k-2) ]

palindromic = concatMap palindromicN [1..]

extendPalindrome n p = n*10^(digits+1) + p*10 + n
  where digits = ilog10 p

ilog10 n = aux n 1
  where aux n l | n < 10 = l
        aux n l = aux (n `div` 10) (l+1)

main = print (palindromic !! 10000)

matthew said
August 30, 2014 at 2:21 PM
Sorry about the multiple posts, my submissions got caught by the PP spam filter…
attilacsordas said
August 30, 2014 at 9:58 PM
A basic and slow Python 10-liner:

a = [] for i in range(0,10000000): m = [int(char) for char in str(i)] # split int into list of digits n = list(reversed(m)) # make reverse of the list of digits if m == n: # definition of palindrome x = int(''.join(map(str,m))) # convert list of ints back to one number a.append(x) # add palindrome to list if len(a) == 10000: break # break out of loop if 10000th palindrome reached print a[9999] # print 10000th palindrome

matthew said

August 31, 2014 at 9:55 AM

@svenningsson: Nice idea of working from the inside out, but that solution doesn’t seem to quite work – 1001 doesn’t appear on the list for example, but here’s another version with the same idea:

extend n ks as = [k*10^(n-1) + a*10 + k | k <- ks, a <- as]
core 0 = [0]
core 1 = [0..9]
core n = extend n [0..9] (core(n-2))
pal 0 = [0]
pal 1 = [1..9]
pal n = extend n [1..9] (core(n-2))
p = concatMap pal [0..]
main = do print (p !! 9999)

matthew said

September 1, 2014 at 7:22 PM

And finally, I thought it would be nice to use kernelbob’s method of constructing the nth palindrome directly, but just use numbers throughout – also, it’s straightforward to generalize to any radix:

#!/usr/bin/python
import string
digs = string.digits + string.lowercase + string.uppercase + "#*"

def int2radix(n, radix):
    if n==0: return '0'
    digits = []
    while n != 0:
        digits.append(digs[n % radix])
        n /= radix
    digits.reverse()
    return ''.join(digits)

def pal(n, radix):
    tmp = n; p = 1; k = 0
    # Reduce n until it's 1xxx or Nxxx for N > 1
    while tmp >= 2*radix:
        tmp /= radix
        k += 1
        p *= radix
    if tmp <= radix: 
        # Odd length case
        n -= p
        tmp = n/radix
    else:
        # Even length case
        n -= radix*p
        tmp = n
        k += 1
    for i in range(k):
        # Double up
        n = radix*n + tmp%radix
        tmp /= radix
    return n

for i in range(1,100): print(int2radix(pal(i,2),2))
for r in range(2,65): print(int2radix(pal(pow(10,100),r),r))

ickybyte said
September 2, 2014 at 2:33 AM
//C# – likely not the most efficient but it works
public static void Main(string[] args)
{
int i = 0;
uint j = 0;
while (i < 10000)
{
if (IsPalindrome(j))
{
i++;
Console.WriteLine(j);
}
j++;
}

}
private static bool IsPalindrome(uint i)
{
string candidate = i.ToString();
if (candidate.Length == 1)
{
return true;
}
int lengthOfSplit = candidate.Length / 2;
string firstHalf = candidate.Substring(0, lengthOfSplit);
bool isEvenLength = (candidate.Length % 2 == 0);
string secondHalf = ReverseString(
candidate.Substring(isEvenLength
? lengthOfSplit
: lengthOfSplit + 1, lengthOfSplit));
return firstHalf.Equals(secondHalf);

}
private static string ReverseString(string candidate)
{
char[] chars = candidate.ToCharArray();
var rev = chars.Reverse().ToArray();
StringBuilder builder = new StringBuilder(rev.Count());
foreach (var c in rev)
{
builder.Append(c);
}
return builder.ToString();

}
Andras said
September 2, 2014 at 10:27 AM
Smart and dummy in Java: http://codepad.org/kxgYZF2U

Mark said

September 9, 2014 at 1:28 PM

def is_pal(n):
    return str(n) == str(n)[::-1]

cnt = 0
for i, n in enumerate(range(10**7)):
    if is_pal(n):
        cnt += 1
        if cnt == 10000:
            print n
            break

sealfin said

August 21, 2017 at 7:33 PM

August 29th, 2014.c:

#include "seal_bool.h" /* <http://GitHub.com/sealfin/C-and-C-Plus-Plus/blob/master/seal_bool.h> */
#include "printDateAndTime.h" /* <http://Gist.GitHub.com/sealfin/6d35f3a3958bd6797a0f> */
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

size_t f_NumberOfDigits( unsigned long p )
{
  size_t number_of_digits = 1;

  p /= 10;
  while( p != 0 )
  {
    number_of_digits ++;
    p /= 10;
  }
  return number_of_digits;
}

void p_NumberToString( unsigned long p_number, char * const p_string )
{
  size_t i = 0, k = 0;

  p_string[ i ++ ] = p_number % 10 + '0';
  p_number /= 10;
  while( p_number != 0 )
  {
    p_string[ i ++ ] = p_number % 10 + '0';
    p_number /= 10;
  }
  p_string[ i -- ] = '\0';

  while( k < i )
  {
    const char c = p_string[ i ];

    p_string[ i ] = p_string[ k ];
    p_string[ k ] = c;
    i --;
    k ++;
  }
}

bool f_IsPalindrome( const char * const p )
{
  size_t i = 0, k = strlen( p ) - 1;

  while( i < k )
  {
    if( p[ i ] != p[ k ] )
      return false;
    i ++;
    k --;
  }
  return true;
}

const char * const f_SuffixForNumber( const int p )
{
  char *suffix = "th";

  switch( p % 10 )
  {
    case 1:
      if( p % 100 != 11 )
        suffix = "st";
      break;
    case 2:
      if( p % 100 != 12 )
        suffix = "nd";
      break;
    case 3:
      if( p % 100 != 13 )
        suffix = "rd";
      break;
  }
  return suffix;
}

void main( void )
{
  p_PrintDateAndTime();
  printf( "\n" );

  {
    const int k_SoughtPalindromicNumber = 10000;

    unsigned long i = 0;
    char *string_representation_of_i = ( char* )malloc( sizeof( char ) * ( f_NumberOfDigits( ULONG_MAX ) + 1 ));
    int number_of_palindromic_numbers = 0;

    while( true )
    {
      if(( i % 10 != 0 ) || ( i == 0 ))
      {
        p_NumberToString( i, string_representation_of_i );
        if( f_IsPalindrome( string_representation_of_i ))
          if( ++ number_of_palindromic_numbers == k_SoughtPalindromicNumber )
            break;
      }

      {
        const unsigned long old_i = i;

        if( ++ i < old_i )
        {
          fprintf( stderr, "Sorry, an error occurred: `i` overflowed.\n" );
          free( string_representation_of_i );
          return;
        }
      }
    }
    printf( "The %d%s palindromic number is %lu.\n", k_SoughtPalindromicNumber, f_SuffixForNumber( k_SoughtPalindromicNumber ), i );
    free( string_representation_of_i );
  }

  printf( "\n" );
  p_PrintDateAndTime();
}

Output:

The 10000th palindromic number is 9000009.

On an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) to run the solution took:

approximately eighteen minutes and twenty-three seconds on Mac OS 9.2.2 (International English) (the solution interpreted using Leonardo IDE 3.4.1);
approximately ten seconds on Mac OS X 10.4.11 (the solution compiled using Xcode 2.2.1).

(I’m just trying to solve the problems posed by this ‘site whilst I try to get a job; I’m well aware that my solutions are far from the best – but, in my defence, I don’t have any traditional qualifications in computer science :/ )

Programming Praxis