## 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 = 1111_{2} = 120_{3} = 33_{4} = 30_{5} = 23_{6} = 21_{7} = 17_{8} = 16_{9} = 15_{10} = 14_{11} = 13_{12} = 12_{13} = 11_{14}; 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.

Advertisements

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.