# 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 perfectly train the head, 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 by n = 5: 16, 8, 4, 2, 1.

I ask you to forgive me for my math, let me know if I make a mistake somewhere.

Let's select the total number of details to e Nij to unity and the true number of details to e Nij unit. 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) is 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)
2five317eleven792533435739105
fourten6342214184965865978203
eight2012352315nineteen50668711479209
sixteen211368442836516789115153210
3240246945293798130182118156211
6442267046thirty3899131173119157406
128804875885672100132174228158407
2568452136905874101133177229305409
5128553138926077102134178230306418

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.



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)
five317eleven792533435739105
2113352315nineteen4965875979203
855369452937516789115153209
3411137593617799131173119157211
136521314118111781101133177229305407

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 that 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:



The same sequence can be described by the recursive formula:






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 several times, this can be written as where is the number of divisions.



The final formula takes the form:



We also introduce an amendment to  as to avoid the option of dividing a number not a multiple of 3 by 3.



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









Thus, the 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 calculatedfrom 5.

n = 113actually:


summarize:
Set from  generated by the function of each element of the set of .
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) ...
five317eleven79...
11375201267715...
22715140110731425...

To be clear, here is an example of how the elements of a set from  generate elements of the set from for alpha from 0 to 4.
P (k) = 3P (k) = 113P (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  , we get:
17, 75, 151 ...
That is, it all comes down to:



Why somewhere  , and somewhere ?

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

 - does not produce child sequences.
 - produces child sequences with .
 - produces child sequences with .

There are only 3 potential child sets in the number.
If applied to a recursive formula, then:
Function  , where is any multiple of 3, forms an empty set ⨂.



Function  , where - any number generated , with forms the set of numbers K belonging to the set of natural numbers N.



Function  , with forms the set of numbers L belonging to the set of natural numbers 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:



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



It remains only to relate everything together:



Final version:



Thus, any k can generate a sequence.
Is it the reverse that any of the natural numbers definitely belongs to any sequence from ?
If so, then it is entirely possible that Collatz was right.

Below is the final example of the javascript function implementation:

functioncollatsSequence(
number,
sequenceLength,
alpha,
epsilon
) {
// Массив множества от истинного шага,// определяемого numberlet set = [];
// Сводим к нечетномуwhile (number % 2 === 0) number /= 2;
// Для каждого элемента последовательности, // образованной от number, ограничиваясь sequenceLengthfor (let k = 0; k < sequenceLength; k++) {
// Для каждой степени alphafor (let a = 0; a < alpha; a++) {
// Пустое множество, пропускаемif (number % 3 === 0) break;
// Рассчитываем для beta = 1let numWithBeta = (number * 2 ** (2 * a + 1) - 1) / 3;
// Если число не делится на 3 при beta === 1// тогда точно делится на 3 при beta === 2if (Math.floor(numWithBeta) !== numWithBeta)
// Рассчитываем для beta = 2
numWithBeta = (number * 2 ** (2 * a + 2) - 1) / 3;
// Заполняем множество четными до предела epsilonfor (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 ]

Only registered users can participate in the survey. Sign in , please.