Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Goodstein's theorem
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== Goodstein sequences == The '''Goodstein sequence''' <math>G_m</math> of a number ''m'' is a sequence of natural numbers. The first element in the sequence <math>G_m</math> is ''m'' itself. To get the second, <math>G_m (2)</math>, write ''m'' in hereditary base-2 notation, change all the 2s to 3s, and then subtract 1 from the result. In general, the {{nowrap|1 + ''n''th}} term, <math>G_m (n+1)</math>, of the Goodstein sequence of ''m'' is as follows: * Take the hereditary base-{{nowrap|''n''β+β1}} representation of <math>G_m (n)</math>. * Replace each occurrence of the base-{{nowrap|''n''β+β1}} with {{nowrap|''n''β+β2}}. * Subtract one. (Note that the next term depends both on the previous term and on the index ''n''.) * Continue until the result is zero, at which point the sequence terminates. Early Goodstein sequences terminate quickly. For example, <math>G_3</math> terminates at the 6th step: {| class="wikitable" border="1" |- ! Base !! Hereditary notation !! Value !! Notes |- | 2 || <math> 2^1 + 1 </math> || 3 || Write 3 in base-2 notation |- | 3 || <math> 3^1 + 1 - 1 = 3^1 </math> || 3 || Switch the 2 to a 3, then subtract 1 |- | 4 || <math> 4^1 - 1 = 3 </math> || 3 || Switch the 3 to a 4, then subtract 1. Now there are no more 4's left |- | 5 || <math> 3 - 1 = 2 </math> || 2 || No 4's left to switch to 5's. Just subtract 1 |- | 6 || <math> 2 - 1 = 1 </math> || 1 || No 5's left to switch to 6's. Just subtract 1 |- | 7 || <math> 1 - 1 = 0 </math> || 0 || No 6's left to switch to 7's. Just subtract 1 |} Later Goodstein sequences increase for a very large number of steps. For example, <math>G_4</math> {{OEIS2C|id=A056193}} starts as follows: {| class="wikitable" border="1" |- ! Base !! Hereditary notation !! Value |- | 2 || <math> 2^{2^1} </math> || 4 |- | 3 || <math> 3^{3^1} - 1 = 2 \cdot 3^2 + 2 \cdot 3 + 2 </math> || 26 |- | 4 || <math> 2 \cdot 4^2 + 2 \cdot 4 + 1 </math> || 41 |- | 5 || <math> 2 \cdot 5^2 + 2 \cdot 5 </math> || 60 |- | 6 || <math> 2 \cdot 6^2 + 2 \cdot 6 - 1 = 2 \cdot 6^2 + 6 + 5 </math> || 83 |- | 7 || <math> 2 \cdot 7^2 + 7 + 4 </math> || 109 |- align=center | <math> \vdots </math> || <math> \vdots </math> || <math> \vdots </math> |- | 11 || <math> 2 \cdot 11^2 + 11 </math> || 253 |- | 12 || <math> 2 \cdot 12^2 + 12 - 1 = 2 \cdot 12^2 + 11 </math> || 299 |- align=center | <math> \vdots </math> || <math> \vdots </math> || <math> \vdots </math> |- | 24 || <math> 2 \cdot 24^2 - 1 = 24^2 + 23 \cdot 24 + 23 </math> || 1151 |- align=center | <math> \vdots </math> || <math> \vdots </math> || <math> \vdots </math> |- | <math> B = 3 \cdot 2^{402\,653\,209} - 1 </math> || <math> 2 \cdot B^1 </math> || <math> 3 \cdot 2^{402\,653\,210} - 2 </math> |- | <math> B = 3 \cdot 2^{402\,653\,209} </math> || <math> 2 \cdot B^1 - 1 = B^1 + (B-1) </math> || <math> 3 \cdot 2^{402\,653\,210} - 1 </math> |- align=center | <math> \vdots </math> || <math> \vdots </math> || <math> \vdots </math> |} Elements of <math>G_4</math> continue to increase for a while, but at base <math>3 \cdot 2^{402\,653\,209}</math>, they reach the maximum of <math>3 \cdot 2^{402\,653\,210} - 1</math>, stay there for the next <math>3 \cdot 2^{402\,653\,209}</math> steps, and then begin their descent. However, even <math>G_4</math> doesn't give a good idea of just ''how'' quickly the elements of a Goodstein sequence can increase. <math>G_{19}</math> increases much more rapidly and starts as follows: {| class="wikitable" border="1" |- ! Hereditary notation !! Value |- | <math> 2^{2^2} + 2 + 1 </math> || 19 |- | <math> 3^{3^3} + 3 </math> || {{val|7,625,597,484,990}} |- | <math> 4^{4^4} + 3 </math> || <math> \approx 1.3 \times 10^{154} </math> |- | <math> 5^{5^5} + 2 </math> || <math> \approx 1.8 \times 10^{2\,184} </math> |- | <math> 6^{6^6} + 1 </math> || <math> \approx 2.6 \times 10^{36\,305} </math> |- | <math> 7^{7^7} </math> || <math> \approx 3.8 \times 10^{695\,974} </math> |- | <math> 8^{8^8} - 1 = 7 \cdot 8^{7 \cdot 8^7 + 7 \cdot 8^6 + 7 \cdot 8^5 + 7 \cdot 8^4 + 7 \cdot 8^3 + 7 \cdot 8^2 + 7 \cdot 8 + 7}</math> <math>{}+ 7 \cdot 8^{7 \cdot 8^7 + 7 \cdot 8^6 + 7 \cdot 8^5 + 7 \cdot 8^4 + 7 \cdot 8^3 + 7 \cdot 8^2 + 7 \cdot 8 + 6} + \cdots</math> <math>{}+ 7 \cdot 8^{8+2} + 7 \cdot 8^{8+1} + 7 \cdot 8^8 </math> <math>{}+ 7 \cdot 8^7 + 7 \cdot 8^6 + 7 \cdot 8^5 + 7 \cdot 8^4 </math> <math>{}+ 7 \cdot 8^3 + 7 \cdot 8^2 + 7 \cdot 8 + 7</math> | <math> \approx 6.0 \times 10^{15\,151\,335} </math> |- | <math>7 \cdot 9^{7 \cdot 9^7 + 7 \cdot 9^6 + 7 \cdot 9^5 + 7 \cdot 9^4 + 7 \cdot 9^3 + 7 \cdot 9^2 + 7 \cdot 9 + 7}</math> <math>{}+ 7 \cdot 9^{7 \cdot 9^7 + 7 \cdot 9^6 + 7 \cdot 9^5 + 7 \cdot 9^4 + 7 \cdot 9^3 + 7 \cdot 9^2 + 7 \cdot 9 + 6} + \cdots</math> <math>{}+ 7 \cdot 9^{9+2} + 7 \cdot 9^{9+1}+ 7 \cdot 9^9 </math> <math>{}+ 7 \cdot 9^7 + 7 \cdot 9^6 + 7 \cdot 9^5 + 7 \cdot 9^4 </math> <math>{}+ 7 \cdot 9^3 + 7 \cdot 9^2 + 7 \cdot 9 + 6</math> | <math> \approx 5.6 \times 10^{35\,942\,384} </math> |- align=center | <math> \vdots </math> || <math> \vdots </math> |} In spite of this rapid growth, Goodstein's theorem states that every Goodstein sequence eventually terminates at 0, no matter what the starting value is.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)