Introduction

The forward equation we introduced above is quite straight forward . When dealing with the odd numbers only, when we look in the opposite direction every odd number not divisible by three has an infinite number of immediate precursors. This page explores identifying those numbers.

Although the forward equation we introduced earlier is quite easy to calculate, as it is a one to one mapping, calculating the precursors of a given number is more interesting. Looking at "1", we see that it is preceded by the infinite sequence of powers of 2. On this site, though we are focusing focusing on the odd numbers, and we will see below, every odd number that isn't a multiple of 3 has an infiniite number of odd precursors.

To find the precursors of 1 we have to find powers of two that fit the equation

2k = 3x+1 ⇒ x = (2k-1) / 3

Where x is an integer. Only even values of k lead to integer solutions, giving;

k	(2k-1) / 3
2	(4-1)/3 = 1
4	(16-1)/3 = 5
6	(64-1)/3 = 21
8	(256-1)/3 = 85

k	(2k-1) / 3
10	(1024-1)/3 = 341
12	(4096-1)/3 = 1,365
14	(16384-1)/3 = 5,461
16	(65536-1)/3 = 21,845

For numbers other than 1, say 'A', we get the similar equation

A.2k = 3x+1  ⇒ (A.2k-1) / 3

Calculating x for a few values of A and k we can see a pattern;

x(A,k)	k = 2	k = 4	k = 6
A = 1	1	5	21
A = 7	9	37	149
A = 13	17	69	277

x(A,k)	k = 1	k = 3	k = 5
A = 5	3	13	53
A = 11	7	29	117
A = 17	11	45	181

When A is a multiple of three we get no predecessors, as a multiple of three can't be of the form 3x+1. When A is one more than a multiple of 6, k will be even, and when it is one less than a multiple of 6, k will be odd. The smallest precursors are therefore:

6n+1 → 8n+1
6n+5 → 4n+3.

When reading down the columns the values increase arithmetically in steps of x → x + 2(k+1), whereas across the table they increase geometrically as x → 4x+1.

Try it for yourself

Starting number:

Predecessors:

More examples

The next two tables are extensions of the previous tables, but now the numbers are colour-coded according to their remainders when divided by 6.

A\k 2 4 6 8 10 12 14 16 18

1 1 5 21 85 341 1,365 5,461 21,845 87,381

7 9 37 149 597 2,389 9,557 38,229 152,917 611,669

13 17 69 277 1,109 4,437 17,749 70,997 283,989 1,135,957

19 25 101 405 1,621 6,485 25,941 103,765 415,061 1,660,245

25 33 133 533 2,133 8,533 34,133 136,533 546,133 2,184,533

31 41 165 661 2,645 10,581 42,325 169,301 677,205 2,708,821

A\k	2	4	6	8	10	12	14	16	18
1	1	5	21	85	341	1,365	5,461	21,845	87,381
7	9	37	149	597	2,389	9,557	38,229	152,917	611,669
13	17	69	277	1,109	4,437	17,749	70,997	283,989	1,135,957
19	25	101	405	1,621	6,485	25,941	103,765	415,061	1,660,245
25	33	133	533	2,133	8,533	34,133	136,533	546,133	2,184,533
31	41	165	661	2,645	10,581	42,325	169,301	677,205	2,708,821

A\k 1 3 5 7 9 11 13 15 17

5 3 13 53 213 853 3,413 13,653 54,613 21,8453

11 7 29 117 469 1,877 7,509 30,037 120,149 480,597

17 11 45 181 725 2,901 11,605 46,421 185,685 742,741

23 15 61 245 981 3,925 15,701 62,805 251,221 1,004,885

29 19 77 309 1,237 4,949 19,797 79,189 316,757 1,267,029

A\k	1	3	5	7	9	11	13	15	17
5	3	13	53	213	853	3,413	13,653	54,613	21,8453
11	7	29	117	469	1,877	7,509	30,037	120,149	480,597
17	11	45	181	725	2,901	11,605	46,421	185,685	742,741
23	15	61	245	981	3,925	15,701	62,805	251,221	1,004,885
29	19	77	309	1,237	4,949	19,797	79,189	316,757	1,267,029

Notice that numbers of the form 6n+5 have a smaller odd predecessor. This can be used to generate arbitrary long sequences of numbers where (3x+1)/2 is odd and (3×(3x+1)/2+1) is larger than 3x+1, see blue chains, below.

The colour patterns repeat every 3 rows, as we can see from the following tables

A\k 2 4 6

18n+1 24n+1 = 6.(4n)+1 96n+5 = 6.(16n)+5 384n+21 = 6.(64n+3)+3

18n+7 24n+9 = 6.(4n+1)+3 96n+37 = 6.(16n+6)+1 384n+149 = 6.(64n+24)+5

18n+13 24n+17 = 6.(4n+2)+5 96n+69 = 6.(16n+11)+3 384n+277 = 6.(64n+46)+1

A\k	2	4	6
18n+1	24n+1 = 6.(4n)+1	96n+5 = 6.(16n)+5	384n+21 = 6.(64n+3)+3
18n+7	24n+9 = 6.(4n+1)+3	96n+37 = 6.(16n+6)+1	384n+149 = 6.(64n+24)+5
18n+13	24n+17 = 6.(4n+2)+5	96n+69 = 6.(16n+11)+3	384n+277 = 6.(64n+46)+1

A\k 1 3 5

18n+5 12n+3 = 6.(2n)+3 48n+13 = 6.(8n+2)+1 192n+53 = 6.(32n+8)+5

18n+11 12n+7 = 6.(2n+1)+1 48n+29 = 6.(8n+4)+5 192n+117 = 6.(128n+19)+3

18n+17 12n+11 = 6.(2n+1)+5 48n+45 = 6.(8n+7)+3 192n+181 = 6.(128n+30)+1

A\k	1	3	5
18n+5	12n+3 = 6.(2n)+3	48n+13 = 6.(8n+2)+1	192n+53 = 6.(32n+8)+5
18n+11	12n+7 = 6.(2n+1)+1	48n+29 = 6.(8n+4)+5	192n+117 = 6.(128n+19)+3
18n+17	12n+11 = 6.(2n+1)+5	48n+45 = 6.(8n+7)+3	192n+181 = 6.(128n+30)+1

Blue Chains

We have been colouring the numbers according to their remainder when divided by 6. Numbers of the form 6n+5, which we call blue numbers, always have a predecessor of the form 4n+3 (which for large n is about 2/3rds of the starting value) eg.

The colour of the this smallest node varies but a third of the time it will also be blue, so we can start constructing a chain of blue numbers, each one roughly 2/3rds of its predecessor. So for 17 in the above list we can construct the larger tree;

Examining a few of these trees we can see that sequences of decreasing blue nodes end in a number of the form 3×2n-1. The numbers in this sequence start with [5,11,23,47,95,191,...]. If we take a number of this form and put it through the (3x+1)/2 equation n-1 times we get 2×3n-1

For instance

n Sequence

1 [5]

2 [11,17]

3 [23,35, 53]

4 [47, 71, 107, 161]

5 [95, 143, 215, 323, 485]

6 [191, 287, 431, 647, 971, 1457]

7 [383, 575, 863, 1295, 1943, 2915, 4373]

All the numbers in the above table are of the form 6n+5 and appear blue in the diagram. This shows that we can create an arbitrarily long sequence of increasing values, just by increasing the value of n.

The figure on the left shows the tree generated by these first seven sequences.

The end number divided by the start (for large n) is 2×3n/3*2n, or (1.5)n-1. Here

log(Max(N))/log(N) = (log(2)+n*log(3))/(log(3)+n*log(2))

which converges on log(3)/log(2), about 1.5849625007211563. If there is a limit to log(Max(N))/log(N), it must be at least this large. This chart shows the largest value of log(Max(N))/log(N) for successive ranges of N of the form (2i to 2i+1-1).

The dotted line is log(3)/log(2). The highlights are

27 → 3077, ratio = 2.4369
41 → 3077, ratio = 2.1628
270271 → 8216025965, ratio = 1.8253

This chart shows the path taken by 270271. The Y axis is Log₁₀.

If we continue we find that 6,631,675 gives a log (Max(N))/log(N) of 1.9502. So, although this blue chains method will find sequences where log (Max(N))/log(N) is about 1.585, there are series with larger values.

The image on the left was drawn using GraphViz, see http://www.research.att.com/sw/tools/graphviz/

Applying Reverse Iteration

Introduction

In blue chains we noticed that except for 27 and 41, log (Max(N))/log(N) doesn't appear to exceed 2. Though I can't prove this is true I can assume it and use it as the basis of a backwards searching algorithm for numbers that converge on a particular root. For instance if I want to find all the numbers than converge on 85 that are less than 1024 I can reject sequences that pass through numbers greater than 1024 squared (1048576).

Applying this algorithm gives us the following results;

Start (1 value):

[85]

First iteration (7 values):

[113, 453, 1813, 7253, 29013, 116053, 464213]

2nd iteration (19 values):

[75, 301, 1205, 4821, 19285, 77141, 308565, 2417, 9669, 38677, 154709,
618837, 4835, 19341, 77365, 309461, 154737, 618949, 309475]

3rd iteration (39 values):

[401, 1605, 6421, 25685, 102741, 410965, 803, 3213, 12853, 51413, 205653,
822613, 25713, 102853, 411413, 51427, 205709, 822837, 1611, 6445, 25781, 103125, 412501,
51569, 206277, 825109, 103139, 412557, 3223, 12893, 51573, 206293, 825173, 103153, 412613,
206307, 825229, 825265, 412633]

The results are summarised in the table below where you will see that the search reaches a maxmum width of 357 at iteration 18.

This chart shows the location of the found values (numbers less than 1024) in each row of the table. All the target values were found in the first 8 rows (7 iteration, the first value is 85 itself). These are the green cells in the table below.

This second chart shows the width (vertical axis) and depth (horizontal) of the search tree, and includes all for odd numbers up to 1048576 that we examined. Although we found all the values we were looking for in the first 7 iterations, the algorithm itself didn't stop until 60 iterations, after it had examined 7582 values.

Testing the 511 values smaller than 1024 would have been quicker. You can see the corresponding tree here.

To get numbers out to 4096 this algorithm requires that 118564 possibilities be explored, for 8192 this grows to 468857, just to find the first 99 values that converge on 85. This chart shows the distribution of those 99 values in terms of the number of odd-hops from the root.

As we double the depth to search we roughly quadruple the set of values to search.

So it's not looking that good an algorithm.

Searching for values out to 1024

Iteration Tree Width Five smallest values

0 1 85

1 7 113 453 1813 7253 29013

2 19 75 301 1205 2417 4821

3 39 401 803 1605 1611 3213

4 60 267 535 1069 2141 4277

5 101 713 1425 1427 2851 2853

6 156 475 951 1901 3801 3805

7 177 633 1267 2533 5067 5069

8 232 1689 3377 3379 6755 6757

9 230 2251 4503 4505 9005 9009

10 276 3001 3003 6003 6007 6011

11 339 4001 4007 8003 8007 8009

12 316 2667 2671 5335 5339 5343

13 354 3559 3561 7113 7119 7123

14 305 4745 9483 9491 9497 18967

15 329 3163 6327 6331 12653 12655

16 278 4217 8435 8441 16859 16869

17 308 2811 5623 5627 11239 11245

18 357 3751 7497 7503 14985 14993

19 305 5001 9995 10003 19991 19993

20 321 6663 13327 13337 13343 26653

21 259 8891 8895 17769 17771 17775

22 261 5927 11847 11855 23691 23695

23 294 3951 7903 15805 31593 31599

24 232 10537 21073 21075 42119 42123

25 245 14049 28079 28097 28099 56159

26 181 18719 18731 37439 37463 37465

27 176 12479 12487 24959 24975 24991

28 137 8319 16639 16649 33263 33277

29 138 11099 22175 22185 22199 44351

30 139 7399 14783 14799 29567 29579

31 106 9855 9865 19711 19719 19731

32 108 13153 26281 26307 52561 52563

33 88 17537 35041 35075 35079 35103

34 89 11691 23383 46721 46765 93441

35 93 31147 31177 62295 62353 62355

36 70 41529 41569 41575 83059 83099

37 72 55399 55425 55433 55471 110745

38 57 36955 73865 73899 73911 73961

39 51 49243 49273 49307 98439 98487

40 40 32871 65657 65697 65743 131315

41 36 43771 87543 87657 175003 175007

42 36 58361 116671 116723 116783 116795

43 28 38907 77815 77855 77863 155559

44 30 51903 103707 103753 103817 207415

45 20 69211 138337 138423 276553 276673

46 18 92281 184449 184551 184563 368737

47 17 123041 245931 246059 246083 491643

48 9 82027 164039 164055 327915 328109

49 9 109359 109369 218739 437437 437477

50 5 145825 291651 583249 583301 583307

51 5 194433 388867 388871 777665 777733

52 5 259247 518443 518489 1036977 1036989

53 4 172831 345659 691257 691325

54 5 230439 230441 460883 921757 921765

55 3 153627 307255 614509

56 2 409673 819345

57 1 273115

58 1 364153

59 1 485537

60 1 323691

Iteration	Tree Width	Five smallest values
0	1	85
1	7	113	453	1813	7253	29013
2	19	75	301	1205	2417	4821
3	39	401	803	1605	1611	3213
4	60	267	535	1069	2141	4277
5	101	713	1425	1427	2851	2853
6	156	475	951	1901	3801	3805
7	177	633	1267	2533	5067	5069
8	232	1689	3377	3379	6755	6757
9	230	2251	4503	4505	9005	9009
10	276	3001	3003	6003	6007	6011
11	339	4001	4007	8003	8007	8009
12	316	2667	2671	5335	5339	5343
13	354	3559	3561	7113	7119	7123
14	305	4745	9483	9491	9497	18967
15	329	3163	6327	6331	12653	12655
16	278	4217	8435	8441	16859	16869
17	308	2811	5623	5627	11239	11245
18	357	3751	7497	7503	14985	14993
19	305	5001	9995	10003	19991	19993
20	321	6663	13327	13337	13343	26653
21	259	8891	8895	17769	17771	17775
22	261	5927	11847	11855	23691	23695
23	294	3951	7903	15805	31593	31599
24	232	10537	21073	21075	42119	42123
25	245	14049	28079	28097	28099	56159
26	181	18719	18731	37439	37463	37465
27	176	12479	12487	24959	24975	24991
28	137	8319	16639	16649	33263	33277
29	138	11099	22175	22185	22199	44351
30	139	7399	14783	14799	29567	29579
31	106	9855	9865	19711	19719	19731
32	108	13153	26281	26307	52561	52563
33	88	17537	35041	35075	35079	35103
34	89	11691	23383	46721	46765	93441
35	93	31147	31177	62295	62353	62355
36	70	41529	41569	41575	83059	83099
37	72	55399	55425	55433	55471	110745
38	57	36955	73865	73899	73911	73961
39	51	49243	49273	49307	98439	98487
40	40	32871	65657	65697	65743	131315
41	36	43771	87543	87657	175003	175007
42	36	58361	116671	116723	116783	116795
43	28	38907	77815	77855	77863	155559
44	30	51903	103707	103753	103817	207415
45	20	69211	138337	138423	276553	276673
46	18	92281	184449	184551	184563	368737
47	17	123041	245931	246059	246083	491643
48	9	82027	164039	164055	327915	328109
49	9	109359	109369	218739	437437	437477
50	5	145825	291651	583249	583301	583307
51	5	194433	388867	388871	777665	777733
52	5	259247	518443	518489	1036977	1036989
53	4	172831	345659	691257	691325
54	5	230439	230441	460883	921757	921765
55	3	153627	307255	614509
56	2	409673	819345
57	1	273115
58	1	364153
59	1	485537
60	1	323691

Tree routed on 85

This picture shows the tree containing all the numbers less than 1024 that converge on 85 = (256-1)/3. 633 is the furthest out, being 30 iterations from 1. Even numbers are omitted, being encapsulated in the small white boxes, for instance the '4' steps between 803 and 2141 includes 1606, 3212 and 6424.

The Collatz Conjecture

Contents

Introduction

Try it for yourself

More examples

Blue Chains

Applying Reverse Iteration

Introduction

Searching for values out to 1024

Tree routed on 85

Other pages

n	Sequence
1	[5]
2	[11,17]
3	[23,35, 53]
4	[47, 71, 107, 161]
5	[95, 143, 215, 323, 485]
6	[191, 287, 431, 647, 971, 1457]
7	[383, 575, 863, 1295, 1943, 2915, 4373]