21
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
15
  • 1
    \$\begingroup\$ I think base should be limited. \$\endgroup\$
    – Snack
    Commented May 22, 2014 at 5:36
  • 3
    \$\begingroup\$ @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. \$\endgroup\$
    – Dennis
    Commented May 22, 2014 at 5:58
  • 3
    \$\begingroup\$ Interesting anecdote: n in base n-1 is always 11 for n >= 2 and thus a palindrome is always possible. \$\endgroup\$
    – Cruncher
    Commented May 22, 2014 at 13:15
  • 1
    \$\begingroup\$ @Cruncher: n can be 1 and 2 is not a base 1 palindrome. However, every positive n is a base n + 1 palindrome. \$\endgroup\$
    – Dennis
    Commented May 22, 2014 at 13:51
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Cruncher
    Commented May 22, 2014 at 15:05

20 Answers 20

Reset to default
5
\$\begingroup\$

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
}?
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Dennis
    Commented May 22, 2014 at 13:58
4
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Nice. The function doesn't have to be named though, does it? Could you just use an unnamed function? \$\endgroup\$
    – numbermaniac
    Commented Sep 30, 2017 at 1:19
  • \$\begingroup\$ (Also, is it possible to use PalindromeQ for the reverse check?) \$\endgroup\$
    – numbermaniac
    Commented Sep 30, 2017 at 1:25
4
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Shaggy
    Commented Oct 2, 2017 at 15:51
  • \$\begingroup\$ Yeah, the base-36 alphabet doesn't matter for N.ì(n) since we're using raw integers ;-) \$\endgroup\$
    – ETHproductions
    Commented Oct 2, 2017 at 16:31
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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
}
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ 2+1 i.~[#.inv"*(-:|.@)~2+i. for 27 bytes. (Don't want to post it separately. I will just leave it here.) \$\endgroup\$
    – randomra
    Commented Apr 18, 2015 at 0:06
  • \$\begingroup\$ @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. \$\endgroup\$
    – algorithmshark
    Commented Apr 18, 2015 at 3:52
  • \$\begingroup\$ 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. :) \$\endgroup\$
    – randomra
    Commented Apr 18, 2015 at 4:49
1
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ This is nice. You can even s/var b=2,c,d/b=d=2/ to gain 6 more bytes ;) \$\endgroup\$
    – core1024
    Commented May 22, 2014 at 11:41
1
\$\begingroup\$

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
$
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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))})][1]

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)))][1]

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
                   ][1] #Return the first (i. e. smallest) for which it is
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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? \$\endgroup\$
    – Cruncher
    Commented May 22, 2014 at 12:57
  • \$\begingroup\$ @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). \$\endgroup\$
    – xnor
    Commented May 22, 2014 at 18:32
  • \$\begingroup\$ 82 bytes. \$\endgroup\$
    – 97.100.97.109
    Commented Oct 10, 2022 at 19:42
  • \$\begingroup\$ @97.100.97.109 Thanks, it turns out avoiding the and is even shorter \$\endgroup\$
    – xnor
    Commented Oct 10, 2022 at 23:34
0
\$\begingroup\$

Note: Pyth is newer than this question, so this answer is not eligible to win.

Pyth, 10 bytes

fq_jQTjQT2

Try it here.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Scala, 83 bytes

def s(n:Int)=(for(b<-2 to n;x=Integer.toString(n,b);if(x==x.reverse))yield(b)).min
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 8 bytes

¼[¼¾вÂQ#

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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)

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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)&
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Ruby, 43 bytes

-1 byte thanks to Steffan

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

Attempt This Online!

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ n.digits(_1) => n.digits _1 \$\endgroup\$
    – naffetS
    Commented Oct 10, 2022 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.