3
$\begingroup$

I am a web developer that programs in PHP which is limited to large math calculations.

I am also a math enthusiastic that likes learning math through problems that seem simple (but are anything like simple), and the best example is the Collatz Conjecture.

I am not dilusional and I am well aware that there is no chances for someone at my level to solve the Collatz Conjecture, but I like to try and solve other elements that may be related.

Let's begin with the description of the conjecture: According to the rules of the Collatz Conjecture if $𝑛$ is odd then execute $3𝑛+1$ and when $𝑛$ is even execute $𝑛/2$. Repeat until (supposedly) reaching $𝑛=1$.

So I was trying to prove the most basic variant: If $𝑛$ is odd then execute $𝑛+1$ and when $𝑛$ is even execute $𝑛/2$. Repeat until (supposedly) reaching 𝑛=1.

I was able to proof it in my own head,

So I progressed into trying to prove: If $𝑛$ is odd then execute $𝑛+π‘₯$ and when $𝑛$ is even execute $𝑛/2$. Repeat until (supposedly) reaching $𝑛=1$. So obviously sometimes it reached 1 and some times it reached π‘₯.

I was able to proof it in my own head.

So I realized that I had to find a different approach for when 𝑛 is odd that is more than just adding a constant.

So I decided to add $1$ for the first odd occurrence, $3$ to the second odd occurrence, $5$ to the third odd occurrence , $7$ to the fourth odd occurrence .... (with increments of $+ 2$)

I have then ran a PHP script with a list of the first 2500 odd numbers, with a limit accepted of 10000 steps.

I immediately noticed that most numbers ended in 1, example:

$13 β†’ 14 β†’ 7 β†’ 10 β†’ 5 β†’ 10 β†’ 5 β†’ 12 β†’ 6 β†’ 3 β†’ 12 β†’ 6 β†’ 3 β†’ 14 β†’ 7 β†’ 20 β†’ 10 β†’ e5 β†’ o20 β†’ 10 β†’ 5 β†’ 22 β†’ 11 β†’ 30 β†’ 15 β†’ 36 β†’ 18 β†’ 9 β†’ 32 β†’ 16 β†’ 8 β†’ 4 β†’ 2 β†’ 1$

but then there were numbers that had so many steps and were cut by the accepted $10000$ steps of my script.

I have then checked a specific number that seemed to have endless steps, which is the beginning number $21$.

To my surprise there were no loops but I have noticed that there seemed to be a pattern that shows growing into infinity.

Fo example the beginning number of $21$:

$21 β†’ 22 β†’ 11 β†’ 14 β†’ 7 β†’ 12 β†’ 6 β†’ 3 β†’ 10 β†’ 5 β†’ 14 β†’ 7 β†’ 18 β†’ 9 β†’ 22 β†’ 11 β†’ 26 β†’ 13 β†’ 30 β†’ 15 β†’ o34 β†’ 17 β†’ 38 β†’ 19 β†’ 42 β†’ 21 β†’ 46 β†’ 23 β†’ 50 β†’ 25 β†’ 54 β†’ 27...$

I have then noticed that all the numbers that seem to have endless steps reach $6 β†’ 3 β†’ 10 β†’ 5 β†’ 14 β†’ 7 β†’ 18....$

Which seems to be a pattern that grows into infinity,

So my question is how can I prove that:

Starting with $6$ and then first odd occurrence ($3$) add $7$, second odd occurrence add $9$, third odd occurrence add $11$... will always grow infinitely (*Note the sequence/pattern of odd β†’ even β†’ odd β†’ even...)?

Do all these numbers that seem to have endless steps, begin the endless path through $6 β†’ 3 β†’ 10 β†’ 5 β†’ 14 β†’ 7 β†’ 18....$ ? In other words is that the only path to infinite steps in my presented variant?

$\endgroup$
2
  • 1
    $\begingroup$ +1 ; what is the importance of Collatz Conjecture ?? $\endgroup$ Feb 27, 2021 at 8:37
  • 2
    $\begingroup$ @haidangel for me personally it is not important, but it’s a brain exercise. Not trying to solve the conjecture, but rather learn from it $\endgroup$ Feb 27, 2021 at 8:46

1 Answer 1

3
$\begingroup$

This is the sequence https://oeis.org/A066070, and yes it continues indefinitely. The pattern is

$$2x \to x \to 2x+4 \to x+2 \to 2x+8 \to x + 4 \to \dots$$

Notice that whenever an odd number $n$ is in the sequence, the number $n+4$ is added to it. This can be formally proven by induction.

EDIT: incomplete answer to follow-up question: this is the only loop of this "kind". If we have:

$$n \to 2n+2a \to n+a \to 2n+3a+2 \to n+\frac32a+1\to\dots$$

we have $n+2a = n + \dfrac32 a + 1$, giving $a=2$. If we have:

$$n \to 4n + 4a \to\to n+a \to 4n+4a + 2\to2n + 2a + 1$$

we already start breaking the pattern. Therefore there are no more "short, double-arithmetic-sequence loops". Whether a larger or irregular loop exists requires some more thought. For all values that fell into a loop that I have checked, it eventually falls into this loop.

$\endgroup$
2
  • 1
    $\begingroup$ Is that the only one ? I mean starting at 6 (or 3 as the odd) $\endgroup$ Feb 27, 2021 at 8:34
  • 1
    $\begingroup$ What is that sequence called ? $\endgroup$ Feb 27, 2021 at 8:35

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.