## Two-Base Palindromes

### October 21, 2014

We begin with a function that determines if a number n is a palindrome when written in base b:

```(define (palin? n b)   (let ((ds (digits n b)))     (equal? ds (reverse ds))))```

Then we can test each number, starting from 1:

```> (do ((n 1 (+ n 1))) (#f)     (when (and (palin? n 10) (palin? n 8))       (display (digits n)) (display " ")       (display (digits n 8)) (display " ")       (newline))) (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)```

A better solution uses the generator of the previous exercise, modified to return palindromes in base b instead of base 10:

```(define-generator (palindromes b)   (do ((k 0 (+ k 1))) ((= k b))     (yield k))   (do ((i 1 (* i b))) (#f)     (do ((j i (+ j 1))) ((= j (* b i)))       (let ((ds (digits j b)))         (yield (undigits (append ds (reverse ds)) b))))     (do ((j i (+ j 1))) ((= j (* b i)))       (let ((ds (digits j b)))         (do ((k 0 (+ k 1))) ((= k b))           (yield (undigits (append ds (list k) (reverse ds)) b)))))))```

This is much faster:

```> (let ((p10 (palindromes 10)) (p8 (palindromes 8)))     (let loop ((a (p10)) (b (p8)))       (cond ((< a b) (loop (p10) b))             ((< b a) (loop a (p8)))             (else (display (digits a)) (display " ")                   (display (digits b 8)) (newline)                   (loop (p10) (p8)))))) () () (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)```

We used the `digits` and `undigits` functions and the `define-generator` macro from the Standard Prelude. You can run the two programs at http://programmingpraxis.codepad.org/qvEXpaBO and http://programmingpraxis.codepad.org/VgTeRuIn.

Pages: 1 2

### 10 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 String counter = "0";
private int digits = 1;
private boolean lastIncludedInMirror = true;

}

public long nextInDecimal() {
}

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();
}
if (String.valueOf(counter).length() > digits) {
if (lastIncludedInMirror) {
} else {
digits++;
}
lastIncludedInMirror = !lastIncludedInMirror;
}
return palindrome;
}

}

}
}
```
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;
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

9. sealfin said

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:

```Base 10	Base 8
1      	1
2      	2
3      	3
4      	4
5      	5
6      	6
7      	7
9      	11
121    	171
292    	444
333    	515
373    	565
414    	636
585    	1111
3663   	7117
8778   	21112
13131  	31513
13331  	32023
26462  	63536
26662  	64046
30103  	72627
30303  	73137```

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_MAX` is equal to `65,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 :/ )