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.

About these ads

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 615 other followers

%d bloggers like this: