## Minimal Palindromic Base

### August 5, 2014

We have a simple little problem today: Given an integer n > 2, find the minimum b > 1 for which n base b is a palindrome. For instance, n = 15 = 11112 = 1203 = 334 = 305 = 236 = 217 = 178 = 169 = 1510 = 1411 = 1312 = 1213 = 1114; of those, bases 2, 4 and 14 form palindromes, and the least of those is 2, so the correct answer is 2.

Your task is to write a program that calculates the smallest base for which a number n is a palindrome. 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.

Advertisement

Pages: 1 2

### 14 Responses to “Minimal Palindromic Base”

1. Perl routine to do this – takes values in from command line….

```use strict;
use warnings;
use feature qw(say);

foreach my \$no (@ARGV) {
my( \$b,\$str ) = minimal_palindromic_base( \$no );
say \$b,q(: ), \$str;
}

sub minimal_palindromic_base {
my \$n = shift;
foreach my \$b (2..(\$n-1)) {
my \$t = \$n;
my @Q;
while( \$t ) {
push @Q, \$q = \$t % \$b;
\$t = (\$t-\$q)/\$b;
}
my @A = @Q;
0 while (@A && shift @A == pop @A);
return (\$b, "@Q") if @A<=1;
}
return;
}

1;
```
2. Slightly better code (fixed a minor bug!)

```use strict;
use warnings;
use feature qw(say);

say sprintf '%10d: %5d: %s', \$_, minimal_palindromic_base( \$_ ) foreach @ARGV;

sub minimal_palindromic_base {
my \$n = shift;
foreach my \$b (2..(\$n-1)) {
my \$t = \$n;
my @Q;
while( \$t ) {
my \$q = \$t % \$b;
push @Q,\$q;
\$t = (\$t-\$q)/\$b;
}
my @A = @Q;
while( @A && (\$A[0] == \$A[-1]) ) {
shift @A;
pop @A;
}
return (\$b, "@Q") unless @A;
}
return;
}

1;
```
3. Mike said

The answer will have 2 digits when b > sqrt(n), and will be of the form kk. If we expand kk, we get k*b + k == n, which only has an integer solution when n % k == 0. So, for sqrt(n) > k >= 1, if n%k == 0 then b = n//k – 1 (where // means integer division).

```def minimal_palindromic_base(n):
if n <= 2: raise ValueError("n must be > 2")

k = 1
b = 2
while b*b < n:

# find 'digits' of n base b
nb = []
t = n
while t:
nb.append(t % b)
t //= b

# check to see if its a palindrome
if all(nb[i]==nb[-i-1] for i in range(len(nb)//2)):
return (nb, b)

# k is the largest b that divides n
if nb[0] == 0:
k = b

b += 1

# none of the b < sqrt(n) resulted in a palindrome, so calculate b from k
# k was initialized to 1, so if no b divides n the answer is [1,1], n-1
return ([k, k], n//k - 1)
```
4. matthew said

I was wondering if there was an easier way of going from a number in base n to a number in base n+1 that doing a full conversion. A quick look in Knuth showed there was – he describes a method only using subtraction, described by Walter Soden in 1953, for going from octal to decimal that can be generalized.

Incidentally, 0x1000000000000000 is [ 1 6 15 20 15 6 1 ], radix 1023 and 0x1234567890abcdef is [ 578043 565455 578043 ], radix 1506428.

```#include <stdio.h>
#include <stdlib.h>

typedef unsigned long T;

// Subtract b[0..n-1] from a[0..n-1], base r
void sub(T r, T *a, T *b, int n)
{
int k = 0; // k for karry
for (int i = 0; i < n; i++) {
T t = k + b[i];
if (a[i] >= t) {
a[i] -= t;
k = 0;
} else {
a[i] -= t-r;
k = 1;
}
}
}

// Convert from radix r-1 to radix r:
// subtract (radix r) most significant k digits from most significant
// k+1 digits, for k = 1..n-1
void upbase(T r, T *a, int n)
{
for (int i = 2; i < n; i++) {
sub(r, a+n-i-1, a+n-i, i);
}
}

bool ispalindrome(T *a, int n)
{
int j = 0, k = n-1;
while(j < k) {
if (a[j] != a[k]) return false;
j++; k--;
}
return true;
}

// print a number and the relevant radix
void p(T r, T *a, int n)
{
printf("[ ");
for (int i = 0; i < n; i++) {
printf("%lu ", a[n-i-1]);
}
printf("] [radix %lu]\n", r);
}

int main(int argc, char *argv[])
{
T n = strtoul(argv[1],NULL,16);
const int NDIGITS = 8*sizeof(T)+1;
T *a = new T[NDIGITS];
int N = 0;
while(n != 0) {
a[N++] = n&1;
n >>= 1;
}
a[N++] = 0;
for (T i = 3; ; i++) {
if (ispalindrome(a,N-1)) {
p(i-1,a,N-1);
break;
}
upbase(i,a,N);
while(a[N-2] == 0) N--;
}
}
```
5. matthew said

This version expects input in hex – change to “strtoul(argv[1],NULL,0)” to use decimal, octal or hex.

6. Nate Cook said

I’ve been having fun with these in Swift — here’s today’s:

```func minimalPalindromicBase(num: Int) -> (Int, String) {

func rebaseNumber(var num: Int, toBase base: Int) -> String {
func digit(n: Int) -> Character { return Character(UnicodeScalar(n + 48)) }
var result = ""
while num > base {
result = digit(num % base) + result
num /= base
}
return digit(num) + result
}

func palindrome(str: String) -> Bool {
let letters = Array(str)
for i in 0..<letters.count / 2 {
if letters[i] != letters[letters.count - (i + 1)] {
return false
}
}
return true
}

for i in 2..<num {
let rebased = rebaseNumber(num, toBase: i)
if palindrome(rebased) {
return (i, rebased)
}
}

return (0, "")
}
```
7. Jan Van lent said

Haskell:

```isPalindrome xs = and \$ zipWith (==) xs (reverse xs)

baseDigits _ 0 = []
baseDigits b n = r : (baseDigits b q)
where (q, r) = divMod n b

minimalPalindromicBase n =
head [ b | b <- [2..], isPalindrome \$ baseDigits b n ]
```
8. Jan Van lent said

Alternative Haskell implementation of the last function:

```-- alternative with helper functions for intermediate results

allBases n = [ (b, baseDigits b n) | b <- [2..] ]
basePalindromes n = filter (isPalindrome . snd) \$ allBases n
minimalPalindromicBaseAlt' n = head \$ basePalindromes n
minimalPalindromicBaseAlt n = fst \$ minimalPalindromicBase' n
```
9. Jan Van lent said

Another Python implementation. Similar to the Haskell code. No optimizations.

```def digits(n, b=10):
q = n
while q > 0:
q, r = q//b, q%b
yield r

def ispal(L):
return all(a == b for (a, b) in zip(L, reversed(L)))

def minimal_palindromic_base(n):
return [ b for b in range(2, n) if ispal(list(digits(n, b))) ][0]
```
10. Jan Van lent said

A simpler version of the isPalindrome Haskell function:

```isPalindrome xs = xs == reverse xs
```
11. Paul said

A version in Python. I could not find a method, that significantly performs better than brute force. I liked the upbase method from matthew and implemented a version in Python. Using this method is (in Python) slower than brute force.

```from itertools import count

def tobase(n, r):
"""return n in base r"""
res = []
while n:
n, rem = divmod(n, r)
res.append(rem)
return res

def is_palindrome(seq):
return seq == seq[::-1]

def min_palindrome_base(n):
for base in count(2):
if is_palindrome(tobase(n, base)):
return base

def upbase(r, a, n):
""" go from base r to base r+1
n is the decimal number, a is the number in base r
returns number in base r+1 and the new base
see Conversion of number systems and factorization by
Janusz Wlodarczyk, Djilali Behloul and Sui Sun Cheng
Malaya Journal of Matematik (2014)
"""
a = list(a) + [0]
m = len(a)
for k in range(m-2, -1, -1):
b = 0
for i in range(k, m-1):
a[i] -= a[i+1] + b
b = 0
if a[i] < 0:
b += 1
a[i] += r + 1
if a[i] < 0:
a[i] += r + 1
while a[-1] == 0:
a.pop()
return a, r + 1

def min_palindrome_base2(n):
base = 2
i = tobase(n, 2)
while 1:
if is_palindrome(i):
return base
i, base = upbase(base, i, n)
```
12. JP said

Racket:

```; Convert a decimal number n to base b
(define (rebase n b)
(let loop ([n n] [ls '()])
(if (= n 0)
ls
(loop (quotient n b)
(cons (remainder n b) ls)))))

; Find the minimal base b such that n in base b is a palindrome
(define (minimal-palindromic-base n)
(for/first ([b (in-naturals 2)]
#:when (let ([nb (rebase n b)])
(equal? nb (reverse nb))))
b))
```

Got some pretty pictures of the minimal palindromic bases over the first 1000 integers and a full write up too: Minimal palindromic base @ jverkamp.com

13. slabounty said

In ruby …

```def minimum_palindrome_base(i)
(2..i).each { |base| return base if palindrome(i.to_s(base)) }
return nil
end

def palindrome(s)
s == s.reverse
end

minimum_palindrome_base(15)
minimum_palindrome_base(20)
```

Been a while good to be back …
Apologies if this appears twice.

14. sealfin said

August 5th, 2014.c:

```#include "seal_bool.h" /* <http://GitHub.com/sealfin/C-and-C-Plus-Plus/blob/master/seal_bool.h> */
#include <string.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

bool f_StringToNumber( const char * const p_string, unsigned int * const p_number )
/*
Returns true if:
* p_number != NULL;
* p_string != NULL;
* p_string points to a string comprised of – and only of – one or more digits in the range [ 0, 9 ];
* and the number represented by the string pointed to by p_string is ≤ UINT_MAX.
*/
{
size_t i;
unsigned long multiplier = 1, number = 0;

if( p_number == NULL )
return false;
if( p_string == NULL )
return false;
i = strlen( p_string );
if( i == 0 )
return false;
for( ; i > 0; i --, multiplier *= 10 )
{
const char c = p_string[ i - 1 ];

if(( c >= '0' ) && ( c <= '9' ))
{
number += (( c - '0' ) * multiplier );
if( number > UINT_MAX )
return false;
}
else
return false;
}
*p_number = number;
return true;
}

size_t f_NumberOfDigits( const unsigned int 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;
}

#define  M_NumberToString                         \
digit = p_number / divisor;                     \
if( digit < 10 )                                \
p_string[ string_length ] = digit + '0';      \
else                                            \
p_string[ string_length ] = digit - 10 + 'a'; \
string_length ++;                               \
p_number -= ( digit * divisor );                \
divisor /= p_base;

void p_NumberToString( unsigned int p_number, const unsigned int p_base, char * const p_string )
{
unsigned long divisor = 1;
unsigned int digit;
size_t string_length = 0;

while( p_number / divisor != 0 )
divisor *= p_base;
divisor /= p_base;

M_NumberToString
while( divisor != 0 )
{
M_NumberToString
}
#undef M_NumberToString
p_string[ string_length ] = '\0';
}

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

int main( const int argc, const char * const argv[] )
{
bool error_occurred = false;
unsigned int n;

#ifdef LEONARDO
const size_t index_of_argument = 0;
if( argc != 1 )
error_occurred = true;
#else
const size_t index_of_argument = 1;
if( argc != 2 )
error_occurred = true;
#endif

if( !error_occurred )
if( !f_StringToNumber( argv[ index_of_argument ], &n ))
error_occurred = true;
else
if( n <= 2 )
error_occurred = true;
printf( "\n" );
if( error_occurred )
printf( "This program will determine the minimal base ( 1, 36 ] in which the base 10 argument ( 2, %u ] passed to it is a palindrome.\n", ( unsigned int )UINT_MAX );
else
{
unsigned int b = 2;
char *n_base_b = ( char* )malloc( sizeof( char ) * ( f_NumberOfDigits( UINT_MAX, 2 ) + 1 ));
bool is_palindrome = false;

for( ; b <= 36; b ++ )
{
p_NumberToString( n, b, n_base_b );
if( f_IsPalindrome( n_base_b ))
{
is_palindrome = true;
break;
}
}
printf( "The base 10 number %u is ", n );
if( !is_palindrome )
printf( "not " );
printf( "a palindrome in base " );
if( !is_palindrome )
printf( "( 1, 36 ]" );
else
printf( "%u: %s", b, n_base_b );
printf( ".\n" );
free( n_base_b );
}

#ifndef LEONARDO
printf( "\n" );
#endif

return 0;
}```

The solution is known to run on an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) on both Mac OS 9.2.2 (International English) (the solution interpreted using Leonardo IDE 3.4.1) and 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 :/ )