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.
Programming Praxis 
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; }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));Here’s the list of dual-base palindromes I got when I let my program run overnight:
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()); }Haskell: http://codepad.org/mTNnPb8l
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); } }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"; } } }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()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
October 21st, 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 <limits.h> #include <string.h> #include <stdlib.h> #include <stdio.h> typedef unsigned long t_IntegerType; const t_IntegerType k_MaximumValueOfIntegerType = UINT_MAX; size_t f_NumberOfDigits( const t_IntegerType p_number, const unsigned int p_base ) { size_t number_of_digits = 1; unsigned long divisor = p_base; while( p_number / divisor != 0 ) { number_of_digits ++; divisor *= p_base; } return number_of_digits; } 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; } void main( void ) { t_IntegerType i = 1; char *denary_representation_of_i = ( char* )malloc( sizeof( char ) * ( f_NumberOfDigits( k_MaximumValueOfIntegerType, 10 ) + 1 )); char *octal_representation_of_i = ( char* )malloc( sizeof( char ) * ( f_NumberOfDigits( k_MaximumValueOfIntegerType, 8 ) + 1 )); size_t k; const size_t number_of_spaces = ( strlen( "Base 10" ) < f_NumberOfDigits( k_MaximumValueOfIntegerType, 10 ))?f_NumberOfDigits( k_MaximumValueOfIntegerType, 10 ):strlen( "Base 10" ); p_PrintDateAndTime(); printf( "\n" ); printf( "Base 10" ); for( k = strlen( "Base 10" ); k < number_of_spaces; k ++ ) printf( " " ); printf( "\tBase 8\n" ); for( ; i < k_MaximumValueOfIntegerType; i ++ ) { sprintf( denary_representation_of_i, "%u", ( unsigned int )i ); if( f_IsPalindrome( denary_representation_of_i )) { sprintf( octal_representation_of_i, "%o", ( unsigned int )i ); if( f_IsPalindrome( octal_representation_of_i )) { printf( "%u", ( unsigned int )i ); for( k = strlen( denary_representation_of_i ); k < number_of_spaces; k ++ ) printf( " " ); printf( "\t%o\n", ( unsigned int )i ); } } } free( denary_representation_of_i ); free( octal_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 two seconds on Mac OS 9.2.2 (International English) (the solution interpreted using Leonardo IDE 3.4.1, where
UINT_MAXis equal to65,535).(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 :/ )