7
$\begingroup$

I came across the Collatz conjecture. So apparently the idea is to see if all prime factors of a number can be 'annihilated' by successive steps of either removing a factor of two, if n is even or in case it is not to transform it by a simple '(e.g. linear) transformation' to an even number. Now the algorithm to accomplish that is:

Take $n$ and generate the sequence $f^i(n)$, with

$$f(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ 3n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases}$$

It seems a tough problem. I thought about the following simplified version:

$$g_0(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases}$$

The first question is can one show that all the sequences $g_0^i$ go to orbits $...,1,2,1,2,...$?

I think the answer must be yes, since there will never be members with prime factors larger than $\sqrt{n}$, so there is only a limited reservoir of possible prime factors which all in all are getting reduced by the steps. Is that about correct?

The next question is how far can one go with such variations on the original algorithm 'approching the normal one', For example what about:

$$g_1(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ n+3 & \text{if } n\equiv 1 \pmod{2} .\end{cases}$$

or

$$g_2(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ n+(n+1)/2 & \text{if } n\equiv 1 \pmod{2} .\end{cases}$$

and so on.

Another interesting extension would be an $abc$ variant:

$$g^j_{abc}(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ n+m^j & \text{if } n\equiv 1 \pmod{2} \end{cases}$$

for $m^j =$ the next-but-$j$ prime of $n$.

I suppose $g_1$ can be handled with a similar argument (in case it is correct) as what I lined out for $g_0$. For $g_2$ I am not sure anymore, but somehow I suppose $f$ (the original) is something like the simplest of this class which cannot be handled with that kind of argument (otherwise it wouldn't be such a conundrum?).

$\endgroup$
  • 1
    $\begingroup$ Relevant: oeis.org/A061313 $\endgroup$ – Matthew Conroy Aug 8 '16 at 18:27
  • $\begingroup$ wouldn't $g_2$ go to infinity after reaching an odd number over $1$? $\endgroup$ – Jorge Fernández Hidalgo Aug 8 '16 at 18:27
  • 1
    $\begingroup$ Interesting why someone thought to downvote this question: isn't it relevant? Does the OP demmands to to his homework? Isn't it sufficiently worked out and exposed...? $\endgroup$ – DonAntonio Aug 8 '16 at 18:47
  • 1
    $\begingroup$ A reformulation of the Collatz conjecture that you might be interested in is as follows: start with some odd integer $x$. Then, add one to it and take the prime factorization. Change all the 2's in the prime factorization to 3's. Then subtract one, and factor that number. Remove all the factors of two. Repeat. We should get to $1$ eventually. This gives us some connection to factorization, but says little of what happens to anything but the orders of $2$ and $3$. (The reformulation follows from the fact that $0$ and $-1$ are fixed points of the maps $n/2$ and $(3n+1)/2$ respectively) $\endgroup$ – Milo Brandt Aug 8 '16 at 20:12
  • 1
    $\begingroup$ @Franky_GTH It's a subsequence - you get the odd numbers that were preceded by at least two division by two steps. For instance, under the $n/2$ and $3n+1$ iteration, from $7$ the sequence is $$7,\,22,\,11,\,34,\,17,\,52,\,26,\,13,\,40,\,20,\,10,\,5,\,16,\,8,\,4,\,2,\,1$$ whereas the modified sequence is $$7,\,13,\,5,\,1$$ $\endgroup$ – Milo Brandt Aug 8 '16 at 20:38
4
$\begingroup$

The case of $g_0$ is immediate. You can combine two steps in one and

$$g'_0(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ (n+1)/2 & \text{if } n\equiv 1 \pmod{2}\end{cases}$$ so that the function is strictly decreasing for $n>2$, and $g'_0(1)=g'_0(2)=1$.

The same argument holds for $g_1$ and $g_2$.

$\endgroup$
  • $\begingroup$ I see your point. Part of the idea here would be to think in terms of the prime factors accessible. In this way one could try to maintain the argument for the standard case. Hence, instead of showing triviality by the monotony argument, I would be interested in the validity of my argument. $\endgroup$ – Rudi_Birnbaum Aug 8 '16 at 18:56
  • $\begingroup$ @Franky_GTH: is there any relation between the prime factorization of a number and a linear transform of the latter ? $\endgroup$ – Yves Daoust Aug 8 '16 at 19:18
  • 1
    $\begingroup$ Isn't $g_2()$ the Collatz-function itself? $\endgroup$ – Gottfried Helms Jan 1 '18 at 9:19
0
$\begingroup$

$g_0(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases}$

Hi. That the function is decreasing is a demonstration? If so, how can we transfer it to the 3n + 1 problem? Somehow the Collatz algorithm encodes or reorders n, is a permutation from N, and in this distribution, the function can be shown decreasing?

$$ \begin{matrix} ... & ... & ... & ... & ... & ... & ... & ... & ... & ... \\ 128 & 84 & 52 & 136 & 88 & 58 & 74 & 100 & 260 & ... \\ 64 & 80 & 48 & 75 & 49 & 56 & 72 & 99 & 133 & ... \\ 32 & 42 & 26 & 74 & 46 & 30 & 38 & 98 & 132 & ... \\ 16 & 40 & 24 & 70 & 45 & 29 & 37 & 96 & 130 & ... \\ 8 & 21 & 13 & 68 & 44 & 28 & 36 & 51 & 67 & ... \\ 4 & 20 & 12 & 35 & 23 & 15 & 19 & 50 & 66 & ... \\ 2 & 10 & 6 & 34 & 22 & 14 & 18 & 49 & 65 & ... \\ 1 & 5 & 3 & 17 & 11 & 7 & 9 & 25 & 33 & ... \\ \hline\\ k=0 & k=1 & k=2&k=3&k=4&k=5&k=6&k=7&k=8&k=... \end{matrix} $$

k=odd steps. The even numbers go down and the odd numbers go to the left.

$\endgroup$

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.