18
\$\begingroup\$

(This might be quite classic but this is my first post here, so I'm not ready for the fancy stuff yet)

The Goodstein sequence is defined for an input number as follows:

Pick a starting number n, let b=2 and repeat:

  • write n in heriditary base b notation
  • substitute all the (b)s to (b+1)s in n and substract 1
  • output the new decimal evaluation of n
  • increment b

Hereditary Base notation is a decomposition of a number where the basis is the bigger number to appear. Examples:

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

Goodstein sequences always end up at 0, but they tend to first get quite big quite fast so it is not asked to output the complete sequence.


Task:

Given an input number in any reasonable format, your job is to output the Goodstein sequence for this number at least until it reaches 10^25 or 0

Examples:

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

Details:

  • Input number can be an array, a string, an integer, as long as it is in decimal base
  • Output follows the same rule
  • Separation of the terms in the output can be spaces, new-lines, or any reasonable separation
  • As soon as the sequence becomes larger than 10^25, your program may exit normally, throw an error/exception, or continue (no restriction)
  • This is , so the shortest answer (in bytes) wins
  • Of course, standard loopholes are forbidden
  • Python ungolfed working example here
\$\endgroup\$
  • 2
    \$\begingroup\$ Could you add an step-by-step of one test case? \$\endgroup\$ – Rod Dec 22 '17 at 15:12
  • 5
    \$\begingroup\$ Welcome to PPCG! Nice first challenge! \$\endgroup\$ – FantaC Dec 22 '17 at 15:42
  • 1
    \$\begingroup\$ Related. Related. \$\endgroup\$ – Martin Ender Dec 22 '17 at 15:52
  • 2
    \$\begingroup\$ @ØrjanJohansen Yeah, the bug is that int(q/base.b), q%base.b needs to be q//base.b, q%base.b (or simply divmod(q, base.b)) to avoid floating-point errors. \$\endgroup\$ – Anders Kaseorg Dec 22 '17 at 22:44
  • 2
    \$\begingroup\$ Does “at least until it reaches 10^25 or 0” mean the program is allowed to continue after it reaches 0 (presumably with −1, −2, −3, …)? \$\endgroup\$ – Anders Kaseorg Dec 23 '17 at 12:17
3
\$\begingroup\$

Pyth, 28 26 bytes

.V2JbL&bs.e*^hJykb_jbJ=ty

The trailing newline is significant.

Try it online! (This link includes an extra Q not needed by the current version of Pyth.)

How it works

.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

It’s important that y is redefined in each loop iteration to prevent memoization across changes to the global variable J.

\$\endgroup\$
3
\$\begingroup\$

Haskell, 77 bytes

(&2) is an anonymous function taking an Integer and returning a (potentially very long) list of Integers, use as (&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)

Try it online! (cuts off at 10^25.)

How it works

  • (&2) starts the sequence with base 2.
  • n&b calculates the subsequence starting with the number n and base b.
    • It halts with an empty list if n<0, which generally happens the step after n==0.
    • Otherwise, it prepends n to the list returned recursively by the expression (0?n-1)&(b+1).
  • ? is a local function operator. 0?n gives the result of converting n to hereditary base b, then incrementing the base everywhere.
    • The conversion recurses with the variable e keeping track of the current exponent. e?n converts the number n*b^e.
    • The recursion halts with 0 when n==0.
    • Otherwise, it divides n by the base b.
      • (e+1)?div n b handles the recursion for the quotient and next higher exponent.
      • mod n b*(b+1)^0?e handles the remainder (which is the digit corresponding to the current exponent e), the increment of base, and converting the current exponent hereditarily with 0?e.
\$\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.