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.
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 :/ )