The Collatz Conjecture

In this section

• Introduction
• Which 'a' Values?
• Where to look for loops

Introduction

Earlier when calculating where we needed to start looking for loops, given that exhaustive searches had eliminated most numbers up to 1015 we decided to look for systems where the maximum ratio of a seed value to K was greater than this value. Unfortunately loops with large values also contain small values, and all the values must be greater than our cut-off value. So what we need to do is find, for a particular combination of m and n, what the largest loop seed (the smallest loop member) is. For small n and m values we can just search through the loop members; the results are summarised in the following tables (LS is the largest loop seed).

n m LS K LS/K 3 5 23 5   3 6 37 37 1 3 7 37 101   3 8 53 229   3 9 97 485 1/5 3 10 97 997   3 11 161 2021   3 12 313 4069 1/13 3 13 313 8165	n m LS K LS/K 6 10 1357 295   6 11 1805 1319   6 12 3367 3367 1 6 13 3367 7463
n m LS K LS/K 4 7 101 47   4 8 175 175 1 4 9 175 431   4 10 287 943   4 11 415 1967   4 12 803 4015 1/5 4 13 803 8111	n m LS K LS/K 7 12 5095 1909   7 13 7463 6005   7 14 14197 14197 1 7 15 14197 30581
n m LS K LS/K 5 8 319 13   5 9 431 269   5 10 781 781 1 5 11 781 1805   5 12 1299 3853   5 13 1885 7949   5 14 3293 16141   5 15 6505 32525 1/5 5 16 6505 65293	n m LS K LS/K 8 13 14501 1631   8 14 21109 9823   8 15 30581 26207   8 16 58975 58975 1 8 17 58975 124511

Observations

There are a few interesting observations in the above table.

The values LS/K=1 when m=2n is obtained by setting all the 'a' values to 2. The 1/5 is when all the 'a' values are 3. The sequence continues [1, 1/5, 1/13, 1/29, 1/61, 1/125.0, 1/253, 1/509, ...], the rule being double it and add 3.

Here we have proved that there are no cycles (other than [1,4,2,1]) in 3x+1 that contain twice as many or more even numbers as odd numbers, so there is no point looking at systems where m>=2n. When a list consists of a repeated sequence it can be factorised, so [2,2,2] is [2]^3, which generates three repeats of the basic cycle [1,4,2,1]. This is the cycle with the largest possible ratio m/n.

Which 'a' Values?

For a given n value the loop values are determined by the equation.

s = (3n-1 + 3n-2*2a1 + 3n-3*2a1+a2 + ...)

What combinations of 'a' values lead to the loop seeds encountered above? Here are a few lists found by searching through the sets of all a values that meet the constraint sum(a)=m. The set of lists gets very large so I've stopped at m = 10.

n	m	LS	loop
3	5	23	[1, 2, 2]
3	6	37	[2, 2, 2]
4	7	101	[1, 2, 2, 2]
4	8	175	[2, 2, 2, 2]
5	8	319	[1, 2, 1, 2, 2]
6	10	1357	[1, 2, 2, 1, 2, 2]

It appears likely that for a given n and m the highest loop seed will be found by mixing the '1' and '2' values as uniformly as possible across the list. This can be achieved by using Bresenham's line algorith to connect the points (0,0) to (m,n). Applying this algorithm is a lot quicker than searching all the possible lists so we can easily try it for larger numbers. Here are some results (LS¬[obs] is the value obtained by testing all the loops, LS¬[post] is calculated from the postulated minimal loop)

n	m	Minimal loop	LSobs	LSpost
3	5	[1, 2, 2]	23	23
4	7	[1, 2, 2, 2]	101	101
5	8	[1, 2, 1, 2, 2]	319	319
6	10	[1, 2, 2, 1, 2, 2]	1357	1357
7	12	[1, 2, 2, 1, 2, 2, 2]	5095	5095
8	13	[1, 2, 1, 2, 2, 1, 2, 2]	14501	14501

So this method correctly predicts the largest loop seed for n values up to 8. Let's see what it predicts for some larger numbers.

n	m	Minimal loop	LSpost
9	15	[1, 2, 2, 1, 2, 2, 1, 2, 2]	60,191
10	16	[1, 2, 1, 2, 2, 1, 2, 1, 2, 2]	159,181
11	18	[1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2]	579,943
12	20	[1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2]	2,378,821
13	21	[1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2]	5,805,215
14	23	[1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2]	21,687,773
15	24	[1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2]	59,586,967
16	26	[1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2]	213,933,253
17	27	[1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2]	548,440,271
18	29	[1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2]	1,994,724,077
19	31	[1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2]	7,319,701,703
20	32	[1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2]	19,831,564,885
21	34	[1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2]	68,498,816,767
22	35	[1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2]	176,086,441,085
23	37	[1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2]	634,236,499,703
24	39	[1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2]	2,376,761,709,797
25	40	[1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2]	6,189,164,834,479
26	42	[1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2]	21,429,806,042,125
27	43	[1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2]	53,749,761,723,047
28	45	[1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2]	192,396,217,969,781
29	46	[1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2]	490,121,922,519,007
30	48	[1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2]	1,854,711,264,038,941

These values haven't been verified using exhaustive searches.

Where to look for loops

Looking at the loop seeds (the smallest number in a loop) gives us a much tighter constraint. If we take the set of loop seeds for a particular 'n' and find the largest, we can see that these are much smaller than the largest loop members. The following table shows how the two sets of numbers compare (the ratios have been truncated to whole numbers).

n	m	Largest seed	Max loop member	Ratio
1	2	1	1	1
2	4	7	11	1
3	5	23	49	2
4	7	101	331	3
5	8	319	1,121	3
6	10	1,357	6,995	5
7	12	5,095	43,289	8
8	13	14,501	133,963	9
9	15	60,191	813,601	13
10	16	159,181	2,473,571	15
11	18	579,943	14,913,449	25
12	20	2,378,821	89,827,835	37
13	21	5,805,215	270,532,081	46
14	23	21,687,773	1,625,792,467	74
15	24	59,586,967	4,885,766,009	81
16	26	213,933,253	29,333,801,579	137
17	27	548,440,271	88,068,513,601	160
18	29	1,994,724,077	528,550,376,899	265
19	31	7,319,701,703	3,171,988,582,729	433
20	32	19,831,564,885	9,518,113,231,835	479
21	34	68,498,816,767	57,113,782,541,201	833
22	35	176,086,441,085	171,358,527,492,787	973
23	37	634,236,499,703	1,028,188,503,373,849	1,621
24	39	2,376,761,709,797	6,169,311,754,971,211	2,596
25	40	6,189,164,834,479	18,508,485,020,727,521	2,990
26	42	21,429,806,042,125	111,052,261,859,011,235	5,182
27	43	53,749,761,723,047	333,161,183,623,544,809	6,198
28	45	192,396,217,969,781	1,998,977,068,329,828,283	10,390
29	46	490,121,922,519,007	5,996,966,389,361,573,681	12,236
30	48	1,854,711,264,038,941	35,981,870,443,280,432,531	19,400

So by the time we get to 30 we are already 4 orders of magnitude down on the limit calculated using the largest value. The chart shows that this ratio increases by about an order of magnitude for every seven n values.

For n = 82 we'd expect the ratio to be about 1012, so the largest value we'd need to test searching for loops would be around 1000. The next table shows how the ratio LS/K varies with 'n' (using the predicted LS values).

n	m	LS	K	LS/K
1	2	1	1	1
2	4	7	7	1
3	5	23	5	4
4	7	101	47	2
5	8	319	13	24
6	10	1,357	295	4
7	12	5,095	1,909	2
8	13	14,501	1,631	8
9	15	60,191	13,085	4
10	16	159,181	6,487	24
11	18	579,943	84,997	6
12	20	2,378,821	517,135	4
13	21	5,805,215	502,829	11
14	23	21,687,773	3,605,639	6
15	24	59,586,967	2,428,309	24
16	26	213,933,253	24,062,143	8
17	27	548,440,271	5,077,565	108
18	29	1,994,724,077	149,450,423	13
19	31	7,319,701,703	985,222,181	7
20	32	19,831,564,885	808,182,895	24
21	34	68,498,816,767	6,719,515,981	10
22	35	176,086,441,085	2,978,678,759	59
23	37	634,236,499,703	43,295,774,645	14
24	39	2,376,761,709,797	267,326,277,407	8
25	40	6,189,164,834,479	252,223,018,333	24
26	42	21,429,806,042,125	1,856,180,682,775	11
27	43	53,749,761,723,047	1,170,495,537,221	45
28	45	192,396,217,969,781	12,307,579,633,871	15
29	46	490,121,922,519,007	1,738,366,812,781	281
30	48	1,854,711,264,038,941	75,583,844,616,007	24

Searching up to 281 will eliminate all possibility of loops with fewer than 79 members. The next table shows some values from the region 80-90 (I've missed out the actual LS and K values as they are rather large). Note the ratios are still pretty small, and that the largest value we'd have to test to eliminate loops with fewer than 234 members would be 867.

n	m	LS/K	Predicted
81	129	45	46
82	130	867	877
83	132	64	65
84	134	33	34
85	135	108	108
86	137	43	44
87	138	281	284
88	140	59	59
89	142	32	34
90	143	88	90

The "predicted" values are calculated using the equation

LS/K = n * √8 / (m - n * log(3)/log(2))

which is derived empirically from the next chart. The product of LS/K and (m−n * log(3)/log(2)) is nearly linear:

The gradient is about 0.35, which roughly 1/√8, the constant I used to predict the LS/K values in the earlier table.

(m - n * log(3)/log(2)) varies irregularly in the range 0 - 1. LS/K values will be at their largest when it is close to 0.

The next chart shows the values of LS/K (predicted) out to n=1500. Note the bulk of the values are close to the 0.35n line which forms the lower bound. However, some of the outriders are significantly higher, here by up to a factor of 1000.

Notable values are summarised in the next table, which covers n up to 100,000,000.

n	m	m-n*log(3)/log(2)	n/√8	LS/K (pred)	LS/K (calc)
3	5	0.245112	1.06	4	4
5	8	0.075187	1.77	23	24
17	27	0.055637	6.01	108	108
29	46	0.036087	10.25	284	281
41	65	0.016537	14.50	876	867
94	149	0.013525	33.23	2,457	2,419
147	233	0.010512	51.97	4,943	4,862
200	317	0.007500	70.71	9,428	9,266
253	401	0.004487	89.45	19,933	19,584
306	485	0.001475	108.19	73,358	72,058
971	1,539	0.001412	343.30	243,165	238,670
1,636	2,593	0.001349	578.41	428,829	420,841
2,301	3,647	0.001286	813.53	632,680	620,858
2,966	4,701	0.001223	1048.64	857,529	841,477
3,631	5,755	0.001160	1283.75	1,106,796	1,086,054
4,296	6,809	0.001097	1518.87	1,384,686
4,961	7,863	0.001034	1753.98	1,696,431
5,626	8,917	0.000971	1989.09	2,048,618
6,291	9,971	0.000908	2224.20	2,449,663
6,956	11,025	0.000845	2459.32	2,910,491
7,621	12,079	0.000782	2694.43	3,445,545
8,286	13,133	0.000719	2929.54	4,074,330
8,951	14,187	0.000656	3164.66	4,823,840
9,616	15,241	0.000593	3399.77	5,732,537
10,281	16,295	0.000530	3634.88	6,857,158
10,946	17,349	0.000467	3870.00	8,285,043
11,611	18,403	0.000404	4105.11	10,157,974
12,276	19,457	0.000341	4340.22	12,722,434
12,941	20,511	0.000278	4575.33	16,448,126
13,606	21,565	0.000215	4810.45	22,354,632
14,271	22,619	0.000152	5045.56	33,149,032
14,936	23,673	0.0000892	5280.67	59,181,261
15,601	24,727	0.0000262	5515.79	210,131,286
47,468	75,235	0.0000158	16782.47	1,064,327,305
79,335	125,743	0.00000529	28049.16	5,305,246,769
190,537	301,994	0.0000000930	67365.00	724,231,494,698
10,781,274	17,087,915	0.0000000149	3811755.98	255,802,613,502,959
75,278,381	119,313,411	0.0000000149	26614926.84	1,786,097,505,737,402

The linear relationship appears to hold for at least n values up to 3600, but using 1/√8 as the constant of proportionality appears to overestimate the values by about 2%. 0.36 would be closer. This doesn't really effect the result though. To find loops given that the smallest value must be greater than 1015 we need to search loops with at least 194 million members.

I stopped calculating LS/K at n = 3631 as the K value has 1730 digits.

Other pages