Sortie de la séquence Goodstein

18

(Cela peut être assez classique mais c'est mon premier post ici, donc je ne suis pas encore prêt pour les trucs de fantaisie)

La séquence de Goodstein est définie pour un numéro d'entrée comme suit:

Choisissez un nombre de départ n , soit b = 2 et répétez:

  • écrire n en notation b de base hériditaire
  • substituer tous les ( b ) s à ( b +1) s dans n et soustraire 1
  • sortie la nouvelle évaluation décimale de n
  • incrément b

La notation de base héréditaire est une décomposition d'un nombre où la base est le plus grand nombre à apparaître. Exemples:

  • 83 dans HB3: 3^(3+1)+2
  • 226 en HB2: 2^(2^(2+1))+2^(2+1)+2

Les séquences de Goodstein finissent toujours à 0 , mais elles ont tendance à devenir assez grandes assez rapidement, il n'est donc pas demandé de sortir la séquence complète.


Tâche:

Étant donné un numéro d'entrée dans un format raisonnable, votre travail consiste à sortir la séquence de Goodstein pour ce nombre au moins jusqu'à ce qu'il atteigne 10 ^ 25 ou 0

Exemples:

Input: 3
Output: 3, 3, 3, 2, 1, 0
Input: 13
Output: 13, 108, 1279, 16092, 280711, 5765998, 134219479, 3486786855, 100000003325, 3138428381103, 106993205384715, 3937376385706415, 155568095557821073, 6568408355712901455, 295147905179352838943, 14063084452067725006646, 708235345355337676376131, 37589973457545958193377292
Input: 38
Output: 38, 22876792454990

Détails:

  • Le numéro d'entrée peut être un tableau, une chaîne, un entier, tant qu'il est en base décimale
  • La sortie suit la même règle
  • La séparation des termes dans la sortie peut être des espaces, des sauts de ligne ou toute séparation raisonnable
  • Dès que la séquence dépasse 10 ^ 25, votre programme peut se fermer normalement, lever une erreur / exception ou continuer (aucune restriction)
  • Il s'agit de , donc la réponse la plus courte (en octets) l'emporte
  • Bien sûr, les échappatoires standard sont interdites
  • Exemple de travail non golfé en Python ici
BusyAnt
la source
2
Pourriez-vous ajouter étape par étape un cas de test?
Rod
5
Bienvenue chez PPCG! Joli premier défi!
FantaC
2
@ ØrjanJohansen Oui, le bogue est qu'il int(q/base.b), q%base.bdoit l'être q//base.b, q%base.b(ou simplement divmod(q, base.b)) pour éviter les erreurs en virgule flottante.
Anders Kaseorg
2
Est-ce que «au moins jusqu'à ce qu'il atteigne 10 ^ 25 ou 0» signifie que le programme peut continuer après avoir atteint 0 (vraisemblablement avec -1, -2, -3,…)?
Anders Kaseorg

Réponses:

3

Pyth , 28 26 octets

.V2JbL&bs.e*^hJykb_jbJ=ty

La nouvelle ligne de fin est significative.

Essayez-le en ligne! (Ce lien inclut un supplément Qnon requis par la version actuelle de Pyth.)

Comment ça fonctionne

.V2JbL&bs.e*^hJykb_jbJ=ty
.V2                          for b in [2, 3, 4, ...]:
   Jb                          assign J = b
     L                         def y(b):
      &b                         b and
                   jbJ             convert b to base J
                  _                reverse
         .e                        enumerated map for values b and indices k:
             hJ                      J + 1
            ^  yk                    to the power y(k)
           *     b                   times b
(newline)                      print Q (autoinitialized to the input)
                        y      y(Q)
                       t       subtract 1
                      =        assign back to Q

Il est important de le yredéfinir dans chaque itération de boucle pour éviter la mémorisation à travers les modifications apportées à la variable globale J.

Anders Kaseorg
la source
3

Haskell , 77 octets

(&2)est une fonction anonyme prenant Integeret renvoyant une liste (potentiellement très longue) de Integers, utilisez comme (&2) 13.

(&2)
n&b|n<0=[]|let _?0=0;e?n=(e+1)?div n b+mod n b*(b+1)^0?e=n:(0?n-1)&(b+1)

Essayez-le en ligne! (coupe à 10^25.)

Comment ça fonctionne

  • (&2)démarre la séquence avec base 2.
  • n&bcalcule la sous-séquence en commençant par le nombre net la base b.
    • Il s'arrête avec une liste vide si n<0, ce qui se produit généralement à l'étape suivante n==0.
    • Sinon, il précède nla liste renvoyée récursivement par l'expression (0?n-1)&(b+1).
  • ?est un opérateur de fonction local. 0?ndonne le résultat de la conversion nen base héréditaire b, puis de l'incrémentation de la base partout.
    • La conversion se reproduit avec la variable egardant la trace de l'exposant actuel. e?nconvertit le nombre n*b^e.
    • La récursivité s'arrête avec 0quand n==0.
    • Sinon, il se divise npar la base b.
      • (e+1)?div n b gère la récursivité pour le quotient et l'exposant supérieur suivant.
      • mod n b*(b+1)^0?egère le reste (qui est le chiffre correspondant à l'exposant actuel e), l'incrément de base et la conversion héréditaire de l'exposant actuel avec 0?e.
Ørjan Johansen
la source