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.
- 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 * 5^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 sequence with base (m - 1). 2. Calculate the results of using the hereditaty sequence found in step 1 using base m rather than (m - 1) 3. Subtract 1 from the result calcualted 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 15.
- Stretch task
- Find the nth term (counting from 0) of Goodstein(n) for n = 16.
- See also
Julia
mutable struct GBase{T<:Integer}
b::T
end
abstract type HereditaryRepresentation end
struct HRTuple <: HereditaryRepresentation
mult::Int
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
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
- 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