## Minimal Palindromic Base

### August 5, 2014

We’ll give three solutions, all based on the `digits` function from the Standard Prelude. The first solution simply tries each base starting from 2:

```(define (f1 n)   (let loop ((b 2))     (let ((ds (digits n b)))       (if (equal? ds (reverse ds)) b         (loop (+ b 1))))))```

```> (time (apply + (map f1 (range 3 10000)))) (time (apply + ...))     20 collections     1429 ms elapsed cpu time, including 7 ms collecting     1519 ms elapsed real time, including 9 ms collecting     85477680 bytes allocated, including 84524824 bytes reclaimed 1879426```

From the example on the previous page, it is clear that the answer will have two digits once b > n / 2, the first digit will be 1 and the second digit will be greater than 1, hence non-palindromic, until b = n − 1. Thus, a reasonable short-cut returns n − 1 as soon as the trial base is more than half of n:

```(define (f2 n)   (let loop ((b 2))     (if (< n (+ b b)) (- n 1)       (let ((ds (digits n b)))         (if (equal? ds (reverse ds)) b           (loop (+ b 1)))))))```

```> (time (apply + (map f2 (range 3 10000)))) (time (apply + ...))     15 collections     1236 ms elapsed cpu time, including 6 ms collecting     1332 ms elapsed real time, including 11 ms collecting     66262832 bytes allocated, including 63016616 bytes reclaimed 1879426```

A more clever analysis shows that if b divides n the result cannot be palindromic because the last digit will be 0, and the leading digit of the reversal will be suppressed. That gives us a third version of the function:

```(define (f3 n)   (let loop ((b 2))     (if (< n (+ b b)) (- n 1)       (if (zero? (modulo n b)) (loop (+ b 1))         (let ((ds (digits n b)))           (if (equal? ds (reverse ds)) b             (loop (+ b 1))))))))```

```> (time (apply + (map f3 (range 3 10000)))) (time (apply + ...))     15 collections     1410 ms elapsed cpu time, including 6 ms collecting     1557 ms elapsed real time, including 8 ms collecting     63336832 bytes allocated, including 62985144 bytes reclaimed 1879426```

That’s marginally faster than the basic brute force solution `f1`, but much slower than `f2` because the division inherent in the modulo operation is quite slow, so our attempt at optimization has backfired. On the other hand, if you look at the timings at http://programmingpraxis.codepad.org/kLrlWlns, `f3` is about the same as `f2`, presumably because the Scheme interpreter used there performs the modulo operation faster than the Scheme interpreter I use at home. On the other hand, the version at http://programmingpraxis.codepad.org/kLrlWlns spends a lot more time collecting garbage, suggesting that the way to make it run faster is to change the method of identifying palindromes.

Pages: 1 2

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

// 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]);
}
}

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

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