Goodstein Sequence

Goodstein sequences are sequences defined for a given counting number n by applying increasing bases to a representation of n after n has been used to construct a hereditary representation of that number, originally in base 2.

Goodstein Sequence is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Background

Start by defining the hereditary base-b representation of a number n. Write n as a sum of powers of b, staring with b = 2. For example, with n = 29, write 31 = 16 + 8 + 4 + 1. Now we write each exponent as a sum of powers of n, so as 2^4 + 2^3 + 2^1 + 2^0.

Continue by re-writing all of the current term's exponents that are still > b as a sum of terms that are <= b, using a sum of powers of b: so, n = 16 + 8 + 4 + 1 = 2^4 + 2^3 + 2 + 1 = 2^(2^2) + 2^(2 + 1) + 2 + 1.

If we consider this representation as a representation of a calculation with b = 2, we have the hereditary representation b^(b^b) + b^(b + 1) + b + 1.

Other integers and bases are done similarly. Note that an exponential term can be repeated up to (b - 1) times, so that, for example, if b = 5, 513 = b^3 + b^3 + b^3 + b^3 + b + b + 3 = 4 * b^3 + 2 * b + 3.

The Goodstein sequence for n, G(n) is then defined as follows:

The first term, considered the zeroeth term or G(n)(0), is always 0. The second term G(n)(1) is always n. For further terms, the m-th term G(n)(m) is defined by the following procedure:

   1. Write G(n)(m - 1) as a hereditary representation with base (m - 1).
   2. Calculate the results of using the hereditary representation found in step 1 using base m rather than (m - 1)
   3. Subtract 1 from the result calculated in step 2.

Task

• Create a function to calculate the Goodstein sequence for a given integer.

• Use this to show the first 10 values of Goodstein(n) for the numbers from 0 through 7.

• Find the nth term (counting from 0) of Goodstein(n) for n from 0 through 10.

Stretch task

• Find the nth term (counting from 0) of Goodstein(n) for n = 11 through 16.

See also

•   Wikipedia entry for Goodstein's theorem
•   OEIS Goodstein numbers such that a(n) = G_n(n), where G is the Goodstein function
•   [| "Googology site article " ]

ALGOL 68

Translation of: EasyLang – which is a translation of Phix

64-bit integers are required - adjust the INTEGER mode, if necessary.

BEGIN # Goodstein sequence - translation of Phix via EasyLang #

    MODE INTEGER = LONG INT;

    PROC bump = ( INTEGER v, b )INTEGER:
         BEGIN
            INTEGER n := v, res := 0;
            FOR i FROM 0 WHILE n > 0 DO
                INTEGER d = n MOD b;
                IF d > 0 THEN
                    res +:= d * ENTIER ( ( ( b + 1 ) ^ bump( i, b ) ) + 0.5 )
                FI;
                n OVERAB b
            OD;
            res
         END # bump # ;

    PROC goodstein = ( INTEGER n, INT maxterms )[]INTEGER:
         BEGIN
            [ 1 : maxterms ]INTEGER res;
            INT len res := 0;
            IF maxterms > 0 THEN
                res[ len res +:= 1 ] := n;
                WHILE len res < maxterms AND res[ len res ] /= 0 DO
                    INT cur len := len res;
                    res[ len res +:= 1 ] := bump( res[ cur len ], cur len + 1 ) - 1
                OD
            FI;
            res[ 1 : len res ]
         END # goodstein # ;

    BEGIN
        FOR i FROM 0 TO 7 DO
            []INTEGER gs = goodstein( i, 10 );
            print( ( "[" ) );
            FOR spos FROM LWB gs TO UPB gs DO print( ( " ", whole( gs[ spos ], 0 ) ) ) OD;
            print( ( " ]", newline ) )
        OD;
        print( ( newline ) );
        FOR i FROM 0 TO 10 DO
            []INTEGER h = goodstein( i, ( i + 1 ) );
            print( ( whole( h[ UPB h ], 0 ), newline ) )
        OD
    END
END

Output:

[ 0 ]
[ 1 0 ]
[ 2 2 1 0 ]
[ 3 3 3 2 1 0 ]
[ 4 26 41 60 83 109 139 173 211 253 ]
[ 5 27 255 467 775 1197 1751 2454 3325 4382 ]
[ 6 29 257 3125 46655 98039 187243 332147 555551 885775 ]
[ 7 30 259 3127 46657 823543 16777215 37665879 77777775 150051213 ]

0
0
1
2
83
1197
187243
37665879
20000000211
855935016215
44580503598539

EasyLang

Translation of: Phix

func bump n b .
   while n > 0
      d = n mod b
      if d > 0
         res += d * floor (pow (b + 1) bump i b + 0.5)
      .
      n = n div b
      i += 1
   .
   return res
.
func[] goodstein n maxterms .
   res[] = [ n ]
   while len res[] < maxterms and res[$] <> 0
      res[] &= bump res[$] (len res[] + 1) - 1
   .
   return res[]
.
for i = 0 to 7
   print goodstein i 10
.
print ""
for i = 0 to 10
   h[] = goodstein i (i + 1)
   print h[$]
.

Output:

[ 0 ]
[ 1 0 ]
[ 2 2 1 0 ]
[ 3 3 3 2 1 0 ]
[ 4 26 41 60 83 109 139 173 211 253 ]
[ 5 27 255 467 775 1197 1751 2454 3325 4382 ]
[ 6 29 257 3125 46655 98039 187243 332147 555551 885775 ]
[ 7 30 259 3127 46657 823543 16777215 37665879 77777775 150051213 ]

0
0
1
2
83
1197
187243
37665879
20000000211
855935016215
44580503598539

FreeBASIC

Translation of: Phix

Dim Shared As Double lastTerm

Function bump(ByVal n As Double, ByVal b As Double) As Double
    Dim As Double res = 0, i = 0
    
    While n > 0
        Dim As Integer d = n Mod b
        If d <> 0 Then res += d * Int((b + 1) ^ bump(i, b))
        n = Fix(n / b)
        i += 1
    Wend
    
    Return res
End Function

Function goodstein(ByVal n As Integer, ByVal maxterms As Integer = 10) As String
    Dim As String result = Str(n) 
    Dim As Double current = n
    Dim As Integer term = 1
    
    While term < maxterms AndAlso current <> 0
        current = Bump(current, term + 1) - 1
        result &= ", " & Str(current)
        term += 1
    Wend
    
    lastTerm = current
    Return result
End Function

' Main program
Print "Goodstein(n) sequence (first 10) for values of n from 0 through 7:"
For i As Integer = 0 To 7
    Print "Goodstein of"; i; ": "; goodstein(i)
Next i

Print !"\nThe Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through 15:"
For i As Integer = 0 To 15
    Dim sequence As String = Goodstein(i, i + 1)
    Dim inaccurate As String = IIf(i >= 12, " (inaccurate)", "")
    Print "Term " & i & " of Goodstein(" & i & "): " & Str(lastTerm) & inaccurate
Next i

Sleep

Output:

Goodstein(n) sequence (first 10) for values of n from 0 through 7:
Goodstein of 0: 0
Goodstein of 1: 1, 0
Goodstein of 2: 2, 2, 1, 0
Goodstein of 3: 3, 3, 3, 2, 1, 0
Goodstein of 4: 4, 26, 41, 60, 83, 109, 139, 173, 211, 253
Goodstein of 5: 5, 27, 255, 467, 775, 1197, 1751, 2454, 3325, 4382
Goodstein of 6: 6, 29, 257, 3125, 46655, 98039, 187243, 332147, 555551, 885775
Goodstein of 7: 7, 30, 259, 3127, 46657, 823543, 16777215, 37665879, 77777775, 150051213

The Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through 15:
Term0 of Goodstein(0): 0
Term1 of Goodstein(1): 0
Term2 of Goodstein(2): 1
Term3 of Goodstein(3): 2
Term4 of Goodstein(4): 83
Term5 of Goodstein(5): 1197
Term6 of Goodstein(6): 187243
Term7 of Goodstein(7): 37665879
Term8 of Goodstein(8): 20000000211
Term9 of Goodstein(9): 855935016215
Term10 of Goodstein(10): 44580503598539
Term11 of Goodstein(11): 2120126221988686
Term12 of Goodstein(12): 1.555680955578126e+017 (inaccurate)
Term13 of Goodstein(13): 6.568408355712902e+018 (inaccurate)
Term14 of Goodstein(14): 2.951479051793584e+020 (inaccurate)
Term15 of Goodstein(15): 1.406308445207078e+022 (inaccurate)

Java

import java.math.BigInteger;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public final class GoodsteinSequence {

	public static void main(String[] args) {
		System.out.println("The Goodstein(n) sequence, up to the first 10 terms, for values of n from 0 to 7:");
		IntStream.rangeClosed(0, 7).forEach( i -> {
		    System.out.println("Goodstein of %d: %s".formatted(i, goodstein(i, 10)));
		} );
		
		System.out.println("\nThe nth term, zero based, of Goodstein(n), for values of n from 0 to 16:");
		IntStream.rangeClosed(0, 16).forEach( i -> {
		    System.out.println("Term %2d of Goodstein(%2d): %s".formatted(i, i, goodstein(i, i + 1).get(i)));
		} );
	}
	
	private static List<BigInteger> goodstein(int number, int maxTerms) {
	    BigInteger current = BigInteger.valueOf(number);
	    List<BigInteger> result = Stream.of( current ).collect(Collectors.toList());
	    int term = 1;	    
	    while ( term < maxTerms && current.signum() > 0 ) {
	        current = bump(current, term + 1).subtract(BigInteger.ONE);
	        result.addLast(current);
	        term += 1;
	    }	    
	    return result;
	}
	
	private static BigInteger bump(BigInteger number, int base) {
		BigInteger bigBase = BigInteger.valueOf(base);
		BigInteger result = BigInteger.ZERO;
		int i = 0;
		while ( number.signum() > 0 ) {
			BigInteger remainder = number.mod(bigBase);
			number = number.divide(bigBase);
			if ( remainder.signum() > 0 ) {
				final int exponent = bump(BigInteger.valueOf(i), base).intValueExact();
				result = result.add(remainder.multiply(bigBase.add(BigInteger.ONE).pow(exponent)));
			}
			i += 1;
		}
		return result;
	}

}

Output:

The Goodstein(n) sequence, up to the first 10 terms, for values of n from 0 to 7:
Goodstein of 0: [0]
Goodstein of 1: [1, 0]
Goodstein of 2: [2, 2, 1, 0]
Goodstein of 3: [3, 3, 3, 2, 1, 0]
Goodstein of 4: [4, 26, 41, 60, 83, 109, 139, 173, 211, 253]
Goodstein of 5: [5, 27, 255, 467, 775, 1197, 1751, 2454, 3325, 4382]
Goodstein of 6: [6, 29, 257, 3125, 46655, 98039, 187243, 332147, 555551, 885775]
Goodstein of 7: [7, 30, 259, 3127, 46657, 823543, 16777215, 37665879, 77777775, 150051213]

The nth term, zero based, of Goodstein(n), for values of n from 0 to 10:
Term  0 of Goodstein( 0): 0
Term  1 of Goodstein( 1): 0
Term  2 of Goodstein( 2): 1
Term  3 of Goodstein( 3): 2
Term  4 of Goodstein( 4): 83
Term  5 of Goodstein( 5): 1197
Term  6 of Goodstein( 6): 187243
Term  7 of Goodstein( 7): 37665879
Term  8 of Goodstein( 8): 20000000211
Term  9 of Goodstein( 9): 855935016215
Term 10 of Goodstein(10): 44580503598539
Term 11 of Goodstein(11): 2120126221988686
Term 12 of Goodstein(12): 155568095557812625
Term 13 of Goodstein(13): 6568408355712901455
Term 14 of Goodstein(14): 295147905179358418247
Term 15 of Goodstein(15): 14063084452070776884879
Term 16 of Goodstein(16): 2771517379996516970665566613559367879596937714713289695169887161862950129194382447127464877388711781205972046374648603545513430106433206876557475731408608398953667881600740852227698037876781766310900319669456854530159244376159780346700931210394158247781113134808720678004134212529413831368888355854503034587880113970541681685966414888841800498150131839091463034162026108960280455620621355407543489960326268155088833218122810217973039385643494213235664908254695964740257569988152978579630435471016976693529875691083071137361386386918409765002837648351746984484967203877495399596876291343126699827442908994036031608979805166915596436929638418152127561722561465793969723556331679336828840983098559789555364076924597258115780567651772009250336359472037679350612341393780002377587368649157608579801815531133644879180066181854487069796160774056572568941004114162614925

JavaScript

Works with: NodeJS 16.14.2

Translation of: Java

// Goodstein Sequence implementation in JavaScript

function main() {
    console.log("The Goodstein(n) sequence, up to the first 10 terms, for values of n from 0 to 7:");
    for (let i = 0; i <= 7; i++) {
        console.log(`Goodstein of ${i}: ${goodstein(i, 10).join(', ')}`);
    }
    
    console.log("\nThe nth term, zero based, of Goodstein(n), for values of n from 0 to 16:");
    for (let i = 0; i <= 16; i++) {
        const sequence = goodstein(i, i + 1);
        console.log(`Term ${i.toString().padStart(2)} of Goodstein(${i.toString().padStart(2)}): ${sequence[i]}`);
    }
}

function goodstein(number, maxTerms) {
    let current = BigInt(number);
    const result = [current];
    let term = 1;
    
    while (term < maxTerms && current > 0n) {
        current = bump(current, term + 1) - 1n;
        result.push(current);
        term += 1;
    }
    
    return result;
}

function bump(number, base) {
    const bigBase = BigInt(base);
    let result = 0n;
    let i = 0;
    
    while (number > 0n) {
        const remainder = number % bigBase;
        number = number / bigBase;
        
        if (remainder > 0n) {
            const exponent = Number(bump(BigInt(i), base));
            result = result + remainder * (bigBase + 1n) ** BigInt(exponent);
        }
        i += 1;
    }
    
    return result;
}

// Run the main function
main();

Output:

The Goodstein(n) sequence, up to the first 10 terms, for values of n from 0 to 7:
Goodstein of 0: 0
Goodstein of 1: 1, 0
Goodstein of 2: 2, 2, 1, 0
Goodstein of 3: 3, 3, 3, 2, 1, 0
Goodstein of 4: 4, 26, 41, 60, 83, 109, 139, 173, 211, 253
Goodstein of 5: 5, 27, 255, 467, 775, 1197, 1751, 2454, 3325, 4382
Goodstein of 6: 6, 29, 257, 3125, 46655, 98039, 187243, 332147, 555551, 885775
Goodstein of 7: 7, 30, 259, 3127, 46657, 823543, 16777215, 37665879, 77777775, 150051213

The nth term, zero based, of Goodstein(n), for values of n from 0 to 16:
Term  0 of Goodstein( 0): 0
Term  1 of Goodstein( 1): 0
Term  2 of Goodstein( 2): 1
Term  3 of Goodstein( 3): 2
Term  4 of Goodstein( 4): 83
Term  5 of Goodstein( 5): 1197
Term  6 of Goodstein( 6): 187243
Term  7 of Goodstein( 7): 37665879
Term  8 of Goodstein( 8): 20000000211
Term  9 of Goodstein( 9): 855935016215
Term 10 of Goodstein(10): 44580503598539
Term 11 of Goodstein(11): 2120126221988686
Term 12 of Goodstein(12): 155568095557812625
Term 13 of Goodstein(13): 6568408355712901455
Term 14 of Goodstein(14): 295147905179358418247
Term 15 of Goodstein(15): 14063084452070776884879
Term 16 of Goodstein(16): 2771517379996516970665566613559367879596937714713289695169887161862950129194382447127464877388711781205972046374648603545513430106433206876557475731408608398953667881600740852227698037876781766310900319669456854530159244376159780346700931210394158247781113134808720678004134212529413831368888355854503034587880113970541681685966414888841800498150131839091463034162026108960280455620621355407543489960326268155088833218122810217973039385643494213235664908254695964740257569988152978579630435471016976693529875691083071137361386386918409765002837648351746984484967203877495399596876291343126699827442908994036031608979805166915596436929638418152127561722561465793969723556331679336828840983098559789555364076924597258115780567651772009250336359472037679350612341393780002377587368649157608579801815531133644879180066181854487069796160774056572568941004114162614925

jq

Works with gojq, the Go implementation of jq

Adapted from Wren

This entry assumes infinite-precision integer arithmetic as provided by the Go implementation of jq.

# To take advantage of gojq's infintite-precision integer arithmetic:
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);

# If $j is 0, then an error condition is raised;
# otherwise, assuming infinite-precision integer arithmetic,
# if the input and $j are integers, then the result will be a pair of integers.
def divmod($j):
  . as $i
  | ($i % $j) as $mod
  | [($i - $mod) / $j, $mod] ;

# Given non-negative integer $n and base b$, return hereditary representation
# consisting of tuples (j, k) such that the sum of all (j * b^(evaluate(k; b)) == n.
def decompose($n; $b):
  if $n < $b then $n
  else { n: $n, decomp: [], e: 0 }
  | until (.n == 0; 
      (.n | divmod($b)) as $t
      | .n = $t[0]
      | $t[1] as $r
      | if $r > 0 then .decomp += [[$r, decompose(.e; $b)]] end
      | .e += 1 )
  | .decomp
  end;

# Evaluate hereditary representation $d under base $b.
def evaluate($d; $b):
  if $d|type == "number" then $d
  else reduce $d[] as [$j, $k] (0; 
        . + $j * ($b|power(evaluate($k; $b))) )
  end ;

# Return a vector of up to $limitlength values of the Goodstein sequence for $n.
def goodstein($n; $limitLength):
  { seq: [], b: 2, $n }
   | until (.n == false or (.seq|length) >= $limitLength ;
        .seq += [.n]
        | if .n == 0 then .n = false
          else decompose(.n; .b) as $d
          | .b += 1
          | .n = evaluate($d; .b) - 1
          end )
  | .seq;

# Get the $nth term of the Goodstein($n) sequence counting from 0
def a266201($n): goodstein($n; $n+1)[-1];

### The tasks
"Goodstein(n) sequence (first 10) for values of n in [0, 7]:",
(range (0;8) | "Goodstein of \(.): \(goodstein(.; 10))"),

"\nThe nth term of Goodstein(n) sequence counting from 0, for values of n in [0, 16]:",
( range (0;17) | "Term \(.) of Goodstein(\(.)): \(a266201(.))" )

Output:

Command invocation: gojq -n -f goodstein-sequence.jq

Goodstein(n) sequence (first 10) for values of n in [0, 7]:
Goodstein of 0: [0]
Goodstein of 1: [1,0]
Goodstein of 2: [2,2,1,0]
Goodstein of 3: [3,3,3,2,1,0]
Goodstein of 4: [4,26,41,60,83,109,139,173,211,253]
Goodstein of 5: [5,27,255,467,775,1197,1751,2454,3325,4382]
Goodstein of 6: [6,29,257,3125,46655,98039,187243,332147,555551,885775]
Goodstein of 7: [7,30,259,3127,46657,823543,16777215,37665879,77777775,150051213]

The nth term of Goodstein(n) sequence counting from 0, for values of n in [0, 16]:
Term 0 of Goodstein(0): 0
Term 1 of Goodstein(1): 0
Term 2 of Goodstein(2): 1
Term 3 of Goodstein(3): 2
Term 4 of Goodstein(4): 83
Term 5 of Goodstein(5): 1197
Term 6 of Goodstein(6): 187243
Term 7 of Goodstein(7): 37665879
Term 8 of Goodstein(8): 20000000211
Term 9 of Goodstein(9): 855935016215
Term 10 of Goodstein(10): 44580503598539
Term 11 of Goodstein(11): 2120126221988686
Term 12 of Goodstein(12): 155568095557812625
Term 13 of Goodstein(13): 6568408355712901455
Term 14 of Goodstein(14): 295147905179358418247
Term 15 of Goodstein(15): 14063084452070776884879
Term 16 of Goodstein(16): 2771517379996516970665566613559367879596937714713289695169887161862950129194382447127464877388711781205972046374648603545513430106433206876557475731408608398953667881600740852227698037876781766310900319669456854530159244376159780346700931210394158247781113134808720678004134212529413831368888355854503034587880113970541681685966414888841800498150131839091463034162026108960280455620621355407543489960326268155088833218122810217973039385643494213235664908254695964740257569988152978579630435471016976693529875691083071137361386386918409765002837648351746984484967203877495399596876291343126699827442908994036031608979805166915596436929638418152127561722561465793969723556331679336828840983098559789555364076924597258115780567651772009250336359472037679350612341393780002377587368649157608579801815531133644879180066181854487069796160774056572568941004114162614925

Julia

""" Given nonnegative integer n and base b, return hereditary representation consisting of
    tuples (j, k) such that the sum of all (j * base^(evaluate(k)) = n.
"""
function decompose(n, b)
    if n < b
        return n
    end
    decomp = Vector{Union{typeof(n), Vector}}[]
    e = typeof(n)(0)
    while n != 0
        n, r = divrem(n, b)
        if r > 0
            push!(decomp, [r, decompose(e, b)])
        end
        e += 1
    end
    return decomp
end

""" Evaluate hereditary representation d under base b """
evaluate(d, b) = d isa Integer ? d : sum(j * b ^ evaluate(k, b) for (j, k) in d)

""" Return a vector of up to limitlength values of the Goodstein sequence for n """
function goodstein(n, limitlength = 10)
    seq = typeof(n)[]
    b = typeof(n)(2)
    while length(seq) < limitlength
        push!(seq, n)
        n == 0 && break
        d = decompose(n, b)
        b += 1
        n = evaluate(d, b) - 1
    end
    return seq
end

"""Get the Nth term of Goodstein(n) sequence counting from 0, see https://oeis.org/A266201"""
A266201(n) = last(goodstein(BigInt(n), n + 1))

println("Goodstein(n) sequence (first 10) for values of n from 0 through 7:")
for i in 1:7
    println("Goodstein of $i: $(goodstein(i))")
end
println("\nThe Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through 16:")
for i in big"1":16
    println("Term $i of Goodstein($i}): $(A266201(i))")
end

Output:

Goodstein(n) sequence (first 10) for values of n from 0 through 7:
Goodstein of 0: [0]
Goodstein of 1: [1, 0]
Goodstein of 2: [2, 2, 1, 0]
Goodstein of 3: [3, 3, 3, 2, 1, 0]
Goodstein of 4: [4, 26, 41, 60, 83, 109, 139, 173, 211, 253]
Goodstein of 5: [5, 27, 255, 467, 775, 1197, 1751, 2454, 3325, 4382]
Goodstein of 6: [6, 29, 257, 3125, 46655, 98039, 187243, 332147, 555551, 885775]
Goodstein of 7: [7, 30, 259, 3127, 46657, 823543, 16777215, 37665879, 77777775, 150051213]

The Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through 16:
Term 0 of Goodstein(0): 0
Term 1 of Goodstein(1): 0
Term 2 of Goodstein(2): 1
Term 3 of Goodstein(3): 2
Term 4 of Goodstein(4): 83
Term 5 of Goodstein(5): 1197
Term 6 of Goodstein(6): 187243
Term 7 of Goodstein(7): 37665879
Term 8 of Goodstein(8): 20000000211
Term 9 of Goodstein(9): 855935016215
Term 10 of Goodstein(10): 44580503598539
Term 11 of Goodstein(11): 2120126221988686
Term 12 of Goodstein(12): 155568095557812625
Term 13 of Goodstein(13): 6568408355712901455
Term 14 of Goodstein(14): 295147905179358418247
Term 15 of Goodstein(15): 14063084452070776884879
Term 16 of Goodstein(16): 2771517379996516970665566613559367879596937714713289695169887161862950129194382447127464877388711781205972046374648603545513430106433206876557475731408608398953667881600740852227698037876781766310900319669456854530159244376159780346700931210394158247781113134808720678004134212529413831368888355854503034587880113970541681685966414888841800498150131839091463034162026108960280455620621355407543489960326268155088833218122810217973039385643494213235664908254695964740257569988152978579630435471016976693529875691083071137361386386918409765002837648351746984484967203877495399596876291343126699827442908994036031608979805166915596436929638418152127561722561465793969723556331679336828840983098559789555364076924597258115780567651772009250336359472037679350612341393780002377587368649157608579801815531133644879180066181854487069796160774056572568941004114162614925

Lua

Translation of: EasyLang – which is a translation of Phix

Tested with Lua 5.5.0

do  -- Goodstein sequence - translation of Phix via EasyLang

    local function bump( v, b )
        local n, res = v, 0
        local i = 0
        while n > 0 do
            local d <const> = n % b
            if d > 0 then
                res = res + d * math.floor( ( ( b + 1 ) ^ bump( i, b ) ) + 0.5 )
            end
            n = n // b
            i = i + 1
        end
        return res
    end

    local function goodstein( n, maxterms )
        local res <const> = {}
        if maxterms > 0 then
            res[ # res + 1 ] = n
            while # res < maxterms and res[ # res ] ~= 0 do
                res[ # res + 1 ] = bump( res[ # res ], # res + 1 ) - 1
            end
        end
        return res
    end

    do
        for i = 0, 7 do
            print( "[ " .. table.concat( goodstein( i, 10 ), " " ) .. " ]" )
        end
        print();
        for i = 0, 10 do
            local h = goodstein( i, i + 1 )
            print( h[ # h ] )
        end
    end
end

Output:

[ 0 ]
[ 1 0 ]
[ 2 2 1 0 ]
[ 3 3 3 2 1 0 ]
[ 4 26 41 60 83 109 139 173 211 253 ]
[ 5 27 255 467 775 1197 1751 2454 3325 4382 ]
[ 6 29 257 3125 46655 98039 187243 332147 555551 885775 ]
[ 7 30 259 3127 46657 823543 16777215 37665879 77777775 150051213 ]

0
0
1
2
83
1197
187243
37665879
20000000211
855935016215
44580503598539

Mathematica |Wolfram Language

Translation of: Julia

(* Given nonnegative integer n and base b, return hereditary representation consisting of
   tuples {j, k} such that the sum of all (j * base^(evaluate[k]) = n. *)
decompose[n_, b_] := Module[{decomp = {}, e = 0, quotient = n, remainder},
  If[n < b, Return[n]];
  While[quotient != 0,
    {quotient, remainder} = QuotientRemainder[quotient, b];
    If[remainder > 0,
      AppendTo[decomp, {remainder, decompose[e, b]}]
    ];
    e++
  ];
  decomp
]

(* Evaluate hereditary representation d under base b *)
evaluate[d_, b_] := If[IntegerQ[d], 
  d, 
  Total[#[[1]] * b^evaluate[#[[2]], b] & /@ d]
]

(* Return a list of up to limitlength values of the Goodstein sequence for n *)
goodstein[n_, limitlength_: 10] := Module[{seq = {}, b = 2, current = n, d},
  While[Length[seq] < limitlength,
    AppendTo[seq, current];
    If[current == 0, Break[]];
    d = decompose[current, b];
    b++;
    current = evaluate[d, b] - 1
  ];
  seq
]

(* Get the Nth term of Goodstein(n) sequence counting from 0, see https://oeis.org/A266201 *)
A266201[n_] := Last[goodstein[n, n + 1]]

(* Display results *)
Print["Goodstein(n) sequence (first 10) for values of n from 0 through 7:"];
Do[
  Print["Goodstein of ", i, ": ", goodstein[i]], 
  {i, 1, 7}
];

Print["\nThe Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through 16:"];
Do[
  Print["Term ", i, " of Goodstein(", i, "): ", A266201[i]], 
  {i, 1, 16}
];

Output:

Goodstein(n) sequence (first 10) for values of n from 0 through 7:
Goodstein of 1: {1, 0}
Goodstein of 2: {2, 2, 1, 0}
Goodstein of 3: {3, 3, 3, 2, 1, 0}
Goodstein of 4: {4, 26, 41, 60, 83, 109, 139, 173, 211, 253}
Goodstein of 5: {5, 27, 255, 467, 775, 1197, 1751, 2454, 3325, 4382}
Goodstein of 6: {6, 29, 257, 3125, 46655, 98039, 187243, 332147, 555551, 885775}
Goodstein of 7: {7, 30, 259, 3127, 46657, 823543, 16777215, 37665879, 77777775, 150051213}

The Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through 16:
Term 1 of Goodstein(1): 0
Term 2 of Goodstein(2): 1
Term 3 of Goodstein(3): 2
Term 4 of Goodstein(4): 83
Term 5 of Goodstein(5): 1197
Term 6 of Goodstein(6): 187243
Term 7 of Goodstein(7): 37665879
Term 8 of Goodstein(8): 20000000211
Term 9 of Goodstein(9): 855935016215
Term 10 of Goodstein(10): 44580503598539
Term 11 of Goodstein(11): 2120126221988686
Term 12 of Goodstein(12): 155568095557812625
Term 13 of Goodstein(13): 6568408355712901455
Term 14 of Goodstein(14): 295147905179358418247
Term 15 of Goodstein(15): 14063084452070776884879
Term 16 of Goodstein(16): 2771517379996516970665566613559367879596937714713289695169887161862950129194382447127464877388711781205972046374648603545513430106433206876557475731408608398953667881600740852227698037876781766310900319669456854530159244376159780346700931210394158247781113134808720678004134212529413831368888355854503034587880113970541681685966414888841800498150131839091463034162026108960280455620621355407543489960326268155088833218122810217973039385643494213235664908254695964740257569988152978579630435471016976693529875691083071137361386386918409765002837648351746984484967203877495399596876291343126699827442908994036031608979805166915596436929638418152127561722561465793969723556331679336828840983098559789555364076924597258115780567651772009250336359472037679350612341393780002377587368649157608579801815531133644879180066181854487069796160774056572568941004114162614925

Nim

Translation of: FreeBasic

As we don’t use a multiprecision library, we are limited to the task.

import std/[math, strformat, strutils]

proc bump(n, b: int): int =
  var n = n
  var r: int
  var i = 0
  while n > 0:
    (n, r) = divmod(n, b)
    if r != 0:
      result += r * (b + 1) ^ bump(i, b)
    inc i

proc goodstein(n: int; maxTerms = 10): seq[int] =
  result.add n
  var current = n
  var term = 1
  while term < maxTerms and current != 0:
    current = bump(current, term + 1) - 1
    result.add current
    inc term


when isMainModule:

  echo "Goodstein(n) sequence (first 10) for values of n from 0 through 7:"
  for n in 0..7:
    echo &"Goodstein of {n}: {goodstein(n).join(\", \")}"

  echo "\nThe Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through 10:"
  for n in 0..10:
    let list = goodstein(n, n + 1)
    echo &"Term {n} of Goodstein({n}): {list[n]}"

Output:

Goodstein(n) sequence (first 10) for values of n from 0 through 7:
Goodstein of 0: 0
Goodstein of 1: 1, 0
Goodstein of 2: 2, 2, 1, 0
Goodstein of 3: 3, 3, 3, 2, 1, 0
Goodstein of 4: 4, 26, 41, 60, 83, 109, 139, 173, 211, 253
Goodstein of 5: 5, 27, 255, 467, 775, 1197, 1751, 2454, 3325, 4382
Goodstein of 6: 6, 29, 257, 3125, 46655, 98039, 187243, 332147, 555551, 885775
Goodstein of 7: 7, 30, 259, 3127, 46657, 823543, 16777215, 37665879, 77777775, 150051213

The Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through 10:
Term 0 of Goodstein(0): 0
Term 1 of Goodstein(1): 0
Term 2 of Goodstein(2): 1
Term 3 of Goodstein(3): 2
Term 4 of Goodstein(4): 83
Term 5 of Goodstein(5): 1197
Term 6 of Goodstein(6): 187243
Term 7 of Goodstein(7): 37665879
Term 8 of Goodstein(8): 20000000211
Term 9 of Goodstein(9): 855935016215
Term 10 of Goodstein(10): 44580503598539

Perl

Translation of: Raku

# 20240907 Perl programming solution

use strict;
use warnings;

sub bump {
   my ($n, $b)  = @_;
   my ($res,$i) = 0,0;
   while ($n) {
      if (my $d = int($n % $b)) { $res += $d * (($b + 1) ** &bump($i, $b)) }
      $n = int($n / $b);
      $i++;
   }
   return $res;
}

sub goodstein {
   my ($n, $maxterms) = @_;
   $maxterms = 10 unless defined $maxterms;
   my @res = ($n);
   while (@res < $maxterms && $res[-1] != 0) {
      push @res, &bump($res[-1], scalar @res + 1) - 1
   }
   return @res;
}

print "Goodstein(n) sequence (first 10) for values of n from 0 through 7:\n";
foreach (0..7) { print "Goodstein of $_: ", join(", ", goodstein($_)), "\n" }

my $max = 10;
print "\nThe Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through $max :\n";
foreach my $i (0..$max) {
   my @seq = goodstein($i, $i + 1);
   printf "Term %2d of Goodstein(%2d): %s\n", $i, $i, $seq[-1] 
}

You may Attempt This Online!

Phix

Modified version of the python code from A059934 - tbh, I did not expect to get anywhere near this far using native atoms

using native atoms

with javascript_semantics
function bump(atom n, b)
    atom res = 0, i = 0
    while n do
        integer d = remainder(n,b)
        if d then
            res += d*round(power(b+1,bump(i,b)))
        end if
        n = floor(n/b)
        i += 1
    end while
    return res
end function

function goodstein(integer n, maxterms = 10)
    sequence res = {n}
    while length(res)<maxterms and res[$]!=0 do
        res &= bump(res[$],length(res)+1)-1
    end while
    return res
end function

printf(1,"Goodstein(n) sequence (first 10) for values of n from 0 through 7:\n")
for i=0 to 7 do
    printf(1,"Goodstein of %d: %v\n",{i,goodstein(i)})
end for
printf(1,"\n")
integer m64 = machine_bits()=64, maxi = iff(m64?16:15), alim = iff(m64?13:12)
printf(1,"The Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through %d:\n",maxi)
for i=0 to maxi do
    string ia = iff(i>=alim?" (inaccurate)":""),
           gs = shorten(sprintf("%d",goodstein(i,i+1)[$]))  
    printf(1,"Term %d of Goodstein(%d): %s%s\n",{i,i,gs,ia})
end for

Output:

(on 64-bit)

Goodstein(n) sequence (first 10) for values of n from 0 through 7:
Goodstein of 0: 0
Goodstein of 1: 1, 0
Goodstein of 2: 2, 2, 1, 0
Goodstein of 3: 3, 3, 3, 2, 1, 0
Goodstein of 4: 4, 26, 41, 60, 83, 109, 139, 173, 211, 253
Goodstein of 5: 5, 27, 255, 467, 775, 1197, 1751, 2454, 3325, 4382
Goodstein of 6: 6, 29, 257, 3125, 46655, 98039, 187243, 332147, 555551, 885775
Goodstein of 7: 7, 30, 259, 3127, 46657, 823543, 16777215, 37665879, 77777775, 150051213

The Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through 16:
Term 0 of Goodstein(0): 0
Term 1 of Goodstein(1): 0
Term 2 of Goodstein(2): 1
Term 3 of Goodstein(3): 2
Term 4 of Goodstein(4): 83
Term 5 of Goodstein(5): 1197
Term 6 of Goodstein(6): 187243
Term 7 of Goodstein(7): 37665879
Term 8 of Goodstein(8): 20000000211
Term 9 of Goodstein(9): 855935016215
Term 10 of Goodstein(10): 44580503598539
Term 11 of Goodstein(11): 2120126221988686
Term 12 of Goodstein(12): 155568095557812625
Term 13 of Goodstein(13): 6568408355712901452 (inaccurate)
Term 14 of Goodstein(14): 295147905179358418240 (inaccurate)
Term 15 of Goodstein(15): 14063084452070776847260 (inaccurate)
Term 16 of Goodstein(16): 27715173799965170860...62604488626682848248 (862 digits) (inaccurate)

gmp version

include mpfr.e
function bump(mpz pn, integer b)
    mpz {n, tmp, res, i} = mpz_inits(4)
    mpz_set(n,pn)
    while mpz_cmp_si(n,0) do
        integer d = mpz_fdiv_q_ui(n,n,b)
        if d then
            integer bib = mpz_get_integer(bump(i,b))
            mpz_ui_pow_ui(tmp,b+1,bib)
            mpz_mul_si(tmp,tmp,d)
            mpz_add(res,res,tmp)
        end if
        mpz_add_ui(i,i,1)
    end while
    return res
end function

function goodstein(integer n, maxterms = 10)
    sequence res = {mpz_init(n)}
    while length(res)<maxterms and mpz_cmp_si(res[$],0)!=0 do
        mpz tmp = bump(res[$],length(res)+1)
        mpz_sub_si(tmp,tmp,1)
        res &= tmp
    end while
    return res
end function

printf(1,"Goodstein(n) sequence (first 10) for values of n from 0 through 7:\n")
for i=0 to 7 do
    printf(1,"Goodstein of %d: %s\n",{i,join(apply(goodstein(i),mpz_get_str),", ")})
end for
printf(1,"\n")
printf(1,"The Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through 17:\n")
for i=0 to 17 do
    string gs = mpz_get_short_str(goodstein(i,i+1)[$])  
    printf(1,"Term %d of Goodstein(%d): %s\n",{i,i,gs})
end for

Output:

As above, except ending with the last four and one extra term being accurate:

Term 13 of Goodstein(13): 6568408355712901455
Term 14 of Goodstein(14): 295147905179358418247
Term 15 of Goodstein(15): 14063084452070776884879
Term 16 of Goodstein(16): 27715173799965169706...68941004114162614925 (862 digits)
Term 17 of Goodstein(17): 10685914955539561986...83487458441633279971 (27,776 digits)

Pluto

Translation of: Wren

Library: Pluto-fmt

local bigint = require "bigint"
local fmt = require "fmt"

local zero = bigint.new(0)
local one  = bigint.new(1)

-- Given non-negative integer n and base b, return hereditary representation
-- consisting of tuples {j, k} so sum of all (j * b^(evaluate(k, b)) = n.
local function decompose(n, b)
    if n < b then return n end
    local decomp = {}
    local e = zero
    while n != zero do
        local q, r = n:div(b)
        n = q
        if r > zero then decomp:insert({r, decompose(e, b)}) end
        e += one
    end
    return decomp
end

-- Evaluate hereditary representation d under base b.
local function evaluate(d, b)
    if type(d) == "userdata" then return d end
    local sum = zero
    for d as a do
        local j = a[1]
        local k = a[2]
        sum += j * (b ^ evaluate(k, b))
    end
    return sum
end

-- Return a vector of up to limit_length values of the Goodstein sequence for n.
local function goodstein(n, limit_length)
    local seq = {}
    local b = bigint.new(2)
    while #seq < limit_length do
        seq:insert(n)
        if n == zero then break end
        local d = decompose(n, b)
        b += one
        n = evaluate(d, b) - one
    end
    return seq
end

-- Get the nth term of the Goodstein(n) sequence counting from 0.
local function a266201(n) return goodstein(bigint.new(n), n + 1):back() end

print("Goodstein(n) sequence (first 10) for values of n in {0, 7}:")
for i = 0, 7 do
    print($"Goodstein of {i}: {fmt.swrite(goodstein(bigint.new(i), 10))}")
end

print("\nThe nth term of Goodstein(n) sequence counting from 0, for values of n in {0, 16}:")
for i = 0, 16 do
    fmt.print("Term %2d of Goodstein(%2d): %s", i, i, a266201(i))
end

Output:

Goodstein(n) sequence (first 10) for values of n in {0, 7}:
Goodstein of 0: {0}
Goodstein of 1: {1, 0}
Goodstein of 2: {2, 2, 1, 0}
Goodstein of 3: {3, 3, 3, 2, 1, 0}
Goodstein of 4: {4, 26, 41, 60, 83, 109, 139, 173, 211, 253}
Goodstein of 5: {5, 27, 255, 467, 775, 1197, 1751, 2454, 3325, 4382}
Goodstein of 6: {6, 29, 257, 3125, 46655, 98039, 187243, 332147, 555551, 885775}
Goodstein of 7: {7, 30, 259, 3127, 46657, 823543, 16777215, 37665879, 77777775, 150051213}

The nth term of Goodstein(n) sequence counting from 0, for values of n in {0, 16}:
Term  0 of Goodstein( 0): 0
Term  1 of Goodstein( 1): 0
Term  2 of Goodstein( 2): 1
Term  3 of Goodstein( 3): 2
Term  4 of Goodstein( 4): 83
Term  5 of Goodstein( 5): 1197
Term  6 of Goodstein( 6): 187243
Term  7 of Goodstein( 7): 37665879
Term  8 of Goodstein( 8): 20000000211
Term  9 of Goodstein( 9): 855935016215
Term 10 of Goodstein(10): 44580503598539
Term 11 of Goodstein(11): 2120126221988686
Term 12 of Goodstein(12): 155568095557812625
Term 13 of Goodstein(13): 6568408355712901455
Term 14 of Goodstein(14): 295147905179358418247
Term 15 of Goodstein(15): 14063084452070776884879
Term 16 of Goodstein(16): 2771517379996516970665566613559367879596937714713289695169887161862950129194382447127464877388711781205972046374648603545513430106433206876557475731408608398953667881600740852227698037876781766310900319669456854530159244376159780346700931210394158247781113134808720678004134212529413831368888355854503034587880113970541681685966414888841800498150131839091463034162026108960280455620621355407543489960326268155088833218122810217973039385643494213235664908254695964740257569988152978579630435471016976693529875691083071137361386386918409765002837648351746984484967203877495399596876291343126699827442908994036031608979805166915596436929638418152127561722561465793969723556331679336828840983098559789555364076924597258115780567651772009250336359472037679350612341393780002377587368649157608579801815531133644879180066181854487069796160774056572568941004114162614925

Python

Translation of: Julia

def decompose(n, b):
    if n < b:
        return n
    decomp = []
    e = 0
    while n != 0:
        n, r = divmod(n, b)
        if r > 0:
            decomp.append([r, decompose(e, b)])
        e += 1

    return decomp


def evaluate(d, b):
    if type(d) is int:
        return d
    return sum(j * b ** evaluate(k, b) for j, k in d)


def goodstein(n, maxlen=10):
    seq = []
    b = 2
    while len(seq) < maxlen:
        seq.append(n)
        if n == 0:
            break
        d = decompose(n, b)
        b += 1
        n = evaluate(d, b) - 1

    return seq


def A266201(n):
    """Get the Nth term of Goodstein(n) sequence counting from 0, see https://oeis.org/A266201"""
    return goodstein(n, n + 1)[-1]


if __name__ == "__main__":

    print("Goodstein(n) sequence (first 10) for values of n from 0 through 7:")
    for i in range(8):
        print(f"Goodstein of {i}: {goodstein(i)}")

    print(
        "\nThe Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through 16:"
    )
    for i in range(17):
        print(f"Term {i} of Goodstein({i}): {A266201(i)}")

Output:

Goodstein(n) sequence (first 10) for values of n from 0 through 7:
Goodstein of 0: [0]
Goodstein of 1: [1, 0]
Goodstein of 2: [2, 2, 1, 0]
Goodstein of 3: [3, 3, 3, 2, 1, 0]
Goodstein of 4: [4, 26, 41, 60, 83, 109, 139, 173, 211, 253]
Goodstein of 5: [5, 27, 255, 467, 775, 1197, 1751, 2454, 3325, 4382]
Goodstein of 6: [6, 29, 257, 3125, 46655, 98039, 187243, 332147, 555551, 885775]
Goodstein of 7: [7, 30, 259, 3127, 46657, 823543, 16777215, 37665879, 77777775, 150051213]

The Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through 16:
Term 0 of Goodstein(0): 0
Term 1 of Goodstein(1): 0
Term 2 of Goodstein(2): 1
Term 3 of Goodstein(3): 2
Term 4 of Goodstein(4): 83
Term 5 of Goodstein(5): 1197
Term 6 of Goodstein(6): 187243
Term 7 of Goodstein(7): 37665879
Term 8 of Goodstein(8): 20000000211
Term 9 of Goodstein(9): 855935016215
Term 10 of Goodstein(10): 44580503598539
Term 11 of Goodstein(11): 2120126221988686
Term 12 of Goodstein(12): 155568095557812625
Term 13 of Goodstein(13): 6568408355712901455
Term 14 of Goodstein(14): 295147905179358418247
Term 15 of Goodstein(15): 14063084452070776884879
Term 16 of Goodstein(16): 2771517379996516970665566613559367879596937714713289695169887161862950129194382447127464877388711781205972046374648603545513430106433206876557475731408608398953667881600740852227698037876781766310900319669456854530159244376159780346700931210394158247781113134808720678004134212529413831368888355854503034587880113970541681685966414888841800498150131839091463034162026108960280455620621355407543489960326268155088833218122810217973039385643494213235664908254695964740257569988152978579630435471016976693529875691083071137361386386918409765002837648351746984484967203877495399596876291343126699827442908994036031608979805166915596436929638418152127561722561465793969723556331679336828840983098559789555364076924597258115780567651772009250336359472037679350612341393780002377587368649157608579801815531133644879180066181854487069796160774056572568941004114162614925

Raku

Translation of: Phix

# 20240219 Raku programming solution

sub bump($n is copy, $b) {
   loop ( my ($res, $i) = 0, 0; $n.Bool or return $res; $i++,$n div= $b) {
      if my $d = $n % $b { $res += $d * ($b+1) ** bump($i,$b) }
   }
}

sub goodstein($n, $maxterms = 10) {
   my @res = $n;
   while @res.elems < $maxterms && @res[*-1] != 0 {
      @res.push(bump(@res[*-1], (@res.elems + 1)) - 1)
   }
   return @res
}

say "Goodstein(n) sequence (first 10) for values of n from 0 through 7:";
for 0..7 -> $i { say "Goodstein of $i: ", goodstein($i) }

my $max = 16;
say "\nThe Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through $max :";
for 0..$max -> $i { say "Term $i of Goodstein($i): {goodstein($i, $i+1)[*-1]}" }

You may Attempt This Online!

RPL

We use here the capability of RPL to evaluate the hereditary representation directly.

Works with: RPL version HP-49C

« -1 → b p
  « 0 SWAP
    WHILE DUP REPEAT 
       b IDIV2 'p' INCR
       IF OVER THEN
          IF DUP b ≥ THEN b →HRDT END
          'B' SWAP ^ * ROT + SWAP
       ELSE DROP2 END
    END DROP
» » '→HRDT' STO   @ ( n base → 'hereditary representation' )

«  → n max
  « { 0 }
    IF n THEN 
       n ADD n 
       3 max FOR m
          m 1 - →HRDT m 'B' STO EVAL 1 -     @ compute G(n)(m) 
          SWAP OVER + SWAP
          IF DUP NOT THEN max 'm' STO END     
       NEXT
       DROP 'B' PURGE
    END
» » 'GOODSTEIN' STO   @ ( n max → { G(n)(1) .. G(n)(max) )

« « j 11 GOODSTEIN » 'j' 0 7 1 SEQ
  « j DUP 2 + GOODSTEIN » 'j' 0 16 1 SEQ 
  1 « REVLIST HEAD » DOLIST
» 'TASK' STO

Output:

2: { { 0 } { 1 0 } { 2 2 1 0 } { 3 3 3 2 1 0 } { 4 26 41 60 83 109 139 173 211 253 } { 5 27 255 467 775 1197 1751 2454 3325 4382 } { 6 29 257 3125 46655 98039 187243 332147 555551 885775 } { 7 30 259 3127 46657 823543 16777215 37665879 77777775 150051213 } }
1: { 0 0 1 2 83 1197 187243 37665879 20000000211 855935016215 44580503598539 2120126221988686 155568095557812625 6568408355712901455 295147905179358418247 14063084452070776884879 2771517379996516970665566613559367879596937714713289695169887161862950129194382447127464877388711781205972046374648603545513430106433206876557475731408608398953667881600740852227698037876781766310900319669456854530159244376159780346700931210394158247781113134808720678004134212529413831368888355854503034587880113970541681685966414888841800498150131839091463034162026108960280455620621355407543489960326268155088833218122810217973039385643494213235664908254695964740257569988152978579630435471016976693529875691083071137361386386918409765002837648351746984484967203877495399596876291343126699827442908994036031608979805166915596436929638418152127561722561465793969723556331679336828840983098559789555364076924597258115780567651772009250336359472037679350612341393780002377587368649157608579801815531133644879180066181854487069796160774056572568941004114162614925 }

Wren

Translation of: Julia

Library: Wren-big

Library: Wren-fmt

import "./big" for BigInt
import "./fmt" for Fmt

// Given non-negative integer n and base b, return hereditary representation
// consisting of tuples (j, k) so sum of all (j * b^(evaluate(k, b)) = n.
var decompose // recursive
decompose = Fn.new { |n, b|
    if (n < b) return n
    var decomp = []
    var e = BigInt.zero
    while (n != 0) {
        var t = n.divMod(b)
        n = t[0]
        var r = t[1]
        if (r > 0) decomp.add([r, decompose.call(e, b)])
        e = e.inc
    }
    return decomp
}

// Evaluate hereditary representation d under base b.
var evaluate // recursive
evaluate = Fn.new { |d, b|
    if (d is BigInt) return d
    var sum = BigInt.zero
    for (a in d) {
        var j = a[0]
        var k = a[1]
        sum = sum + j * b.pow(evaluate.call(k, b))
    }
    return sum
}

// Return a vector of up to limitlength values of the Goodstein sequence for n.
var goodstein = Fn.new { |n, limitLength|
    var seq = []
    var b = BigInt.two
    while (seq.count < limitLength) {
        seq.add(n)
        if (n == 0) break
        var d = decompose.call(n, b)
        b = b.inc
        n = evaluate.call(d, b) - 1
    }
    return seq
}

// Get the nth term of the Goodstein(n) sequence counting from 0
var a266201 = Fn.new { |n| goodstein.call(n, (n + 1).toSmall)[-1] }

System.print("Goodstein(n) sequence (first 10) for values of n in [0, 7]:")
for (i in BigInt.zero..7) System.print("Goodstein of %(i): %(goodstein.call(i, 10))")

System.print("\nThe nth term of Goodstein(n) sequence counting from 0, for values of n in [0, 16]:")
for (i in BigInt.zero..16) {
    Fmt.print("Term $2i of Goodstein($2i): $i", i, i, a266201.call(i, 10))
}

Output:

Goodstein(n) sequence (first 10) for values of n in [0, 7]:
Goodstein of 0: [0]
Goodstein of 1: [1, 0]
Goodstein of 2: [2, 2, 1, 0]
Goodstein of 3: [3, 3, 3, 2, 1, 0]
Goodstein of 4: [4, 26, 41, 60, 83, 109, 139, 173, 211, 253]
Goodstein of 5: [5, 27, 255, 467, 775, 1197, 1751, 2454, 3325, 4382]
Goodstein of 6: [6, 29, 257, 3125, 46655, 98039, 187243, 332147, 555551, 885775]
Goodstein of 7: [7, 30, 259, 3127, 46657, 823543, 16777215, 37665879, 77777775, 150051213]

The nth term of Goodstein(n) sequence counting from 0, for values of n in [0, 16]:
Term  0 of Goodstein( 0): 0
Term  1 of Goodstein( 1): 0
Term  2 of Goodstein( 2): 1
Term  3 of Goodstein( 3): 2
Term  4 of Goodstein( 4): 83
Term  5 of Goodstein( 5): 1197
Term  6 of Goodstein( 6): 187243
Term  7 of Goodstein( 7): 37665879
Term  8 of Goodstein( 8): 20000000211
Term  9 of Goodstein( 9): 855935016215
Term 10 of Goodstein(10): 44580503598539
Term 11 of Goodstein(11): 2120126221988686
Term 12 of Goodstein(12): 155568095557812625
Term 13 of Goodstein(13): 6568408355712901455
Term 14 of Goodstein(14): 295147905179358418247
Term 15 of Goodstein(15): 14063084452070776884879
Term 16 of Goodstein(16): 2771517379996516970665566613559367879596937714713289695169887161862950129194382447127464877388711781205972046374648603545513430106433206876557475731408608398953667881600740852227698037876781766310900319669456854530159244376159780346700931210394158247781113134808720678004134212529413831368888355854503034587880113970541681685966414888841800498150131839091463034162026108960280455620621355407543489960326268155088833218122810217973039385643494213235664908254695964740257569988152978579630435471016976693529875691083071137361386386918409765002837648351746984484967203877495399596876291343126699827442908994036031608979805166915596436929638418152127561722561465793969723556331679336828840983098559789555364076924597258115780567651772009250336359472037679350612341393780002377587368649157608579801815531133644879180066181854487069796160774056572568941004114162614925