Goodstein Sequence: Difference between revisions
Content deleted Content added
Create task |
m julia example |
||
Line 50: | Line 50: | ||
:* [[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 web site article on the Goodstein sequence]] |
;* [[https://googology.fandom.com/wiki/Goodstein_sequence|Googology web site article on the Goodstein sequence]] |
||
=={{header|Julia}}== |
|||
<syntaxhighlight lang="julia">mutable struct GBase{T<:Integer} |
|||
b::T |
|||
end |
|||
abstract type HereditaryRepresentation end |
|||
struct HRTuple <: HereditaryRepresentation |
|||
mult::BigInt |
|||
exp::GBase |
|||
end |
|||
struct HRVector <: HereditaryRepresentation |
|||
mult::BigInt |
|||
exp::Vector{HereditaryRepresentation} |
|||
end |
|||
""" given integer n and base b, return tuples (j, k) so sum of all (j * base^(evaluate(k)) = n. """ |
|||
function decompose(n::T, bas::GBase) where T <: Integer |
|||
e = T(0) |
|||
decomp = HereditaryRepresentation[] |
|||
while n != 0 |
|||
n, r = divrem(n, bas.b) |
|||
if r != 0 && e >= bas.b |
|||
if e > bas.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 |
|||
e += 1 |
|||
end |
|||
return decomp |
|||
end |
|||
evaluate(i::Integer, _) = i |
|||
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 """ |
|||
function goodstein(n::T; limitlength = 10) where T <: Integer |
|||
sequence = T[] |
|||
bas = GBase(T(2)) |
|||
while n >= 0 && length(sequence) < limitlength |
|||
push!(sequence, n) |
|||
d = decompose(n, bas) |
|||
bas.b += 1 # Since bas is a reference in d this increments all GBase subcomponents of d |
|||
n = evaluate(d, bas) - 1 |
|||
end |
|||
return sequence |
|||
end |
|||
""" Get the Nth term of Goodstein(n) sequence counting from 0, see https://oeis.org/A266201 """ |
|||
A266201(n) = last(goodstein(BigInt(n), limitlength = n + 1)) |
|||
println("Goodstein(n) sequence (first 10) for values of n from 0 through 7:") |
|||
for i in 0: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"0":16 |
|||
println("Term $i of Goodstein($i): ", A266201(i)) |
|||
end |
|||
</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> |