Integer Sequences Related to 3X+1 Collatz Iteration
(The 3X+1 sequences are also discussed here: A006877, 3X+1 Problem.)
The "3X+1 problem" has been around for a long time, but I learned about it from Hofstadter's book Gödel,_Escher,_Bach [1]. The problem asks if there is a proof, or disproof, that for every initial value X1, the following iteration never reaches Xn=1:
If Xn is even, Xn+1 = Xn/2
If Xn is odd, Xn+1 = 3 Xn + 1
If you try this iteration with a starting value of, for example, X1=27, the values of Xn are:
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, ...
The value goes up and down many times, and seems to be growing steadily into 3- and 4-digit values, but then quickly goes back to small values and ends with the repeating sequence 4, 2, 1, 4, 2, 1, ...
All starting values that have been tried so far end with the values 4, 2, 1. Most starting values end fairly quickly, but a few, such as 27, go for a long time. 27 is a "record-setter" in the sense that its iteration goes higher than any other starting value less than 27. Its highest iteration value is 9232. The next record-setter is 255, which goes as high as 13120. Sequence A006885 gives the highest iteration values, like 9232 and 13120, and sequence A006884 gives the starting values that set the records:
A006885: 1, 2, 16, 52, 160, 9232, 13120, 39364, 41524, 250504, 1276936, 6810136, 8153620, 27114424, 50143264, 106358020, 121012864, 593279152, 1570824736, 2482111348, 2798323360, 17202377752, 24648077896, 52483285312, 56991483520, 90239155648, 139646736808, 151629574372, 155904349696, 156914378224, 190459818484, 352617812944, 622717901620, 858555169576, 1318802294932, 2412493616608, 4799996945368, 60342610919632, 306296925203752, 474637698851092, 2185143829170100, 3277901576118580, 6404797161121264, 1414236446719942480, ...
A006884: 1, 2, 3, 7, 15, 27, 255, 447, 639, 703, 1819, 4255, 4591, 9663, 20895, 26623, 31911, 60975, 77671, 113383, 138367, 159487, 270271, 665215, 704511, 1042431, 1212415, 1441407, 1875711, 1988859, 2643183, 2684647, 3041127, 3873535, 4637979, 5656191, 6416623, 6631675, 19638399, 38595583, 80049391, 120080895, 210964383, 319804831, ...
One can also search for starting values that take a record number of iteration steps to reach 1. The records for number of steps, and the starting values that set these records, are sequence A006878 and sequence A006877 respectively:
A006878: 1, 7, 8, 16, 19, 20, 23, 111, 112, 115, 118, 121, 124, 127, 130, 143, 144, 170, 178, 181, 182, 208, 216, 237, 261, 267, 275, 278, 281, 307, 310, 323, 339, 350, 353, 374, 382, 385, 442, 448, 469, 508, 524, 527, 530, 556, 559, 562, 583, 596, 612, 664, 685, 688, 691, 704, 705, 744, 949, 950, 953, 956, 964, 965, 986, 987, ...
A006877: 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, 10971, 13255, 17647, 23529, 26623, 34239, 35655, 52527, 77031, 106239, 142587, 156159, 216367, 230631, 410011, 511935, 626331, 837799, 1117065, 1501353, 1723519, 2298025, 3064033, 3542887, 3732423, 5649499, 6649279, 8400511, 11200681, 14934241, 15733191, 31466382, 36791535, 63728127, 127456254, 169941673, 226588897, 268549803, 537099606, 670617279, 1341234558, ...
The 3X+1 problem is one of many similar problems involving iteration of an integer value using one of several polynomials that depend on a modulo value (like odd or even). Such iterations are called Collatz problems because the original conjecture regarding the 3X+1 case was given by Lothar Collatz.
Some other sequences are discussed here.
[1] Hofstadter, Douglas, Gödel, Escher Bach: An Eternal Golden Braid, Vintage, 1979, ISBN 978-0394745022
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2012 Mar 01.
s.27