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.

Pages: 1 2

15 Responses to “Generating Palindromes”

  1. matthew said

    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";
    }
    
  2. kernelbob said

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

  3. Nate said

    That is totally bananas. Good job kernelbob.

  4. kernelbob said

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

  5. matthew said

    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)
    
  6. matthew said

    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";
    }
    
  7. matthew said

    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";
    }
    
  8. svenningsson said

    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)
  9. matthew said

    Sorry about the multiple posts, my submissions got caught by the PP spam filter…

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

  11. matthew said

    @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)
    
  12. matthew said

    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))
    
  13. ickybyte said

    //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();

    }

  14. Andras said

    Smart and dummy in Java: http://codepad.org/kxgYZF2U

  15. Mark said
    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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: