Palindrome de base más baja

16

Dado un número n, escriba una función que encuentre la base más pequeña, b ≥ 2como nun palíndromo en la base b. Por ejemplo, una entrada de 28debería devolver la base 3ya que la representación ternaria de 28 es 1001. Aunque 93es un palíndromo tanto en la base 2 como en la base 5, la salida debe ser 2desde 2 <5.

Entrada

Un entero positivo n < 2^31.

Salida

Devuelve la base más pequeña de b ≥ 2modo que la brepresentación de la base nsea ​​un palíndromo No asuma ceros a la izquierda.

Muestras (entrada => salida):

11 => 10

32 => 7

59 => 4

111 => 6

Reglas

El código más corto gana.

ntomlin1996
fuente
1
Creo que la base debería ser limitada.
Merienda
3
@Snack: ¿Cuál es el problema con las bases más altas? Independientemente de la elección de símbolos, un número base 1000 será un palíndromo o no.
Dennis
3
Anécdota interesante: n en la base n-1 siempre es 11 para n> = 2 y, por lo tanto, siempre es posible un palíndromo.
Cruncher
1
@Cruncher: npuede ser 1 y 2 no es un palíndromo base 1. Sin embargo, cada positivo nes un n + 1palíndromo base .
Dennis
1
@Dennis ¿Cómo es que 2 no es un palíndromo base 1? Son 11. O II, o 2 del símbolo que uses. En realidad, todos los números de la base 1 son palíndromos. Y dije n> = 2, porque no sé cuál sería la base 0 de la Tierra.
Cruncher

Respuestas:

4

CJam , 19 bytes / GolfScript, 23 bytes

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

o

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

Pruébalo en línea:

Ejemplos

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

Cómo funciona

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.

Para GolfScript, q~es ~, _es ., bes base, Wes -1y ges do.

Dennis
fuente
6

GolfScript, 20 caracteres

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

Un enfoque diferente con GolfScript que no sea Dennis '. Evita el costoso bucle explícito a favor de un operador de búsqueda . Pruebe en línea .

~: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
fuente
1
¡Inteligente! Sin embargo, esto no funciona si x = 1o x = 2. Ambos son x + 1palíndromos básicos de un solo dígito , por lo que x))deberían solucionarlo.
Dennis
4

Mathematica, 67 66 bytes

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

Realmente no puedo competir con GolfScript aquí en términos de tamaño de código, pero el resultado para 2 32 básicamente se devuelve instantáneamente.

Martin Ender
fuente
Agradable. Sin embargo, la función no tiene que nombrarse, ¿verdad? ¿Podrías usar una función sin nombre?
numbermaniac
(Además, ¿es posible usar PalindromeQpara la verificación inversa?)
numbermaniac
4

Japt , 12 9 bytes

A menos que me haya perdido un truco (¡es tarde!), Esto debería funcionar para todos los números hasta e incluyendo al menos 2**53-1 .

En mis pruebas (ciertamente limitadas y completamente aleatorias), he obtenido resultados hasta la base (!) Hasta ahora. No está mal si tenemos en cuenta JavaScript solamente soporta de forma nativa bases a .11601 310,515236

@ìX êê}a2

Intentalo

  • Gracias a ETH por señalar algo nuevo para mí que ahorró 3 bytes y aumentó considerablemente la eficiencia.

Explicación

Entrada implícita de entero U.

@     }a2

Comenzando con 2, devuelve el primer número que devuelve verdadero cuando se pasa por la siguiente función, Xsiendo el número actual

ìX

Convierte Uen una matriz de Xdígitos base .

êê

Prueba si esa matriz es un palíndromo.

Lanudo
fuente
1) si. ¡Culpa a la cerveza por esas bolas! : D 2) Agradable; Nunca se supo que N.ì(n)podría manejar bases mayores que 36. Gracias por eso.
Shaggy
Sí, el alfabeto de base 36 no importa N.ì(n)ya que estamos usando enteros sin procesar ;-)
ETHproductions
2

Pitón 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)

No estoy seguro de qué formato de entrada / salida quería la pregunta. Escribí una función. El código usa una entrada opcional bpara rastrear la base actual que está probando. Los whilebucles convierten el número en una lista de dígitos en la base b.

La última línea vuelve bsi les un palíndromo, y de forma recursiva intenta la siguiente de lo bcontrario. El truco de índice por booleano no funciona aquí porque causaría que ambas opciones se evaluaran independientemente del booleano, y la recursión nunca tocaría fondo.

xnor
fuente
1
Entonces, esto no funcionará con bases arbitrariamente altas, ¿verdad? Si la base más baja en la que un número tiene un palíndromo es como 10000, ¿obtendrá un desbordamiento de pila?
Cruncher
@Cruncher Depende de la implementación de Python. Se desbordará cuando se ejecute con CPython, pero no con Stackless Python , que optimiza las llamadas de cola y, por lo tanto, no tiene límite de recurrencia (aunque en realidad no lo he probado).
xnor
2

JavaScript, 88 bytes

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

Sin golf:

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
fuente
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/

Tenga en cuenta que esta implementación también funciona correctamente para bases grandes. Por ejemplo, f(10014)devuelve 1668 (10014 es 66 en la base 1668).

GOTO 0
fuente
Esto es bonito. Incluso puedes s/var b=2,c,d/b=d=2/ganar 6 bytes más;)
core1024
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
}

Usos dcpara formatear base. Lo complicado es que dcel formato es diferente para n> 16.

Casos de prueba:

$ ./lowestbasepalindrome.sh 11
10
$ ./lowestbasepalindrome.sh 32
7
$ ./lowestbasepalindrome.sh 59
4
$ ./lowestbasepalindrome.sh 111
6
$ 
Trauma digital
fuente
1

J - 28 char

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

Explicado:

  • #.inv~ - Expande el argumento izquierdo a la base en el argumento derecho.

  • (-.@-:|.@) - Devuelve 0 si la expansión es palindrómica y 1 en caso contrario.

  • (1+]^:) - Incremente el argumento correcto en uno si devolvimos 1, de lo contrario, no realice ninguna acción.

  • ^:_ - Repita el incremento anterior hasta que no realice ninguna acción.

  • &2 - Prepare el argumento correcto como 2, haciendo de esto una función de un argumento.

Ejemplos:

   #.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
Algoritmo de tiburón
fuente
2+1 i.~[#.inv"*(-:|.@)~2+i.por 27 bytes. (No quiero publicarlo por separado. Lo dejaré aquí.)
randomra
@randomra Contaría eso como 29 porque los trenes necesitan parens para usarse en línea; el mío salva a un personaje al tener una conjunción en el nivel superior.
algorithmshark
Creo que la posición de la mayoría en la puntuación es el conteo sin pares con cualquier función sin nombre, aunque siempre hay un argumento al respecto. De todos modos, lo dejaré aquí y todos pueden elegir cómo lo califica. :)
randomra
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]

Solución de tres años en 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]

Con algunas explicaciones:

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
fuente
1

Cáscara , 11 9 bytes

ḟoS=↔`B⁰2

Gracias @ Zgarb por -2!

Pruébalo en línea!

Explicación

ḟ(      )2  -- find least number ≥ 2 that satisfies:
     `B⁰    --   convert input to base (` flips arguments)
  S=↔       --   is palindrome (x == ↔x)
ბიმო
fuente
0

Nota: Pyth es más reciente que esta pregunta, por lo que esta respuesta no es elegible para ganar.

Pyth, 10 bytes

fq_jQTjQT2

Pruébalo aquí

isaacg
fuente
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
fuente
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
fuente
0

Mathematica 42 bytes

Una variación de la entrada de Martin Ender. Hace uso de IntegerReverse(disponible en la versión 10.3) que prescinde IntegerDigits.

(i=2;While[#~IntegerReverse~i !=#,i++];i)&
DavidC
fuente
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;}

Explicación:

Pruébalo aquí

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
fuente