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

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.

August 5th, 2014.c: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 :/ )