On the formation of sequences in the Collatz hypothesis (3n + 1)

I am attracted to such tasks as the Collatz problem. They are easy to formulate and train the head very well, especially algorithmic thinking, which is very useful for the programmer.

The task is formulated quite simply:

Take any positive integer n. If it is even, then divide it by 2, and if it is odd, then multiply by 3 and add 1 (we get 3n + 1). On the resulting number, perform the same actions, and so on.

Collatz’s hypothesis is that whatever initial number n we take, sooner or later we will get one.

Algorithmically it looks like this:
')

while (number > 1) { if (number % 2 === 0) number = number / 2; else number = 3 * number +1; } 

For example, take n = 5. It is odd, so we perform the action on odd, that is, 3n + 1 => 16. 16 is even, then we perform the action on even, that is, n / 2 => 8 => 4 => 2 => 1.
The sequence formed when n = 5: 16, 8, 4, 2, 1.

I ask you to forgive me for my math, let me know if somewhere wrong.

Let's select the total number of units reduced to one and the true amount of units reduced to one. Let's mark it by the steps.

Consider the sequence for n = 7:

22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

There are 16 steps in total. And there are 5 true steps that are actually transferred to another number set:

7, 11, 17, 13, 5.

The true step Sa (n) will be called the number of operations 3n + 1 over the number needed to reach unity.

The idea is clearly demonstrated on the example of the table:

Sn (0)	Sn (1)	Sn (2)	Sn (3)	Sn (4)	Sn (5)	Sn (6)	Sn (7)	Sn (8)	Sn (9)	Sn (10)	Sn (11)	Sn (12)
2	five	3	17	eleven	7	9	25	33	43	57	39	105
four	ten	6	34	22	14	18	49	65	86	59	78	203
eight	20	12	35	23	15	nineteen	50	66	87	114	79	209
sixteen	21	13	68	44	28	36	51	67	89	115	153	210
32	40	24	69	45	29	37	98	130	182	118	156	211
64	42	26	70	46	thirty	38	99	131	173	119	157	406
128	80	48	75	88	56	72	100	132	174	228	158	407
256	84	52	136	90	58	74	101	133	177	229	305	409
512	85	53	138	92	60	77	102	134	178	230	306	418

In such a table, the order is already peeping, its regularity.
As you can see, the power of two will never become odd, so it all comes down to a simple division.
The sequence from Sa (0) is formed with only 1 formula.

$$

$$P (0, k) = 2 * 2 ^ k.$$

No true steps are needed, simple division will reduce everything to unity.
Knowing this, you can drop all the numbers that are a multiple of two from the table.

Sn (0)	Sn (1)	Sn (2)	Sn (3)	Sn (4)	Sn (5)	Sn (6)	Sn (7)	Sn (8)	Sn (9)	Sn (10)	Sn (11)	Sn (12)
	five	3	17	eleven	7	9	25	33	43	57	39	105
	21	13	35	23	15	nineteen	49	65	87	59	79	203
	85	53	69	45	29	37	51	67	89	115	153	209
	341	113	75	93	61	77	99	131	173	119	157	211
	1365	213	141	181	117	81	101	133	177	229	305	407

Now it is more difficult to catch the pattern, but it is. Now the most interesting thing is the formation of sequences. Not just the next number after 5 is 21, and after it 85.
In fact, Sa (1) is the sequence A002450 (0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381 ...). It is formed by the formula:

$$

$$P (k) = {4 ^ k- 1 \ over 3}.$$

The same sequence can be described by the recursive formula:

$$

$$P (k) = 4k_0 + 1, with \ k_0 = 1.$$

$$$P (1) = 4 * 1 + 1 = 5;$
$$$P (5) = 4 * 5 + 1 = 21;$
$$$P (21) = 4 * 21 + 1 = 85;$
And so on…

The series of the first step is constructed, although it can continue indefinitely. Let's go to step two. The formula for the transition to step 2 can be expressed from an odd formula.
Knowing that we are going to share the result $$$3n + 1$ several times, it can be written as $$$2 ^ {2 \ alpha}$ where $$$\ alpha$ - the number of divisions.

$$

$$P (k) = {3n + 1 \ over2 ^ {2 \ alpha}}; \\ 2 ^ {2 \ alpha} P (k) = 3n + 1; \\ 3n = 2 ^ {2 \ alpha} P (k) -1;$$

The final formula takes the form:

$$

$$n (P (k), \ alpha) = {2 ^ {2 \ alpha} P (k) -1 \ over3};$$

We also introduce an amendment to $$$\ beta$ , as $$$2 ^ {2 \ alpha + \ beta}$ to avoid the option of dividing a number not a multiple of 3 by 3.

$$

$$n (P (k), \ alpha, \ beta) = {2 ^ {2 \ alpha + \ beta} P (k) -1 \ over3};$$

Let's check the formula, since alpha is unknown, check for 5 alphas in succession:

$$

$$n (5, \ alpha, \ beta) = {2 ^ {2 \ alpha + \ beta} * 5-1 \ over3};$$

$$$n (5,0,1) = (2 ^ {0 + 1} * 5-1) /3=3.$
$$$n (5,1,1) = (2 ^ {2 + 1} * 5-1) /3=13.$
$$$n (5,2,1) = (2 ^ 5 * 5-1) /3=53.$
$$$n (5,3,1) = (2 ^ 7 * 5-1) /3=213.$
$$$n (5,4,1) = (2 ^ 9 * 5-1) /3=853.$

Thus, a sequence of the second step begins to form. However, it can be noted that 113 is not in sequence, it is important to remember that the formula was calculated from 5 .

n = 113 actually:
$$$n (85,0,2) = (2 ^ {0 + 2} * 85-1) /3=113.$

Summing up:

Set from $$$Sa (n + 1)$ generated by function $$$n (P (k), \ alpha, \ beta)$ from each element of the set from $$$Sa (n)$ .

Then, knowing this - you can still reduce the table, removing all the generations multiples of alpha.

Sn (0)	Sn (1)	Sn (2)	Sn (3)	Sn (4)	Sn (5)	Sn (6)	Sn (7) ...
	five	3	17	eleven	7	9	...
		113	75	201	267	715	...
		227	151	401	1073	1425	...

To be clear, here is an example of how the elements of a set from $$$Sa (2)$ generate elements of the set from $$$Sa (3)$ for alpha from 0 to 4.

P (k) = 3	P (k) = 113	P (k) = 227
3 from α = 0 generates: Nothing 13 from α = 1 generates: 17 69 277 1109 4437 53 from α = 2 generates: 35 141 565 2261 9045 213 from α = 3 generates: Nothing 853 from α = 4 generates: 1137 4549 18197 72789 291157	113 from α = 0 generates: 75 301 1205 4821 19285 453 from α = 1 generates: Nothing 1813 from α = 2 generates: 2417 9669 38677 154709 618837 7253 from α = 3 generates: 4835 19341 77365 309461 1237845 29013 from α = 4 generates: Nothing	227 from α = 0 generates: 151 605 2421 9685 38741 909 from α = 1 generates: Nothing 3637 from α = 2 generates: 4849 19397 77589 310357 1241429 14549 from α = 3 generates: 9699 38797 155189 620757 2483029 58197 from α = 4 generates: Nothing

Combining these sets, we get a set from Sa (3):

17, 35, 69, 75, 141, 151, 277, 301, 565, 605, 1109, 1137, 1205, 2261, 2275, 2417, 2421, 4437, 4549, 4821, 4835, 4849, 9045, 9101, 9669 9685, 9699, 17749, 18197, 19285, 19341, 19397, 19417 ...

And removing the degree $$$\ alpha> 0$ , we get:

17, 75, 151 ...

That is, it all comes down to:

$$

$$n (P (k), \ beta) = {2 ^ \ beta P (k) -1 \ over3};$$

Why somewhere $$$\ beta = 2$ , and somewhere $$$\ beta = 1$ ?

Let's go back to the sequence A002450. There is an interesting relationship:

$$$P (m) = (4 ^ 3m- 1) / 3$ - does not produce child sequences.
$$$P (m) = (4 ^ {3m + 1} - 1) / 3$ - produces child sequences when $$$\ beta = 2$ .
$$$P (m) = (4 ^ {3m + 2} - 1) / 3$ - produces child sequences when $$$\ beta = 1$ .

There are only 3 potential child sets in the number.
If applied to a recursive formula, then:

Function $$$n (\ gamma, \ alpha, \ beta)$ where $$$\ gamma$ - any number multiple of 3 forms an empty set ⨂.

$$

$$A (n (\ gamma), \ alpha, \ beta) = ⨂.$$

Function $$$n (\ lambda, \ alpha, \ beta)$ where $$$\ lambda$ - any number generated $$$\ gamma$ at $$$\ beta = 2$ forms a set of numbers K belonging to a set of natural numbers N.

$$

$$K (n (P (\ gamma), \ alpha, 2)) ⊆ N.$$

Function $$$n (P (\ lambda), \ alpha, \ beta)$ at $$$\ beta = 1$ forms a set of numbers L belonging to a set of natural numbers N.

$$

$$L (n (P (\ lambda), \ alpha, 1)) ⊆ N.$$

Obviously, this can somehow be reduced to a more rigorous and evidence-based formulation.

Actually, so are the sequences in the Collatz hypothesis.
Only one detail remained. It is necessary to restore the complete sets from the absolute steps from the sets obtained by us.

Formula for odd:

$$

$$n (P (k), \ alpha, \ beta) = {2 ^ {2 \ alpha + \ beta} P (k) -1 \ over3};$$

In addition to the odd, you need to restore a lot of even. To do this, recall the formula:

$$

$$P (0, k) = 2 * 2 ^ k.$$

It remains only to relate everything together:

$$

$$n (P (k), \ alpha, \ beta, \ epsilon) = {2 ^ {2 \ alpha + \ beta} P (k) -1 \ over3} * 2 ^ \ epsilon.$$

Final version:

$$

$$n (k, \ alpha, \ beta, \ epsilon) = 2 ^ \ epsilon {2 ^ {2 \ alpha + \ beta} (4k + 1) -1 \ over3};$$

Thus, any k can generate a sequence.

Is it the reverse that any of the natural numbers definitely belongs to any sequence from $$$n (k)$ ?

If so, then it is entirely possible that Collatz was right.

Below is the final example of the javascript function implementation:

 function collatsSequence( number, sequenceLength, alpha, epsilon ) { //     , //  number let set = []; //    while (number % 2 === 0) number /= 2; //    , //   number,  sequenceLength for (let k = 0; k < sequenceLength; k++) { //    alpha for (let a = 0; a < alpha; a++) { //  ,  if (number % 3 === 0) break; //   beta = 1 let numWithBeta = (number * 2 ** (2 * a + 1) - 1) / 3; //      3  beta === 1 //     3  beta === 2 if (Math.floor(numWithBeta) !== numWithBeta) //   beta = 2 numWithBeta = (number * 2 ** (2 * a + 2) - 1) / 3; //      epsilon for (let e = 0; e < epsilon; e++) set.push(numWithBeta * 2 ** e); } //      number = number * 4 + 1; } return set; } console.log( collatsSequence(5, 5, 2, 2) ); // [ 3, 6, 13, 26, 113, 226, 453, 906, 227, 454, 909, 1818 ]