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.

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 634 other followers

%d bloggers like this: