Lowest-Base Palindrome

16

1

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.

ntomlin1996

Posted 11 years ago

Reputation: 263

This is OEIS A016026.

– Engineer Toast – 7 years ago

1I think base should be limited. – Snack – 11 years ago

No, I mean the base to check. For example, I can check up to base 10, or I can check up to base 36, which uses 0-9a-z. And I can even check up to base 127 which uses ASCII characters. You should limit base to check up. – Snack – 11 years ago

3@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. – Dennis – 11 years ago

Oh, I got it. Sorry. – Snack – 11 years ago

Are you asking for a function, or a full program?, And does it have to take command-line input or can I hardcode it?, Is the output printed or returned? – Οurous – 11 years ago

@Ourous: A function. Hardcoding is fine. Output is returned. – ntomlin1996 – 11 years ago

3Interesting anecdote: n in base n-1 is always 11 for n >= 2 and thus a palindrome is always possible. – Cruncher – 11 years ago

1@Cruncher: n can be 1 and 2 is not a base 1 palindrome. However, every positive n is a base n + 1 palindrome. – Dennis – 11 years ago

possible duplicate of Determine if an integer is a palindrome in a given radix (base)

– Digital Trauma – 11 years ago

1@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. – Cruncher – 11 years ago

@DigitalTrauma definitely related. Shaky whether it's a dupe or not – Cruncher – 11 years ago

@Cruncher: I didn't consider 1 a valid base. OK, there's apparently a unary number system, but the question rules base 1 out. – Dennis – 11 years ago

@Dennis Everyone knows unary! You've been doing it with your fingers since you learned to count! Anyway, my comment was more of an aside. I was going to say n >= 3, but since it was mathematically true for n=2, I decided to strengthen it a bit. – Cruncher – 11 years ago

@Cruncher: Exactly! That's why I did not provide an upper bound for the base. – ntomlin1996 – 11 years ago

Answers

4

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.

Dennis

Posted 11 years ago

Reputation: 196 637

6

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
}?         

Howard

Posted 11 years ago

Reputation: 23 109

1Clever! However, this does not work if x = 1 or x = 2. Both are single-digit, base x + 1 palindromes, so x)) should fix it. – Dennis – 11 years ago

4

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.

Shaggy

Posted 11 years ago

Reputation: 24 623

>

  • Yes. Blame the beer for that balls up! :D 2) Nice; never knew N.ì(n) could handle bases greater than 36. Thanks for that.
  • < – Shaggy – 7 years ago

    Yeah, the base-36 alphabet doesn't matter for N.ì(n) since we're using raw integers ;-) – ETHproductions – 7 years ago

    4

    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.

    Martin Ender

    Posted 11 years ago

    Reputation: 184 808

    Nice. The function doesn't have to be named though, does it? Could you just use an unnamed function? – numbermaniac – 7 years ago

    (Also, is it possible to use PalindromeQ for the reverse check?) – numbermaniac – 7 years ago

    2

    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.

    xnor

    Posted 11 years ago

    Reputation: 115 687

    1So 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? – Cruncher – 11 years ago

    @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 – 11 years ago

    2

    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
    }
    

    core1024

    Posted 11 years ago

    Reputation: 1 811

    1

    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)
    

    ბიმო

    Posted 11 years ago

    Reputation: 15 345

    1

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

    GOTO 0

    Posted 11 years ago

    Reputation: 752

    This is nice. You can even s/var b=2,c,d/b=d=2/ to gain 6 more bytes ;) – core1024 – 11 years ago

    1

    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
    

    plannapus

    Posted 11 years ago

    Reputation: 8 610

    1

    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
    $ 
    

    Digital Trauma

    Posted 11 years ago

    Reputation: 64 644

    1

    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
    

    algorithmshark

    Posted 11 years ago

    Reputation: 8 144

    2+1 i.~[#.inv"*(-:|.@)~2+i. for 27 bytes. (Don't want to post it separately. I will just leave it here.) – randomra – 10 years ago

    @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. – algorithmshark – 10 years ago

    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. :) – randomra – 10 years ago

    0

    05AB1E, 8 bytes

    ¼[¼¾вÂQ#
    

    Try it online!

    Justin Mariner

    Posted 11 years ago

    Reputation: 4 746

    0

    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!

    Xcali

    Posted 11 years ago

    Reputation: 7 671

    0

    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)

    DanielIndie

    Posted 11 years ago

    Reputation: 1 220

    0

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

    DavidC

    Posted 11 years ago

    Reputation: 24 524

    0

    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
    

    Kevin Cruijssen

    Posted 11 years ago

    Reputation: 67 575

    0

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

    Pyth, 10 bytes

    fq_jQTjQT2
    

    Try it here.

    isaacg

    Posted 11 years ago

    Reputation: 39 268

    0

    Scala, 83 bytes

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

    Dave Swartz

    Posted 11 years ago

    Reputation: 185