## 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

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

Slightly better code (fixed a minor bug!)

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

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.

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

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

Haskell:

Alternative Haskell implementation of the last function:

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

A simpler version of the isPalindrome Haskell function:

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.

Racket:

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

In ruby …

Been a while good to be back …

Apologies if this appears twice.