# Goodstein Sequence

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

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.

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.
```

• 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.

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

## jq

Works with gojq, the Go implementation of jq

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];

"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
```

## 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)
end if
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)
```

## 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++ ) {
if my \$d = (\$n % \$b).Int { \$res += \$d * ((\$b+1) ** bump(\$i,\$b)).round }
\$n = (\$n / \$b).floor
}
}

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) }

say();
my \$max = 16;
say "The 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!

## 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) {
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
```