Two-Base Palindromes

October 21, 2014

I wanted to do this exercise as a follow-up to the earlier exercise on generating palindromes, but didn’t get around to it until now.

Your task is to write a program that generates a list of numbers that are palindromes in base 10 and base 8; for instance 149694110 = 55535558. 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

9 Responses to “Two-Base Palindromes”

  1. A quick solution to perl (probably pipe the output through sort -n to get them fully in correct order)

    use strict;
    foreach (1..9999999) {
      my $o1 = sprintf '%o', (my $n1 = $_.(my $r = reverse $_));
      my $o2 = sprintf '%o', (my $n2 = $_.substr $r,1);
      printf "%20s %s\n", $n1, $o1 if $o1 eq reverse $o1;
      printf "%20s %s\n", $n2, $o2 if $o2 eq reverse $o2;
    }
    
  2. In Java, pretty cheesy when using StringBuilder.

    for(int i = 0; i < Integer.MAX_VALUE; i++)
    	if(new StringBuilder(""+i).reverse().toString().equals(""+i))
    		if(new StringBuilder(Integer.toOctalString(i)).reverse().toString().equals(Integer.toOctalString(i)))
    			System.out.println(i + " : " + Integer.toOctalString(i));
    
  3. programmingpraxis said

    Here’s the list of dual-base palindromes I got when I let my program run overnight:

    (1) (1)
    (2) (2)
    (3) (3)
    (4) (4)
    (5) (5)
    (6) (6)
    (7) (7)
    (9) (1 1)
    (1 2 1) (1 7 1)
    (2 9 2) (4 4 4)
    (3 3 3) (5 1 5)
    (3 7 3) (5 6 5)
    (4 1 4) (6 3 6)
    (5 8 5) (1 1 1 1)
    (3 6 6 3) (7 1 1 7)
    (8 7 7 8) (2 1 1 1 2)
    (1 3 1 3 1) (3 1 5 1 3)
    (1 3 3 3 1) (3 2 0 2 3)
    (2 6 4 6 2) (6 3 5 3 6)
    (2 6 6 6 2) (6 4 0 4 6)
    (3 0 1 0 3) (7 2 6 2 7)
    (3 0 3 0 3) (7 3 1 3 7)
    (2 0 7 7 0 2) (6 2 5 5 2 6)
    (6 2 8 8 2 6) (2 3 1 4 1 3 2)
    (6 6 0 0 6 6) (2 4 1 1 1 4 2)
    (1 4 9 6 9 4 1) (5 5 5 3 5 5 5)
    (1 9 3 5 3 9 1) (7 3 0 4 0 3 7)
    (1 9 7 0 7 9 1) (7 4 1 1 1 4 7)
    (4 1 9 8 9 1 4) (2 0 0 1 1 0 0 2)
    (5 5 3 6 6 3 5 5) (3 2 3 1 5 1 3 2 3)
    (1 3 0 5 3 5 0 3 1) (7 6 1 7 4 7 1 6 7)
    (5 3 2 8 9 8 2 3 5) (3 7 6 0 6 6 0 6 7 3)
    (7 1 9 8 4 8 9 1 7) (5 2 7 2 0 0 2 7 2 5)
    (7 9 9 5 3 5 9 9 7) (5 7 5 1 7 7 1 5 7 5)
    (1 8 2 0 3 3 0 2 8 1) (1 5 4 4 0 0 0 4 4 5 1)
    (2 4 6 4 5 5 4 6 4 2) (2 2 2 7 1 4 1 7 2 2 2)
    (4 4 2 4 9 9 4 2 4 4) (4 0 7 6 0 0 0 6 7 0 4)
    (4 4 8 0 8 8 0 8 4 4) (4 1 3 0 5 1 5 0 3 1 4)
    (4 6 3 7 3 3 7 3 6 4) (4 2 4 3 2 0 2 3 4 2 4)
    (2 0 8 5 5 5 5 5 8 0 2) (2 3 3 3 0 5 5 0 3 3 3 2)
    (9 4 0 2 9 8 9 2 0 4 9) (1 2 7 4 4 4 7 4 4 4 7 2 1)
    (9 4 4 6 6 6 6 6 4 4 9) (1 2 7 7 6 5 1 5 6 7 7 2 1)
    (2 9 4 3 7 8 8 7 3 4 9 2) (4 2 2 1 2 2 6 2 2 1 2 2 4)
    (3 9 0 8 9 4 4 9 8 0 9 3) (5 5 4 0 3 1 0 1 3 0 4 5 5)
    (5 2 2 7 5 2 9 2 5 7 2 2 5) (1 1 4 0 4 4 1 0 1 4 4 0 4 1 1)
    (5 8 5 3 1 4 3 4 1 3 5 8 5) (1 2 5 1 3 1 2 4 2 1 3 1 5 2 1)
    (7 7 1 2 1 5 0 5 1 2 1 7 7) (1 6 0 1 6 3 7 7 7 3 6 1 0 6 1)
    (1 3 9 9 4 6 8 8 6 4 9 9 3 1) (3 1 3 5 1 4 4 3 4 4 1 5 3 1 3)
    (2 8 7 1 9 5 5 5 5 9 1 7 8 2) (6 4 1 7 3 1 2 7 2 1 3 7 1 4 6)
    (3 4 9 2 6 9 9 9 9 6 2 9 4 3) (7 7 4 2 0 2 3 3 3 2 0 2 4 7 7)
    (1 1 2 7 4 5 3 8 3 5 4 7 2 1 1) (3 1 5 0 5 2 2 4 4 2 2 5 0 5 1 3)
    (1 8 5 8 5 0 9 9 9 0 5 8 5 8 1) (5 2 2 0 3 7 1 6 6 1 7 3 0 2 2 5)
    (2 2 4 7 8 5 6 4 6 5 8 7 4 2 2) (6 3 0 7 0 3 7 4 4 7 3 0 7 0 3 6)
    (3 5 9 9 3 4 1 1 1 4 3 9 9 5 3) (1 2 1 6 5 5 6 6 0 6 6 5 5 6 1 2 1)
    (3 9 3 0 7 3 4 1 4 3 7 0 3 9 3) (1 3 1 2 7 7 6 1 1 1 6 7 7 2 1 3 1)
    (6 6 6 5 5 1 5 3 5 1 5 5 6 6 6) (2 2 7 4 3 4 6 3 7 3 6 4 3 4 7 2 2)
    (6 8 3 1 1 3 4 7 4 3 1 1 3 8 6) (2 3 3 2 4 4 6 7 7 7 6 4 4 2 3 3 2)
    (6 8 5 8 5 4 4 1 4 4 5 8 5 8 6) (2 3 3 7 4 3 7 5 4 5 7 3 4 7 3 3 2)
    (3 3 2 3 9 0 2 4 7 4 2 0 9 3 2 3 3) (1 6 6 0 5 5 3 3 6 0 6 3 3 5 5 0 6 6 1)
    (4 5 5 3 4 4 3 0 5 0 3 4 4 3 5 5 4) (2 4 1 6 1 2 5 1 3 0 3 1 5 2 1 6 1 4 2)
    (4 5 5 7 6 2 1 0 3 0 1 2 6 7 5 5 4) (2 4 1 7 2 6 5 1 1 4 1 1 5 6 2 7 1 4 2)
    (5 7 2 3 4 0 1 7 2 7 1 0 4 3 2 7 5) (3 1 3 2 5 4 0 4 4 2 4 4 0 4 5 2 3 1 3)
    (7 0 3 3 3 3 4 1 5 1 4 3 3 3 3 0 7) (3 7 1 6 7 7 4 6 4 5 4 6 4 7 7 6 1 7 3)
    (8 4 1 7 2 3 6 1 5 1 6 3 2 7 1 4 8) (4 5 3 0 2 4 5 0 4 3 4 0 5 4 2 0 3 5 4)
    (8 4 1 9 9 1 4 8 4 8 4 1 9 9 1 4 8) (4 5 3 1 0 5 2 6 7 5 7 6 2 5 0 1 3 5 4)
    (9 6 8 7 6 8 2 7 4 7 2 8 6 7 8 6 9) (5 3 0 1 3 1 7 3 0 3 0 3 7 1 3 1 0 3 5)
    (1 0 5 0 8 0 4 6 9 9 6 4 0 8 0 5 0 1) (5 6 5 2 4 4 2 0 5 6 5 0 2 4 4 2 5 6 5)
    (1 3 6 0 5 3 3 5 8 8 5 3 3 5 0 6 3 1) (7 4 3 2 6 7 4 7 4 3 4 7 4 7 6 2 3 4 7)
    (1 2 1 9 0 7 1 1 6 9 6 1 1 7 0 9 1 2 1) (1 0 3 5 3 0 0 5 4 2 4 2 4 5 0 0 3 5 3 0 1)
    (2 4 4 5 4 2 0 0 7 9 7 0 0 2 4 5 4 4 2) (2 0 7 5 7 7 0 1 1 5 4 5 1 1 0 7 7 5 7 0 2)
    (2 6 5 0 6 2 6 9 3 9 3 9 6 2 6 0 5 6 2) (2 2 3 1 0 7 2 6 2 4 1 4 2 6 2 7 0 1 3 2 2)
    (3 6 7 6 0 7 7 1 6 6 6 1 7 7 0 6 7 6 3) (3 1 4 0 4 0 3 1 3 2 3 2 3 1 3 0 4 0 4 1 3)
    (3 8 0 0 0 0 3 1 5 0 5 1 3 0 0 0 0 8 3) (3 2 2 7 4 2 4 5 3 5 5 5 3 5 4 2 4 7 2 2 3)
    
  4. Andras said

    Java8 based on previous palindrom solution

    
    
    public static void main(String[] args) {
            generatePalindromesSmart(10000).stream()
                                           .filter(t -> isPalindrom(Integer.toOctalString(t)))
                                           .forEach(p -> System.out.println(p + " - " + Integer.toOctalString(p)));
    
        }
    
        private static boolean isPalindrom(String string) {
            return string.equals(new StringBuilder(string).reverse().toString());
        }
    
  5. Andras said

    Here is a better one in Java. Its uses two generators and works like “merging” them.

    
    
    public static void main(String[] args) {
            Palindromgenerator generator10 = new Palindromgenerator(10);
            Palindromgenerator generator8 = new Palindromgenerator(8);
            long p10 = generator10.nextInDecimal();
            long p8 = generator8.nextInDecimal();
            while (true) {
                if (p8 == p10) {
                    System.out.println(p10 + "(" + String.valueOf(p10).length() + ") " + Long.toString(p8, 8));
                    p8 = generator8.nextInDecimal();
                    p10 = generator10.nextInDecimal();
                } else if (p8 < p10) {
                    p8 = generator8.nextInDecimal();
                } else {
                    p10 = generator10.nextInDecimal();
                }
            }
        }
    
        public static class Palindromgenerator {
    
            private final int radix;
            private String counter = "0";
            private int digits = 1;
            private boolean lastIncludedInMirror = true;
    
            Palindromgenerator(int radix) {
                this.radix = radix;
            }
    
            public long nextInDecimal() {
                return Long.valueOf(next(), radix);
            }
    
            public String next() {
                String counterString = String.valueOf(counter);
                String palindrome;
                if (lastIncludedInMirror) {
                    palindrome =
                        counterString
                            + new StringBuilder(counterString.substring(0, counterString.length() - 1)).reverse()
                                                                                                       .toString();
                } else {
                    palindrome = counterString + new StringBuilder(counterString).reverse().toString();
                }
                counter = decToRad(radToDec(counter) + 1L);
                if (String.valueOf(counter).length() > digits) {
                    if (lastIncludedInMirror) {
                        counter = decToRad(radToDec(counter) / radix);
                    } else {
                        digits++;
                    }
                    lastIncludedInMirror = !lastIncludedInMirror;
                }
                return palindrome;
            }
    
            private Long radToDec(String rad) {
                return Long.valueOf(rad, radix);
            }
    
            private String decToRad(long dec) {
                return Long.toString(dec, radix);
            }
        }
    
  6. matthew said

    Generate the octal palindromes directly in binary and for each one check if we have one in base 10 as well.

    About 10 mins to go up to 21 octal digits (we then run out of bits). The highest seems to be 322742453555354247223 so actually the second half of that time doesn’t find anything.

    #include <iostream>
    #include <stdlib.h>
    #include <stdint.h>
    
    typedef uint64_t T;
    
    static inline T setoct(T s, int n, int d)
    {
      s &= ~(T(7)<<(3*n));
      s |= (T(d)<<(3*n));
      return s;
    }
    
    static inline int getoct(T s, int n) {
      return T(7) & (s>>(3*n));
    }
    
    static inline bool nextpal(uint64_t &s, int &len) {
      for (int n = (len+1)/2; n > 0; n--) {
        int d = getoct(s,n-1);
        if (d < 7) { 
          s = setoct(s,len-n,d+1);
          s = setoct(s,n-1,d+1);
          return true;
        } else {
          s = setoct(s,len-n,0);
          s = setoct(s,n-1,0);
        }
      }
      if (len == 21) {
        len = 0;
        return false;
      } else {
        s = setoct(s,0,1);
        s = setoct(s,len,1);
        len++;
        return true;
      }
    }
    
    bool ispal10(T p) {
      char buff[32];
      int len = 0;
      while(p != 0) {
        buff[len++] = p%10;
        p = p/10;
      }
      for (int i=0, j=len-1; i<j; i++,j--) {
        if(buff[i] != buff[j]) return false;
      }
      return true;
    }
      
    int main(int argc, char *argv[]) {
      uint64_t s = 0;
      int len = 0;
      while(true) {
        if (!nextpal(s,len)) break;
        if (ispal10(s)) {
          std::cout << std::dec << s << " " << std::oct << s << "\n";
        }
      }
    }
    
  7. matthew said

    Here’s a Python version, so we aren’t limited to what will fit in a uint64_t.
    Going a couple of hours now and up to 2650626939396260562 / 223107262414262701322.

    #!/usr/bin/python
    def setoct(s,n,d): return (s & ~(7<<(3*n))) | (d<<(3*n))
     
    def getoct(s,n): return 7 & (s>>(3*n))
     
    def nextpal(s,n):
      for i in range((n+1)//2,0,-1):
          d = getoct(s,i-1)
          if d < 7:
              s = setoct(s,n-i,d+1)
              s = setoct(s,i-1,d+1)
              return (s,n)
          else:
              s = setoct(s,n-i,0)
              s = setoct(s,i-1,0)
      s = setoct(s,0,1)
      s = setoct(s,n,1)
      return (s,n+1)
    
    def ispal10(n):
        s = str(n)
        i = 0; j = len(s)-1
        while (i<j):
            if s[i] != s[j]: return False
            i += 1; j -= 1
        return True
    
    def gen():
        s,n = 0,1
        while True:
            s,n = nextpal(s,n)
            if ispal10(s):
                print("%d %o"%(s,s))
    
    gen()
    
  8. matthew said

    After running for 4 days, my Python program has got well beyond 64 bit values and extended the list above with:

    9843207767677023489 1042320625005260232401
    32300361188116300323 3401017365665637101043
    44643103022030134644 4656141232552321416564
    77580854944945808577 10322464410401446422301
    202693712161217396202 25763605624542650636752
    371911868919868119173 50245203044744030254205
    375183597404795381573 50532677140404177623505
    375586160515061685573 50561160560606506116505
    379080765242567080973 51063153270407235136015
    473317002010200713374 63242276231313267224236
    494635531909135536494 65501623271217232610556
    552868393727393868255 73742270655755607224737
    556362998454899263655 74244263365556336244247
    579927810111018729975 76700353553235535300767
    2503498805115088943052 417334063462264360433714

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: