Goodstein Sequence: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Wherrera (talk | contribs)
4,129 edits
typo
Wherrera (talk | contribs)
4,129 edits
m →‎{{header|Julia}}: Using a generic vector instead of an inheritance tree of elements is faster here, for once.
Line 54: Line 54:


=={{header|Julia}}==
=={{header|Julia}}==
<syntaxhighlight lang="julia">mutable struct GBase{T<:Integer}
<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.
⚫
b::T
"""
end
⚫
function decompose(n, b)

⚫
if n < b
abstract type HereditaryRepresentation end
⚫
return n

⚫
end
struct HRTuple <: HereditaryRepresentation
decomp = Vector{Union{typeof(n), Vector}}[]
mult::Int
e = typeof(n)(0)
exp::GBase
end

struct HRVector <: HereditaryRepresentation
mult::Int
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
while n != 0
n, r = divrem(n, bas.b)
n, r = divrem(n, b)
if r != 0 && e >= bas.b
if r > 0
if e > bas.b
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 73:
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::T; limitlength = 10) where T <: Integer
function goodstein(n, limitlength = 10)
sequence = T[]
seq = typeof(n)[]
bas = GBase(T(2))
b = typeof(n)(2)
while n >= 0 && length(sequence) < limitlength
while length(seq) < limitlength
push!(sequence, n)
push!(seq, n)
d = decompose(n, bas)
n == 0 && break
d = decompose(n, b)
bas.b += 1 # Since bas is a reference in d this increments all GBase subcomponents of d
n = evaluate(d, bas) - 1
b += 1
n = evaluate(d, b) - 1
end
end
return sequence
return seq
end
end


""" Get the Nth term of Goodstein(n) sequence counting from 0, see https://oeis.org/A266201 """
"""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))
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 0:7
for i in 1:7
println("Goodstein of $i: ", goodstein(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"0":16
for i in big"1":16
println("Term $i of Goodstein($i): ", A266201(i))
println("Term $i of Goodstein($i}): $(A266201(i))")
end
end
</syntaxhighlight>{{out}}
</syntaxhighlight>{{out}}
Retrieved from "https://rosettacode.org/wiki/Goodstein_Sequence"