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.
Programming Praxis 
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;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;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)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--; } }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:
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, "") }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 ]Alternative Haskell implementation of the last function:
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]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.
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)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
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.
August 5th, 2014.c:
#include "seal_bool.h" /* <http://GitHub.com/sealfin/C-and-C-Plus-Plus/blob/master/seal_bool.h> */ #include <string.h> #include <limits.h> #include <stdio.h> #include <stdlib.h> bool f_StringToNumber( const char * const p_string, unsigned int * const p_number ) /* Returns true if: * p_number != NULL; * p_string != NULL; * p_string points to a string comprised of – and only of – one or more digits in the range [ 0, 9 ]; * and the number represented by the string pointed to by p_string is ≤ UINT_MAX. */ { size_t i; unsigned long multiplier = 1, number = 0; if( p_number == NULL ) return false; if( p_string == NULL ) return false; i = strlen( p_string ); if( i == 0 ) return false; for( ; i > 0; i --, multiplier *= 10 ) { const char c = p_string[ i - 1 ]; if(( c >= '0' ) && ( c <= '9' )) { number += (( c - '0' ) * multiplier ); if( number > UINT_MAX ) return false; } else return false; } *p_number = number; return true; } size_t f_NumberOfDigits( const unsigned int p_number, const unsigned int p_base ) { size_t number_of_digits = 1; unsigned long divisor = p_base; while( p_number / divisor != 0 ) { number_of_digits ++; divisor *= p_base; } return number_of_digits; } #define M_NumberToString \ digit = p_number / divisor; \ if( digit < 10 ) \ p_string[ string_length ] = digit + '0'; \ else \ p_string[ string_length ] = digit - 10 + 'a'; \ string_length ++; \ p_number -= ( digit * divisor ); \ divisor /= p_base; void p_NumberToString( unsigned int p_number, const unsigned int p_base, char * const p_string ) { unsigned long divisor = 1; unsigned int digit; size_t string_length = 0; while( p_number / divisor != 0 ) divisor *= p_base; divisor /= p_base; M_NumberToString while( divisor != 0 ) { M_NumberToString } #undef M_NumberToString p_string[ string_length ] = '\0'; } bool f_IsPalindrome( const char * const p ) { size_t i = 0, k = strlen( p ) - 1; while( i < k ) { if( p[ i ] != p[ k ] ) return false; i ++; k --; } return true; } int main( const int argc, const char * const argv[] ) { bool error_occurred = false; unsigned int n; #ifdef LEONARDO const size_t index_of_argument = 0; if( argc != 1 ) error_occurred = true; #else const size_t index_of_argument = 1; if( argc != 2 ) error_occurred = true; #endif if( !error_occurred ) if( !f_StringToNumber( argv[ index_of_argument ], &n )) error_occurred = true; else if( n <= 2 ) error_occurred = true; printf( "\n" ); if( error_occurred ) printf( "This program will determine the minimal base ( 1, 36 ] in which the base 10 argument ( 2, %u ] passed to it is a palindrome.\n", ( unsigned int )UINT_MAX ); else { unsigned int b = 2; char *n_base_b = ( char* )malloc( sizeof( char ) * ( f_NumberOfDigits( UINT_MAX, 2 ) + 1 )); bool is_palindrome = false; for( ; b <= 36; b ++ ) { p_NumberToString( n, b, n_base_b ); if( f_IsPalindrome( n_base_b )) { is_palindrome = true; break; } } printf( "The base 10 number %u is ", n ); if( !is_palindrome ) printf( "not " ); printf( "a palindrome in base " ); if( !is_palindrome ) printf( "( 1, 36 ]" ); else printf( "%u: %s", b, n_base_b ); printf( ".\n" ); free( n_base_b ); } #ifndef LEONARDO printf( "\n" ); #endif return 0; }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 :/ )