16
\$\begingroup\$

Given a number n, write a function 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 the ternary representation of 28 is 1001. 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 => 10

32 => 7

59 => 4

111 => 6

Rules

The shortest code wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think base should be limited. \$\endgroup\$ – Snack May 22 '14 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 May 22 '14 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 May 22 '14 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 May 22 '14 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 May 22 '14 at 15:05

18 Answers 18

4
\$\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.

\$\endgroup\$
6
\$\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
}?         
\$\endgroup\$
  • 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 May 22 '14 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.

\$\endgroup\$
  • \$\begingroup\$ Nice. The function doesn't have to be named though, does it? Could you just use an unnamed function? \$\endgroup\$ – numbermaniac Sep 30 '17 at 1:19
  • \$\begingroup\$ (Also, is it possible to use PalindromeQ for the reverse check?) \$\endgroup\$ – numbermaniac Sep 30 '17 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.

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

Python 2 (83)

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

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.

\$\endgroup\$
  • 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 May 22 '14 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 May 22 '14 at 18:32
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
}
\$\endgroup\$
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).

\$\endgroup\$
  • \$\begingroup\$ This is nice. You can even s/var b=2,c,d/b=d=2/ to gain 6 more bytes ;) \$\endgroup\$ – core1024 May 22 '14 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
$ 
\$\endgroup\$
1
\$\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
\$\endgroup\$
  • \$\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 Apr 18 '15 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 Apr 18 '15 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 Apr 18 '15 at 4:49
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
\$\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)
\$\endgroup\$
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.

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

05AB1E, 8 bytes

¼[¼¾вÂQ#

Try it online!

\$\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!

\$\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)

\$\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)&
\$\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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.