## Generating Palindromes

### August 29, 2014

Here is our palindrome generator:

`(define-generator (palindromes)`

(do ((k 0 (+ k 1))) ((= k 10))

(yield k))

(do ((i 1 (* i 10))) (#f)

(do ((j i (+ j 1))) ((= j (* 10 i)))

(let ((ds (digits j)))

(yield (undigits (append ds (reverse ds))))))

(do ((j i (+ j 1))) ((= j (* 10 i)))

(let ((ds (digits j)))

(do ((k 0 (+ k 1))) ((= k 10))

(yield (undigits (append ds (list k) (reverse ds)))))))))

First we generate the ten 1-digit palindromes. Then the loop on *i* generates the 2-digit and 3-digit palindromes the first time through, the 4-digit and 5-digit palindromes the second time through, and so on. Each time through the *i* loop there are two inner loops, the loop on *j* generating even-length palindromes and the loop on *k* generating odd-length palindromes.

The `nth-palindrome`

function generates palindromes, returning the requested one:

`(define (nth-palindrome n)`

(let ((p (palindromes)))

(do ((n n (- n 1))) ((= n 1) (p)) (p))))

For instance:

`> (nth-palindrome 100)`

909

> (nth-palindrome 10000)

9000009

We used `digits`

, `undigits`

and `define-generator`

from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/AloHmePH.

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:

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

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

Another solution:

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:

//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

August 29th, 2014.c: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 :/ )