Goodstein Sequence: Difference between revisions
mNo edit summary |
m →{{header|RPL}}: typo |
||
(26 intermediate revisions by 6 users not shown) | |||
Line 4: | Line 4: | ||
Goodstein sequences are sequences defined for a given counting number n by applying increasing bases to a representation of n after n has been |
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 <em>hereditary |
used to construct a <em>hereditary representation</em> 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 |
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. |
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 |
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. |
n = 16 + 8 + 4 + 1 = 2^4 + 2^3 + 2 + 1 = 2^(2^2) + 2^(2 + 1) + 2 + 1. |
||
Line 16: | Line 16: | ||
Other integers and bases are done similarly. Note that an exponential term can be repeated up to (b - 1) times, so that, for example, |
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 * |
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 Goodstein sequence for n, G(n) is then defined as follows: |
||
Line 23: | Line 23: | ||
the m-th term G(n)(m) is defined by the following procedure: |
the m-th term G(n)(m) is defined by the following procedure: |
||
1. Write G(n)(m - 1) as a hereditary |
1. Write G(n)(m - 1) as a hereditary representation with base (m - 1). |
||
2. Calculate the results of using the |
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 |
3. Subtract 1 from the result calculated in step 2. |
||
<br /> |
<br /> |
||
Line 35: | Line 35: | ||
* Use this to show the first 10 values of Goodstein(n) for the numbers from 0 through 7. |
* 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 |
* Find the nth term (counting from 0) of Goodstein(n) for n from 0 through 10. |
||
<br /> |
<br /> |
||
Line 41: | Line 41: | ||
;Stretch task |
;Stretch task |
||
* Find the nth term (counting from 0) of Goodstein(n) for n = 16. |
* Find the nth term (counting from 0) of Goodstein(n) for n = 11 through 16. |
||
<br /><br /> |
<br /><br /> |
||
Line 49: | Line 49: | ||
:* [[wp:Goodstein%27s_theorem|Wikipedia entry for Goodstein's theorem]] |
:* [[wp:Goodstein%27s_theorem|Wikipedia entry for Goodstein's theorem]] |
||
:* [[oeis:A266201|OEIS Goodstein numbers such that a(n) = G_n(n), where G is the Goodstein function]] |
:* [[oeis:A266201|OEIS Goodstein numbers such that a(n) = G_n(n), where G is the Goodstein function]] |
||
;* [[https://googology.fandom.com/wiki/Goodstein_sequence|Googology |
;* [[https://googology.fandom.com/wiki/Goodstein_sequence | "Googology site article " ]] |
||
=={{header| |
=={{header|jq}}== |
||
'''Works with gojq, the Go implementation of jq''' |
|||
<syntaxhighlight lang="julia">mutable struct GBase{T<:Integer} |
|||
b::T |
|||
end |
|||
'''Adapted from [[#Wren|Wren]]''' |
|||
abstract type HereditaryRepresentation end |
|||
This entry assumes infinite-precision integer arithmetic as provided by the Go |
|||
struct HRTuple <: HereditaryRepresentation |
|||
implementation of jq. |
|||
mult::BigInt |
|||
<syntaxhighlight lang="jq"> |
|||
exp::GBase |
|||
# To take advantage of gojq's infintite-precision integer arithmetic: |
|||
end |
|||
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in); |
|||
# If $j is 0, then an error condition is raised; |
|||
struct HRVector <: HereditaryRepresentation |
|||
# otherwise, assuming infinite-precision integer arithmetic, |
|||
mult::BigInt |
|||
# if the input and $j are integers, then the result will be a pair of integers. |
|||
exp::Vector{HereditaryRepresentation} |
|||
def divmod($j): |
|||
end |
|||
. 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. |
|||
function decompose(n::T, bas::GBase) where T <: Integer |
|||
def decompose($n; $b): |
|||
e = T(0) |
|||
if $n < $b then $n |
|||
decomp = HereditaryRepresentation[] |
|||
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(.))" ) |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
Command invocation: gojq -n -f goodstein-sequence.jq |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Julia}}== |
|||
<syntaxhighlight lang="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 |
while n != 0 |
||
n, r = divrem(n, |
n, r = divrem(n, b) |
||
if r |
if r > 0 |
||
push!(decomp, [r, decompose(e, b)]) |
|||
push!(decomp, HRVector(r, decompose(e, bas))) |
|||
elseif e == bas.b |
|||
push!(decomp, HRTuple(r, bas)) |
|||
end |
|||
else |
|||
push!(decomp, HRTuple(r, GBase(e))) |
|||
end |
end |
||
e += 1 |
e += 1 |
||
Line 90: | Line 168: | ||
end |
end |
||
""" Evaluate hereditary representation d under base b """ |
|||
evaluate(i::Integer, _) = i |
|||
evaluate(d, b) = d isa Integer ? d : sum(j * b ^ evaluate(k, b) for (j, k) in d) |
|||
evaluate(bas::GBase, _) = bas.b |
|||
evaluate(t::HRTuple, bas) = t.mult * (bas.b)^(evaluate(t.exp, bas)) |
|||
evaluate(hv::HRVector, bas) = hv.mult * bas.b^evaluate(hv.exp, bas) |
|||
evaluate(arr::Vector{HereditaryRepresentation}, bas) = isempty(arr) ? 0 : sum(evaluate(a, bas) for a in arr) |
|||
""" Return a vector of up to limitlength values of the Goodstein sequence for n """ |
""" Return a vector of up to limitlength values of the Goodstein sequence for n """ |
||
function goodstein(n |
function goodstein(n, limitlength = 10) |
||
seq = typeof(n)[] |
|||
b = typeof(n)(2) |
|||
while |
while length(seq) < limitlength |
||
push!( |
push!(seq, n) |
||
n == 0 && break |
|||
d = decompose(n, b) |
|||
bas.b += 1 # Since bas is a reference in d this increments all GBase subcomponents of d |
|||
b += 1 |
|||
n = evaluate(d, b) - 1 |
|||
end |
end |
||
return |
return seq |
||
end |
end |
||
""" |
"""Get the Nth term of Goodstein(n) sequence counting from 0, see https://oeis.org/A266201""" |
||
A266201(n) = last(goodstein(BigInt(n), |
A266201(n) = last(goodstein(BigInt(n), n + 1)) |
||
println("Goodstein(n) sequence (first 10) for values of n from 0 through 7:") |
println("Goodstein(n) sequence (first 10) for values of n from 0 through 7:") |
||
for i in |
for i in 1:7 |
||
println("Goodstein of $i: |
println("Goodstein of $i: $(goodstein(i))") |
||
end |
end |
||
println("\nThe Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through 16:") |
println("\nThe Nth term of Goodstein(N) sequence counting from 0, for values of N from 0 through 16:") |
||
for i in big" |
for i in big"1":16 |
||
println("Term $i of Goodstein($i): |
println("Term $i of Goodstein($i}): $(A266201(i))") |
||
end |
end |
||
</syntaxhighlight>{{out}} |
</syntaxhighlight>{{out}} |
||
Line 145: | Line 219: | ||
Term 8 of Goodstein(8): 20000000211 |
Term 8 of Goodstein(8): 20000000211 |
||
Term 9 of Goodstein(9): 855935016215 |
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 |
|||
</pre> |
|||
=={{header|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 === |
|||
<!--(phixonline)--> |
|||
<syntaxhighlight lang="phix"> |
|||
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 |
|||
</syntaxhighlight> |
|||
{{out}} (on 64-bit) |
|||
<pre> |
|||
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) |
|||
</pre> |
|||
=== gmp version === |
|||
<syntaxhighlight lang="phix"> |
|||
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 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
As above, except ending with the last four and one extra term being accurate: |
|||
<pre> |
|||
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) |
|||
</pre> |
|||
=={{header|Python}}== |
|||
{{trans|Julia}} |
|||
<syntaxhighlight lang="python">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)}") |
|||
</syntaxhighlight>{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Raku}}== |
|||
{{trans|Phix}} |
|||
<syntaxhighlight lang="raku" line># 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]}" }</syntaxhighlight> |
|||
You may [https://ato.pxeger.com/run?1=XZK_btswEMaBjnqKr4YaUJas2ktTWElRdCm6eMpWdPAfyiIqkQ5FtjUMPUmXDM0LZczT9I5SXTkaCIj33Xe_O97vP3b93T88PHpXzt4_v3pq_QYb3xxErKFabM3hmCHeJDhFAGpjDhBojhCxlS1FVIJbzDPMC8Q6_2RMDWNhpfNWgzV0r9IUgwF9quT8eEd5XOQNu-dftMMp6JHecnAKIeJNukgwnQ5AKiNlklvj9Q7d4EYOvc_b4FMSoeVQF3VRxM3sjdm1TipNIuJt1r-ctE1LWYv5AEU4H7kyFdYFX_ysVC3DXS5rSeKbUeLVVYh8nc4W3_Camj93FhIOvq1EAD6rMoiRV4pFkmBGZ89JxzAuFgXs9RGTz2dunaCV917qrYQolW1dQC9pzj_WtSdwU0KjtKYhGFfRgPYVrpeTImLNPM-vMftAz0ATvrTmxFgtMcnGY6In7SFEUkT8VNQ6j-td0ZPdVRIrV4HHwQ7_SVcj0i09k1N6P3BlL3hXL3lDlRFz-L_AvuN69HtRkmiXOI3peSlpb8Lkuwm6frWHDf-36X8B Attempt This Online!] |
|||
=={{header|RPL}}== |
|||
We use here the capability of RPL to evaluate the hereditary representation directly. |
|||
{{works with|RPL|HP-49C}} |
|||
« -1 → b p |
|||
« 0 SWAP |
|||
'''WHILE''' DUP '''REPEAT''' |
|||
b IDIV2 'p' INCR |
|||
'''IF''' OVER '''THEN''' |
|||
'''IF''' DUP b ≥ THEN b <span style="color:blue">→HRDT</span> '''END''' |
|||
'B' SWAP ^ * ROT + SWAP |
|||
'''ELSE''' DROP2 '''END''' |
|||
'''END''' DROP |
|||
» » '<span style="color:blue">→HRDT</span>' STO <span style="color:grey">''@ ( n base → 'hereditary representation' )''</span> |
|||
« → n max |
|||
« { 0 } |
|||
'''IF''' n '''THEN''' |
|||
n ADD n |
|||
3 max '''FOR''' m |
|||
m 1 - <span style="color:blue">→HRDT</span> m 'B' STO EVAL 1 - <span style="color:grey">''@ compute G(n)(m)'' </span> |
|||
SWAP OVER + SWAP |
|||
'''IF''' DUP NOT '''THEN''' max 'm' STO '''END''' |
|||
'''NEXT''' |
|||
DROP 'B' PURGE |
|||
'''END''' |
|||
» » '<span style="color:blue">GOODSTEIN</span>' STO <span style="color:grey">''@ ( n max → { G(n)(1) .. G(n)(max) )''</span> |
|||
« « j 11 <span style="color:blue">GOODSTEIN</span> » 'j' 0 7 1 SEQ |
|||
« j DUP 2 + <span style="color:blue">GOODSTEIN</span> » 'j' 0 16 1 SEQ |
|||
1 « REVLIST HEAD » DOLIST |
|||
» '<span style="color:blue">TASK</span>' STO |
|||
{{out}} |
|||
<pre> |
|||
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 } |
|||
</pre> |
|||
=={{header|Wren}}== |
|||
{{trans|Julia}} |
|||
{{libheader|Wren-big}} |
|||
{{libheader|Wren-fmt}} |
|||
<syntaxhighlight lang="wren">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)) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 10 of Goodstein(10): 44580503598539 |
||
Term 11 of Goodstein(11): 2120126221988686 |
Term 11 of Goodstein(11): 2120126221988686 |
Latest revision as of 08:28, 1 August 2024
- 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.
- 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
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
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)
Python
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
# 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!
RPL
We use here the capability of RPL to evaluate the hereditary representation directly.
« -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
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