def collatz_length(n):
original_n = n
steps = 0
while n != 1:
if n in CACHE:
steps += CACHE[n]
break
if n & 1: # n is odd
n = (3 * n + 1) >> 1 # Equivalent to (3*n + 1) // 2
steps += 2
else:
n >>= 1 # Equivalent to n // 2
steps += 1
CACHE[original_n] = steps
return steps
It ran sort of slow though. I only ended up going to a billion and then relied upon the OEIS for getting a few more points for the graph: https://oeis.org/A006877/
1 Comment
Used Python for this one. Basic collatz function:
CACHE = {}
def collatz_length(n):
original_n = n
steps = 0
while n != 1:
if n in CACHE:
steps += CACHE[n]
break
if n & 1: # n is odd
n = (3 * n + 1) >> 1 # Equivalent to (3*n + 1) // 2
steps += 2
else:
n >>= 1 # Equivalent to n // 2
steps += 1
CACHE[original_n] = steps
return steps
It ran sort of slow though. I only ended up going to a billion and then relied upon the OEIS for getting a few more points for the graph: https://oeis.org/A006877/
Used matplotlib for the graph:
import matplotlib.pyplot as plt
records = [
(2, 1), (3, 7), (6, 8), (7, 16), (9, 19), (18, 20), (25, 23), (27, 111),
(54, 112), (73, 115), (97, 118), (129, 121), (171, 124), (231, 127),
(313, 130), (327, 143), (649, 144), (703, 170), (871, 178), (1161, 181),
(2223, 182), (2463, 208), (2919, 216), (3711, 237), (6171, 261),
(10971, 267), (13255, 275), (17647, 278), (23529, 281), (26623, 307),
(34239, 310), (35655, 323), (52527, 339), (77031, 350), (106239, 353),
(142587, 374), (156159, 382), (216367, 385), (230631, 442), (410011, 448),
(511935, 469), (626331, 508), (837799, 524), (1117065, 527), (1501353, 530),
(1723519, 556), (2298025, 559), (3064033, 562), (3542887, 583),
(3732423, 596), (5649499, 612), (6649279, 664), (8400511, 685),
(11200681, 688), (14934241, 691), (15733191, 704), (31466382, 705),
(36791535, 744), (63728127, 949), (127456254, 950), (169941673, 953),
(226588897, 956), (268549803, 964), (537099606, 965), (670617279, 986),
(1341234558, 987), (1412987847, 1000), (1674652263, 1008), (2610744987, 1050),
(4578853915, 1087), (4890328815, 1131), (9780657630, 1132), (12212032815, 1153),
(12235060455, 1184), (13371194527, 1210), (17828259369, 1213), (31694683323, 1219),
(63389366646, 1220), (75128138247, 1228), (133561134663, 1234), (158294678119, 1242),
(166763117679, 1255), (202485402111, 1307), (404970804222, 1308), (426635908975, 1321),
(568847878633, 1324), (674190078379, 1332), (881715740415, 1335), (989345275647, 1348),
(1122382791663, 1356), (1444338092271, 1408), (1899148184679, 1411), (2081751768559, 1437),
(2775669024745, 1440), (3700892032993, 1443), (3743559068799, 1549), (7487118137598, 1550),
(7887663552367, 1563), (10516884736489, 1566), (14022512981985, 1569), (19536224150271, 1585),
(26262557464201, 1588), (27667550250351, 1601), (38903934249727, 1617), (48575069253735, 1638),
(51173735510107, 1651), (60650353197163, 1659), (80867137596217, 1662), (100759293214567, 1820),
(134345724286089, 1823), (223656998090055, 1847), (397612441048987, 1853), (530149921398649,
1856),
(706866561864865, 1859), (942488749153153, 1862), (1256651665537537, 1865), (1675535554050049,
1868),
(2234047405400065, 1871), (2978729873866753, 1874), (3586720916237671, 1895),
(4320515538764287, 1903), (4861718551722727, 1916), (6482291402296969, 1919),
(7579309213675935, 1958), (12769884180266527, 2039), (17026512240355369, 2042),
(22702016320473825, 2045), (45404032640947650, 2046), (46785696846401151, 2090)
]
def visualise_records(records):
numbers, lengths = zip(*records)
plt.style.use(‘dark_background’)
plt.figure(figsize=(12, 8))
colours = [length for length in lengths]
plt.scatter(numbers, lengths, alpha=0.7, c=colours, cmap=’viridis_r’)
plt.xscale(‘log’)
plt.xlabel(‘Starting Number (log scale)’)
plt.ylabel(‘Sequence Length’)
plt.title(‘Collatz Conjecture: Record-Setting Sequence Lengths’)
plt.tight_layout()
plt.show()
visualise_records(records)