# Lowest-Base Palindrome

Given a number $$\n\$$, write a program that finds the smallest base $$\b ≥ 2\$$ such that $$\n\$$ is a palindrome in base $$\b\$$. For example, an input of $$\28\$$ should return the base $$\3\$$ since $$\28_{10} = 1001_3\$$. Although $$\93\$$ is a palindrome in both base $$\2\$$ and base $$\5\$$, the output should be $$\2\$$ since $$\2<5\$$.

## Input

A positive integer $$\n < 2^{31}\$$.

## Output

Return the smallest base $$\b ≥ 2\$$ such that the base $$\b\$$ representation of $$\n\$$ is a palindrome. Do not assume any leading zeros.

Samples (input => output):

$$\11 \to 10\$$

$$\32 \to 7\$$

$$\59 \to 4\$$

$$\111 \to 6\$$

## Rules

The shortest code wins.

• I think base should be limited. May 22, 2014 at 5:36
• @Snack: What's the problem with higher bases? Independently of the choice of symbols, a base 1000 number will either be a palindrome or not. May 22, 2014 at 5:58
• Interesting anecdote: n in base n-1 is always 11 for n >= 2 and thus a palindrome is always possible. May 22, 2014 at 13:15
• @Cruncher: n can be 1 and 2 is not a base 1 palindrome. However, every positive n is a base n + 1 palindrome. May 22, 2014 at 13:51
• @Dennis How is 2 not a base 1 palindrome? It's 11. Or II, or 2 of whatever symbol you use. Actually all base 1 numbers are palindromes. And I said n >= 2, because I don't know what on earth base 0 would be. May 22, 2014 at 15:05

### GolfScript, 20 characters

~:x,2>{x\base.-1%=}?


A different approach with GolfScript other than Dennis'. It avoids the costly explicit loop in favour of a find operator. Try online.

~:x        # interpret and save input to variable x
,2>        # make a candidate list 2 ... x-1 (note x-1 is the maximum possible base)
{          # {}? find the item on which the code block yields true
x\       # push x under the item under investigation
base     # perform a base conversion
.-1%     # make a copy and reverse it
=        # compare reversed copy and original array
}?

• Clever! However, this does not work if x = 1 or x = 2. Both are single-digit, base x + 1 palindromes, so x)) should fix it. May 22, 2014 at 13:58

## Mathematica, 67 66 bytes

g[n_]:=For[i=1,1>0,If[(d=n~IntegerDigits~++i)==Reverse@d,Break@i]]


Can't really compete with GolfScript here in terms of code size, but the result for 232 is basically returned instantly.

• Nice. The function doesn't have to be named though, does it? Could you just use an unnamed function? Sep 30, 2017 at 1:19
• (Also, is it possible to use PalindromeQ for the reverse check?) Sep 30, 2017 at 1:25

# Japt, 12 9 bytes

Unless I've missed a trick (it's late!), this should work for all numbers up to and including at least 2**53-1.

In my (admittedly limited and entirely random) testing, I've gotten results up to base 11601 310,515(!) so far. Not too shabby when you consider JavaScript only natively supports bases 2 to 36.

@ìX êê}a2


Try it

• Thanks to ETH for pointing out something new to me that saved 3 bytes and increased the efficiency considerably.

## Explanation

Implicit input of integer U.

@     }a2


Starting with 2, return the first number that returns true when passed through the following function, with X being the current number

ìX


Convert U to an array of base X digits.

êê


Test if that array is a palindrome.

• 1) Yes. Blame the beer for that balls up! :D 2) Nice; never knew N.ì(n) could handle bases greater than 36. Thanks for that. Oct 2, 2017 at 15:51
• Yeah, the base-36 alphabet doesn't matter for N.ì(n) since we're using raw integers ;-) Oct 2, 2017 at 16:31

# CJam, 19 bytes / GolfScript, 23 bytes

q~:N;1{)_N\b_W%=!}g


or

~:N;1{).N\base.-1%=!}do


Try it online:

### Examples

$cjam base.cjam <<< 11; echo 10$ cjam base.cjam <<< 111; echo
6
$golfscript base.gs <<< 11 10$ golfscript base.gs <<< 111
6


### How it works

q~:N;   # Read the entire input, interpret it and save the result in “N”.
1       # Push 1 (“b”).
{       #
)     # Increment “b”.
_N\   # Duplicate “b”, push “N” and swap.
b     # Push the array of digits of “N” in base “b”.
_W%   # Duplicate the array and reverse it.
=!    # Compare the arrays.
}g      # If they're not equal, repeat the loop.


For GolfScript, q~ is ~, _ is ., b is base, W is -1 and g is do.

## JavaScript, 88 bytes

f=function(n){for(a=b='+1';a^a.split('').reverse().join('');a=n.toString(++b));return+b}


Ungolfed:

f = function(n) {
for(a = b = '+1'; // This is not palindrome, but equals 1 so we have at least one iteration
a ^ a.split('').reverse().join(''); // test a is palindrome
a = n.toString(++b));
return+b
}


# J - 28 char

#.inv~(-.@-:|.@)(1+]^:)^:_&2


Explained:

• #.inv~ - Expand left argument to the base in the right argument.

• (-.@-:|.@) - Return 0 if the expansion is palindromic, and 1 otherwise.

• (1+]^:) - Increment the right argument by one if we returned 1, else take no action.

• ^:_ - Repeat the above incrementing until it takes no action.

• &2 - Prepare the right argument as 2, making this a function of one argument.

Examples:

   #.inv~(-.@-:|.@)(1+]^:)^:_&2 (28)
3
#.inv~(-.@-:|.@)(1+]^:)^:_&2 every 93 11 32 59 111  NB. perform on every item
2 10 7 4 6
#.inv~(-.@-:|.@)(1+]^:)^:_&2 every 1234 2345 3456 4567 5678 6789
22 16 11 21 31 92

• 2+1 i.~[#.inv"*(-:|.@)~2+i. for 27 bytes. (Don't want to post it separately. I will just leave it here.) Apr 18, 2015 at 0:06
• @randomra I would count that as 29 because trains need parens to be used inline; mine saves a character by having a conjunction at the top level. Apr 18, 2015 at 3:52
• I think the majority's stand on scoring is the paren-less counting with any unnamed function though there is always an argument about this. Anyway, I will leave it here and everybody can choose how he/she scores it. :) Apr 18, 2015 at 4:49

# Javascript, 105 bytes

function f(n){for(var b=2,c,d;d=[];++b){for(c=n;c;c=c/b^0)d.push(c%b);if(d.join()==d.reverse())return b}}


JSFiddle: http://jsfiddle.net/wR4Wf/1/

Note that this implementation also works correctly for large bases. For example, f(10014) returns 1668 (10014 is 66 in base 1668).

• This is nice. You can even s/var b=2,c,d/b=d=2/ to gain 6 more bytes ;) May 22, 2014 at 11:41

# Bash + coreutils, 100 bytes

for((b=1;b++<=$1;)){ p=dc<<<${b}o$1p c=tac ((b<17))&&c=rev [ "$p" = "$c<<<$p" ]&&echo $b&&exit }  Uses dc to do base formatting. The tricky thing is dc's format is different for n > 16. Testcases: $ ./lowestbasepalindrome.sh 11
10
$./lowestbasepalindrome.sh 32 7$ ./lowestbasepalindrome.sh 59
4
$./lowestbasepalindrome.sh 111 6$


## R, 122 95 bytes

function(n)(2:n)[sapply(2:n,function(x){r={};while(n){r=c(n%%x,r);n=n%/%x};all(r==rev(r))})]


Three-year old solution at 122 bytes:

f=function(n)(2:n)[sapply(sapply(2:n,function(x){r=NULL;while(n){r=c(n%%x,r);n=n%/%x};r}),function(x)all(x==rev(x)))]


With some explanations:

f=function(n)(2:n)[sapply(
sapply(2:n,function(x){ #Return the decomposition of n in bases 2 to n
r=NULL
while(n){
r=c(n%%x,r)
n=n%/%x}
r
}
),
function(x)all(x==rev(x))) #Check if palindrome
] #Return the first (i. e. smallest) for which it is


# Husk, 11 9 bytes

ḟoS=↔B⁰2


Thanks @Zgarb for -2!

Try it online!

### Explanation

ḟ(      )2  -- find least number ≥ 2 that satisfies:
B⁰    --   convert input to base ( flips arguments)
S=↔       --   is palindrome (x == ↔x)


# Python 2, 79 bytes

def f(n,b=2):
l=[];m=n
while m:l+=m%b,;m/=b
return(l==l[::-1])*b or f(n,b+1)


Try it online!

-1 bytes thanks to 97.100.97.109

I'm not sure what input/output format the question wanted. I wrote a function. The code uses an optional input b to track the current base it's testing. The while loops converts the number to a list of digits in base b.

The last line returns b if l is a palindrome, and recursively tries the next b otherwise. The index-by-Boolean trick doesn't work here because it would cause both options to be evaluated regardless of the Boolean, and the recursion would never bottom out.

• So this will not work with arbitrarily high bases right? If the lowest base that a number has a palindrome is like 10000 then you'll get a stack overflow? May 22, 2014 at 12:57
• @Cruncher It depends of the implementation of Python. It will overflow when run with CPython, but not with Stackless Python, which does tail call optimization and so has no recursion limit (though I haven't actually tested it).
– xnor
May 22, 2014 at 18:32
• 82 bytes. Oct 10, 2022 at 19:42
• @97.100.97.109 Thanks, it turns out avoiding the and is even shorter
– xnor
Oct 10, 2022 at 23:34

# Pyth, 10 bytes

fq_jQTjQT2


Try it here.

# Scala, 83 bytes

def s(n:Int)=(for(b<-2 to n;x=Integer.toString(n,b);if(x==x.reverse))yield(b)).min


# 05AB1E, 8 bytes

¼[¼¾вÂQ#


Try it online!

# Perl 5, 84 + 1 (-p) = 85 bytes

$\=1;{++$\;my@r;$n=$_;do{push@r,$n%$\}while$n=int$n/$\;@t=@r;map$_-pop@t&&redo,@r}}{


Try it online!

# JavaScript 72 bytes

F=(n,b=2)=>eval(for(t=n,a=c="";t;t=t/b|0)a=t%b+a,c+=t%b)^a?F(n,b+1):b

console.log(F(11) == 10)

console.log(F(32) == 7)

console.log(F(59) == 4)

console.log(F(111) == 6)

# Mathematica 42 bytes

A variation of Martin Ender's entry. Makes use of IntegerReverse (made available in version 10.3) which dispenses with IntegerDigits.

(i=2;While[#~IntegerReverse~i !=#,i++];i)&


# Java 8, 103 bytes

n->{int b=1,l;for(String s;!(s=n.toString(n,++b)).equals(new StringBuffer(s).reverse()+""););return b;}


Explanation:

Try it here.

n->{                          // Method with integer as both parameter and return-type
int b=1,                    //  Base-integer, starting at 1
l;                      //  Length temp integer
for(String s;               //  Temp String
!(s=n.toString(n,++b))  //   Set the String to n in base b+1
//   (by first increase b by 1 using ++b)
.equals(new StringBuffer(s).reverse()+"");
//   And continue looping as long as it's not a palindrome
);                          //  End of loop
return b;                   //  Return the resulting base integer
}                             // End of method


# Jelly, 8 bytes

2b@ŒḂ¥1#


Try it online!

## How it works

2b@ŒḂ¥1# - Main link. Takes an integer n on the left
¥   - Group the previous 2 links into a dyad f(b, n):
b@      -   Convert n to base b
ŒḂ    -   Is palindrome?
2     1# - Count up b = 2, 3, 4, ... returning the first b that's true under f(b, n)


# Ruby, 43 bytes

-1 byte thanks to Steffan

->n{(2..).find{d=n.digits _1
d==d.reverse}}


Attempt This Online!

• n.digits(_1) => n.digits _1` Oct 10, 2022 at 19:54