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

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

Algorithmically it looks like this:

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.

Let's select the total number of details to

Consider the sequence for n = 7:

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

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.

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,

The same sequence can be described by the recursive formula:

$$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$$3 n + 1 several times, this can be written as$$2 2 α where$$α is the number of divisions.

The final formula takes the form:

We also introduce an amendment to $$β as$$2 2 α + β 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:

$$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, 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 calculated

$$n ( 85 , 0 , 2 ) = ( 2 0 + 2 ∗ 85 - 1 ) / 3 = 113. To

summarize:

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

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

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

$$P ( m ) = ( 4 3 m - 1 ) / 3 - does not produce child sequences.

$$P ( m ) = ( 4 3 m + 1 - 1 ) / 3 - produces child sequences with$$β = 2 .

$$P ( m ) = ( 4 3 m + 2 - 1 ) / 3 - produces child sequences with$$β = 1 .

There are only 3 potential child sets in the number.

If applied to a recursive formula, then:

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.

Below is the final example of the javascript function implementation:

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) |
---|---|---|---|---|---|---|---|---|---|---|---|---|

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 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:$$P ( k ) = 4 k - 13 .

The same sequence can be described by the recursive formula:

$$P ( k ) = 4 k 0 + 1 , p p and 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$$3 n + 1 several times, this can be written as$$2 2 α where$$α is the number of divisions.

$$P ( k ) = 3 n + 12 2 α ;2 2 α P ( k ) = 3 n + 1 ;3 n = 2 2 α P ( k ) - 1 ;

The final formula takes the form:

$$n ( P ( k ) , α ) = 2 2 α P ( k ) - 13 ;

We also introduce an amendment to $$β as$$2 2 α + β to avoid the option of dividing a number not a multiple of 3 by 3.

$$n ( P ( k ) , α , β ) = 2 2 α + β P ( k ) - 13 ;

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

$$n ( 5 , α , β ) = 2 2 α + β ∗ 5 - 13 ;

$$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, 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 calculated

**from 5**.**n = 113**actually:$$n ( 85 , 0 , 2 ) = ( 2 0 + 2 ∗ 85 - 1 ) / 3 = 113. To

summarize:

Set from $$S a ( n + 1 ) is generated by the function$$n ( P ( k ) , α , β ) of each element of the set of$$S a ( 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 $$S a ( 2 ) generate elements of the set from$$S a ( 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 $$α > 0 , we get:

17, 75, 151 ...That is, it all comes down to:

$$n ( P ( k ) , β ) = 2 β P ( k ) - 13 ;

**Why somewhere $$β = 2 , and somewhere$$β = 1 ?**Let's go back to the sequence A002450. There is an interesting relationship:

$$P ( m ) = ( 4 3 m - 1 ) / 3 - does not produce child sequences.

$$P ( m ) = ( 4 3 m + 1 - 1 ) / 3 - produces child sequences with$$β = 2 .

$$P ( m ) = ( 4 3 m + 2 - 1 ) / 3 - produces child sequences with$$β = 1 .

There are only 3 potential child sets in the number.

If applied to a recursive formula, then:

Function $$n ( γ , α , β ) , where$$γ is any multiple of 3, forms an empty set ⨂.$$A ( n ( γ ) , α , β ) = ⨂ .

Function $$n ( λ , α , β ) , where$$λ - any number generated$$γ , with$$β = 2 forms the set of numbers K belonging to the set of natural numbers N.$$K ( n ( P ( γ ) , α , 2 ) ) ⊆ N .

Function $$n ( P ( λ ) , α , β ) , with$$β = 1 forms the set of numbers L belonging to the set of natural numbers N.$$L ( n ( P ( λ ) , α , 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:

$$

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.