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.
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"; }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).
That is totally bananas. Good job kernelbob.
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…)
Nice. For all palindromes, here’s some Haskell using list comprehensions:
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"; }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"; }Another Haskell version, without using strings:
Sorry about the multiple posts, my submissions got caught by the PP spam filter…
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
@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:
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))//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();
}
Smart and dummy in Java: http://codepad.org/kxgYZF2U
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 breakAugust 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:
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 :/ )