Goodstein Sequence

From Rosetta Code
Revision as of 21:40, 12 February 2024 by Wherrera (talk | contribs) (sp)
Goodstein Sequence is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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 sequence with base (m - 1).
   2. Calculate the results of using the hereditary sequence 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 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

Python

Translation of: Julia
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

Wren

Translation of: Julia
Library: Wren-dynamic
Library: Wren-big
Library: Wren-fmt
import "./dynamic" for Tuple, Struct
import "./big" for BigInt
import "./fmt" for Fmt

var GBase = Struct.create("GBase", ["b"])

var HR = Tuple.create("HR", ["mult", "exp"])

// Given integer n and base b
// return tuples (j, k) so sum of all (j * b^(evaluate(k)) = n.
var decompose // recursive
decompose = Fn.new { |n, bas|
    var e = 0
    var decomp = []
    while (n != 0) {
        var t = (n is Num) ? (n/bas.b).truncate : n/bas.b
        var r = n % bas.b
        n = t
        if (r != 0 && e >= bas.b) {
            if (e > bas.b) {
                decomp.add(HR.new(r, decompose.call(e, bas)))
            } else if (e == bas.b) {
                decomp.add(HR.new(r, bas))
            }
        } else {
            decomp.add(HR.new(r, GBase.new(e)))
        }
        e = e + 1
    }
    return decomp
}

var evaluate // recursive
evaluate = Fn.new { |p, bas|
    if (p is Num || p is BigInt) return p
    if (p is GBase) return p.b
    if (p is HR) {
        var e = evaluate.call(p.exp, bas)
        if (e is BigInt) e = e.toSmall
        if (p.mult is Num) {
            return p.mult * (bas.b).pow(e)
        } else {
            return p.mult * BigInt.new(bas.b).pow(e)
        }
    }
    if (p is List) {
        if (p.count == 0) return 0
        var sum = (p is Num) ? 0 : BigInt.zero
        for (a in p) sum = sum + evaluate.call(a, bas)
        return sum
    }
}

// Return a vector of up to limitlength values of the Goodstein sequence for n.
var goodstein = Fn.new { |n, limitLength|
    var sequence = []
    var bas = GBase.new(2)
    while (n >= 0 && sequence.count < limitLength) {
        sequence.add(n)
        var d = decompose.call(n, bas)
        bas.b = bas.b + 1
        n = evaluate.call(d, bas) - 1
    }
    return sequence
}

// Get the nth term of the Goodstein(n) sequence counting from 0
var a266201 = Fn.new { |n| goodstein.call(BigInt.new(n), n + 1)[-1] }

System.print("Goodstein(n) sequence (first 10) for values of n in [0, 7]:")
for (i in 0..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 0..16) {
    Fmt.print("Term $2d of Goodstein($2d): $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
Retrieved from "https://rosettacode.org/wiki/Goodstein_Sequence?oldid=360820"