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