What is a Goodstein sequence?
A Goodstein sequence is a mathematical sequence generated by repeatedly changing the base of a number's hereditary representation and subtracting one. The process starts in base 2, then moves to base 3, base 4, base 5, and so on.
The surprising part is that a sequence can become extremely large before eventually descending to zero. This behavior is connected to one of the famous results in mathematical logic known as Goodstein's theorem.
Repeat until the current term equals zero.
Generate a Goodstein sequence
Choose an initial nonnegative integer and the maximum number of steps. The calculator uses exact integer arithmetic and stops if a term exceeds the supported PHP integer range.
Generated sequence terms
Each row shows the exact current value, the hereditary representation used for the next base change, and the operation performed.
| Step | Current value | Base used | Hereditary representation | Operation |
|---|---|---|---|---|
| 0 | 3 | 2 | 1 + 1 × 2^(1) | Initial value |
| 1 | 3 | 3 | 1 + 1 × 2^(1) | Increase base from 2 to 3, then subtract 1 |
| 2 | 3 | 4 | 1 × 3^(1) | Increase base from 3 to 4, then subtract 1 |
| 3 | 2 | 5 | 3 | Increase base from 4 to 5, then subtract 1 |
| 4 | 1 | 6 | 2 | Increase base from 5 to 6, then subtract 1 |
| 5 | 0 | 7 | 1 | Increase base from 6 to 7, then subtract 1 |
Final result: The sequence reached zero after 5 transitions.
How hereditary base representation works
Ordinary positional notation expresses a number as a sum of digits multiplied by powers of a base. Hereditary base notation goes further: the exponents are also written in the same base, recursively.
The exponent 3 is itself written in base 2 as 2 + 1. Therefore the hereditary representation can be written:
Every exponent is also expressed using the same base.
During a Goodstein step, every occurrence of the old base is replaced by the next base, including occurrences inside the exponents.
A simple example of a Goodstein step
Start with the number 3. Its hereditary representation in base 2 is:
Replace every occurrence of 2 with 3:
Subtract one to obtain the next Goodstein term:
The first transition is 3 → 3.
The following step uses the hereditary base-3 representation of the current value, changes the base to 4, and subtracts one again.
Why can the sequence grow before it shrinks?
Increasing the base changes the numerical value of every power in the hereditary expression. For example, a power of 2 may become a power of 3, and powers inside exponents change as well.
This can produce a much larger number even after one is subtracted. The process can repeat, creating a long period of dramatic growth.
Eventually, however, the sequence reaches a stage where the subtraction and the structure of the sequence lead it down to zero.
Goodstein's theorem
Goodstein's theorem states that every Goodstein sequence starting from a finite nonnegative integer eventually reaches zero.
This is remarkable because the sequence is described using elementary operations on ordinary integers, but its proof uses transfinite ordinal numbers.
For some sufficiently large finite step k.
The theorem does not say that every sequence decreases at every step. It guarantees eventual termination, even when the sequence initially grows enormously.
The connection with ordinal numbers
A key idea behind the proof is to associate an ordinal number with each Goodstein term. Unlike the ordinary integer value, this ordinal decreases at every step.
The ordinals used in the standard proof are below ε₀ (epsilon-zero), the smallest positive ordinal satisfying ωα = α.
There cannot be an infinite strictly decreasing sequence of ordinals. Therefore the associated ordinal measure must eventually reach zero, which explains why the Goodstein sequence terminates.
The associated ordinal decreases even when the integer sequence grows.
Why is Goodstein's theorem important?
Goodstein's theorem is a famous example of a statement about elementary integer arithmetic that cannot be proved using Peano arithmetic, assuming that Peano arithmetic is consistent.
This illustrates a deep distinction between mathematical truth and provability within a particular formal system. The theorem is true in the standard mathematical interpretation, but its usual proof requires stronger principles than Peano arithmetic can establish.
The independence statement concerns the standard formalization of Goodstein's theorem and the consistency of Peano arithmetic.
Frequently asked questions
What is a Goodstein sequence?
A Goodstein sequence is a sequence of nonnegative integers generated by repeatedly writing a number in hereditary base notation, increasing the base, and then subtracting one.
How is a Goodstein sequence generated?
Start with an integer in base 2. At each step, express the current number in hereditary base notation, replace every occurrence of the current base with the next base, evaluate the expression, and subtract one.
What is hereditary base representation?
It is a positional base representation in which the exponents are themselves written in the same base, recursively. For example, 2^(2) in base 2 is represented with the exponent 2 also expressed in base 2.
Why do Goodstein sequences initially grow?
Increasing the base can make the value of the hereditary expression much larger. Subtracting one may not be enough to offset that increase, so the sequence can grow dramatically before eventually descending.
Do all Goodstein sequences eventually reach zero?
Yes. Goodstein’s theorem states that every Goodstein sequence starting from a finite nonnegative integer eventually reaches zero.
Why is Goodstein’s theorem surprising?
The sequence is defined using ordinary integer arithmetic, but its proof uses ordinal numbers below epsilon-zero. The associated theorem is independent of Peano arithmetic, assuming that arithmetic is consistent.
Can a Goodstein sequence become larger before reaching zero?
Yes. Some sequences grow enormously for a long time before eventually decreasing to zero. Initial growth is a defining feature of many interesting Goodstein sequences.
Does this calculator calculate every Goodstein term?
It calculates terms exactly while they fit within the integer range of the PHP installation. If a term exceeds that range, it stops rather than displaying an inaccurate approximation.
Does reaching the calculator limit mean the sequence never terminates?
No. A computational limit is not a mathematical statement about termination. Goodstein’s theorem guarantees eventual termination for every valid starting value.
What happens when the starting number is zero?
The sequence is already at zero and is considered terminated.
Explore more mathematical calculators
Discover other recursive functions, large-number systems, and mathematical growth sequences.