Palindrome de la base la plus basse

16

Étant donné un nombre n, écrivez une fonction qui trouve la plus petite base b ≥ 2telle qu'un npalindrome en base b. Par exemple, une entrée de 28devrait renvoyer la base 3puisque la représentation ternaire de 28 est 1001. Bien qu'il s'agisse d' 93un palindrome à la fois en base 2 et en base 5, la sortie doit être 2depuis 2 <5.

Contribution

Un entier positif n < 2^31.

Production

Renvoie la plus petite base b ≥ 2telle que la breprésentation de la base de nest un palindrome. Ne supposez pas de zéros non significatifs.

Échantillons (entrée => sortie):

11 => 10

32 => 7

59 => 4

111 => 6

Règles

Le code le plus court gagne.

ntomlin1996
la source
1
Je pense que la base devrait être limitée.
Snack
3
@Snack: Quel est le problème avec des bases plus élevées? Indépendamment du choix des symboles, un nombre de base 1000 sera ou non un palindrome.
Dennis
3
Anecdote intéressante: n dans la base n-1 est toujours 11 pour n> = 2 et donc un palindrome est toujours possible.
Cruncher
1
@Cruncher: npeut être 1 et 2 n'est pas un palindrome de base 1. Cependant, chaque positif nest un n + 1palindrome de base .
Dennis
1
@Dennis Comment 2 n'est-il pas un palindrome de base 1? C'est 11. Ou II, ou 2 de n'importe quel symbole que vous utilisez. En fait, tous les nombres de base 1 sont des palindromes. Et j'ai dit n> = 2, parce que je ne sais pas ce que serait la base terrestre 0.
Cruncher

Réponses:

4

CJam , 19 octets / GolfScript, 23 octets

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

ou

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

Essayez-le en ligne:

Exemples

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

Comment ça fonctionne

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.

Pour GolfScript, q~est ~, _est ., best base, West -1et gest do.

Dennis
la source
6

GolfScript, 20 caractères

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

Une approche différente avec GolfScript autre que Dennis '. Cela évite la boucle explicite coûteuse en faveur d'un opérateur de recherche . Essayez en ligne .

~: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
la source
1
Intelligent! Cependant, cela ne fonctionne pas si x = 1ou x = 2. Les deux sont des x + 1palindromes de base à un seul chiffre , il x))faut donc y remédier.
Dennis
4

Mathematica, 67 66 octets

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

Je ne peux pas vraiment rivaliser avec GolfScript ici en termes de taille de code, mais le résultat pour 2 32 est retourné instantanément.

Martin Ender
la source
Agréable. La fonction n'a pas besoin d'être nommée cependant, n'est-ce pas? Pourriez-vous simplement utiliser une fonction sans nom?
numbermaniac
(Aussi, est-il possible d'utiliser PalindromeQpour la vérification inverse?)
numbermaniac
4

Japt , 12 9 octets

Sauf si j'ai raté une astuce (il est tard!), Cela devrait fonctionner pour tous les numéros jusqu'à et y compris au moins 2**53-1.

Dans mes tests (certes limités et entièrement aléatoires), j'ai jusqu'à présent obtenu des résultats à la base (!). Pas trop mal si l' on considère JavaScript ne supporte nativement les bases pour .11601 310,515236

@ìX êê}a2

Essayez-le

  • Merci à ETH d' avoir signalé quelque chose de nouveau pour moi qui a permis d'économiser 3 octets et d'augmenter considérablement l'efficacité.

Explication

Saisie implicite d'entier U.

@     }a2

En commençant par 2, retourne le premier nombre qui renvoie vrai lorsqu'il est passé par la fonction suivante, avec Xétant le nombre actuel

ìX

Convertissez Uen un tableau de Xchiffres de base .

êê

Testez si ce tableau est un palindrome.

Hirsute
la source
1) Oui. Blâmez la bière pour ces boules! : D 2) Nice; Je ne savais pas qu'il N.ì(n)pouvait gérer des bases supérieures à 36. Merci pour ça.
Shaggy
Oui, l'alphabet base-36 n'a pas d'importance N.ì(n)car nous utilisons des entiers bruts ;-)
ETHproductions
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)

Je ne sais pas quel format d'entrée / sortie la question voulait. J'ai écrit une fonction. Le code utilise une entrée facultative bpour suivre la base actuelle qu'il teste. Les whileboucles convertissent le nombre en une liste de chiffres en base b.

La dernière ligne renvoie bif lest un palindrome et essaie récursivement la suivante bsinon. L'astuce d'indexation par booléen ne fonctionne pas ici car elle entraînerait l'évaluation des deux options indépendamment du booléen, et la récursivité ne serait jamais au plus bas.

xnor
la source
1
Donc, cela ne fonctionnera pas avec des bases arbitrairement élevées, n'est-ce pas? Si la base la plus basse qu'un nombre a un palindrome est comme 10000, alors vous obtiendrez un débordement de pile?
Cruncher
@Cruncher Cela dépend de l'implémentation de Python. Il débordera lorsqu'il sera exécuté avec CPython, mais pas avec Stackless Python , qui fait l'optimisation des appels de queue et n'a donc pas de limite de récursivité (bien que je ne l'ai pas testé).
xnor
2

JavaScript, 88 octets

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

Non 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
la source
1

Javascript, 105 octets

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/

Notez que cette implémentation fonctionne également correctement pour les grandes bases. Par exemple, f(10014)renvoie 1668 (10014 est 66 en base 1668).

GOTO 0
la source
C'est sympa. Vous pouvez même s/var b=2,c,d/b=d=2/gagner 6 octets supplémentaires;)
core1024
1

Bash + coreutils, 100 octets

for((b=1;b++<=$1;)){
p=`dc<<<${b}o$1p`
c=tac
((b<17))&&c=rev
[ "$p" = "`$c<<<$p`" ]&&echo $b&&exit
}

Utilise dcpour faire le formatage de base. La chose délicate est que dcle format est différent pour n> 16.

Testcases:

$ ./lowestbasepalindrome.sh 11
10
$ ./lowestbasepalindrome.sh 32
7
$ ./lowestbasepalindrome.sh 59
4
$ ./lowestbasepalindrome.sh 111
6
$ 
Traumatisme numérique
la source
1

J - 28 caractères

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

Expliqué:

  • #.inv~ - Développez l'argument de gauche à la base dans l'argument de droite.

  • (-.@-:|.@) - Retourne 0 si l'expansion est palindromique, et 1 sinon.

  • (1+]^:) - Incrémentez le bon argument de un si nous avons renvoyé 1, sinon ne prenez aucune mesure.

  • ^:_ - Répétez l'incrémentation ci-dessus jusqu'à ce qu'il ne fasse rien.

  • &2 - Préparez le bon argument en 2, ce qui en fait une fonction d'un seul argument.

Exemples:

   #.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
la source
2+1 i.~[#.inv"*(-:|.@)~2+i.pour 27 octets. (Je ne veux pas le poster séparément. Je vais le laisser ici.)
randomra
@randomra Je compterais cela comme 29 parce que les trains ont besoin de parens pour être utilisés en ligne; le mien sauve un personnage en ayant une conjonction au niveau supérieur.
algorithmshark
Je pense que la position de la majorité sur la notation est le comptage sans paren avec toute fonction sans nom, bien qu'il y ait toujours un argument à ce sujet. Quoi qu'il en soit, je vais le laisser ici et tout le monde peut choisir comment il / elle le marque. :)
randomra
1

R, 122 95 octets

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]

Solution vieille de trois ans à 122 octets:

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]

Avec quelques explications:

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
la source
1

Husk , 11 9 octets

ḟoS=↔`B⁰2

Merci @Zgarb pour -2!

Essayez-le en ligne!

Explication

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

Remarque: Pyth est plus récent que cette question, donc cette réponse n'est pas éligible pour gagner.

Pyth, 10 octets

fq_jQTjQT2

Essayez-le ici.

isaacg
la source
0

Scala, 83 octets

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

JavaScript 72 octets

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
la source
0

Mathematica 42 octets

Une variation de l'entrée de Martin Ender. Utilise IntegerReverse(mis à disposition dans la version 10.3) qui dispense de IntegerDigits.

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

Java 8, 103 octets

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

Explication:

Essayez-le ici.

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
la source