Goodstein Sequence

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 less than 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