0
$\begingroup$

I'm trying to get an insight of the Collatz Conjecture (3n+1 conjecture), and have been researching about iterated functions and thought the conjecture could possibly be solved if I was able to successfully iterate a function that gives me a new element in the progression to infinity and prove that the result tended to 1. I still don't know if this would work since the last thing any number does is fall into a loop of 4, 2, 1 and so on, but that's beyond the question.

My idea is to have a function that does the following:

  • $ f(x) = 3x+1 $
  • $ g(x) = $ biggest factor of 2 of $ x $

The problem is, how do I find this biggest factor of two? My idea is to do something like the following

$ h(x) = \frac{f(x)}{g(f(x))} $

This, I think would return the next odd number in the progression, so I could then run $ h(x) $ again on the result, thus I would want to iterate $ h(x) $ to infinity.


Example:

Let $ n = 1 $, $f(1) = 4$, thus, $ g(f(1))= 4 $, and so, $ h(1) = 1 $.

However, let's say we start with another number.

Let $ n = 4 $, $f(4) = 13$, this, $g(f(4)) = 1$, and so, $ h(4) = 13 $. I know it's a stupid example, because 4 is already a power of two, so I would arrive at 1 just by dividing by 2 $log_2(4)$ times, but note that $g(13) = 1$ because 1 is the biggest factor of 2 that divides 13.


What am I looking for? How could I express $g(x)$ ?

$\endgroup$
  • $\begingroup$ Presumably you know how to factor x? So express x as binary. Mulltiply by "11" (which is three) and add one and count the zeros at the end. If x = 25, = 11001 so 11.11001+1 = 110010 + 11001 + 1 = 1,(1+1),(0+1),(0+0),(1+0),(0+1+1) = 1,2,1,0,1,2 = 2,0,1,0,2,0 = 1,0,0,1,1,00 = 1001100 so the highest power of two is 100 = 4. And 3*25+1 = 76 = 4*19. I don't know if that will make anything easier though. $\endgroup$ – fleablood Mar 17 '17 at 16:41
  • $\begingroup$ Working towards a proof using iterative functions and binary notation doesn't seem ideal. I know that is a possible solution, but not beautiful at all, and not really what I'm looking for. Thank you for the help anyway. $\endgroup$ – ChemiCalChems Mar 17 '17 at 16:42
  • $\begingroup$ A friendly advice: don't loose to much time on this conjecture: even very great mathematicians like Erdös consider it out of reach... There are many more valuable questions in mathematics $\endgroup$ – Jean Marie Mar 17 '17 at 18:43
  • $\begingroup$ @JeanMarie I know, but the sheer simplicity of the statement just astonishes me. I'm not even in uni, I'm just a curious math and physics enthusiast. Thanks for the advice, anyway! $\endgroup$ – ChemiCalChems Mar 17 '17 at 20:07
  • $\begingroup$ Perhaps you find this a nice intro - I've one time started the same way which you seem to want to go now: go.helms-net.de/math/collatz/aboutloop/collloopintro_main.htm or in some more compact form go.helms-net.de/math/collatz/Collatz061102.pdf $\endgroup$ – Gottfried Helms Mar 18 '17 at 3:13
3
$\begingroup$

The biggest factor of $2$ in $x$ is given by $\frac{1}{\lvert x\rvert_2}$ where $\lvert x\rvert_2$ is the 2-adic norm of $x$.

If $f$ instead maps $f(x)=(3x+1)\lvert 3x+1\rvert_2$ then you have your function. This function maps one odd number directly to the next odd number, and this is indeed a crucial simplification which will, in my opinion, ultimately be a cornerstone of the eventual proof.

However the relationship between sequential values of $\lvert x\rvert_2$ is the essence of the difficulty of the Collatz Conjecture, and you have done nothing to resolve that unfortunately.

$\endgroup$
  • $\begingroup$ P.S. if you want a further hint I suspect study of Pascal's n-simplex will be a fruitful direction. $\endgroup$ – samerivertwice Mar 17 '17 at 18:37
  • $\begingroup$ Will do, thank you very much! $\endgroup$ – ChemiCalChems Mar 17 '17 at 18:45
4
$\begingroup$

As others explained, the 2-adic valuation is what you seem to be looking for.


In case you want to embark on a Collatz quest in 2-adic language I want to give you the following warning. Obviously not a counterexample to Collatz, just something you possibly should be aware of :-)

Consider base-2 patterns (extending to the left) like the following $$ x=\ldots11001100110011001101_2 $$ (with the period $1100$ repeating). We then get (with grade school arithmetic) $$ 3x+1=\ldots1001100110011001101000_2, $$ so dividing $3x+1$ by $2$ three times gives back the pattern we started with! Therefore Collatz fails for this (infinite) string of bits.

Writing the above in other words $$ \frac{3x+1}8=x $$ implying that $x=1/5$, albeit written as a 2-adic integer.

This is hardly a surprise:

  • $1/5$ is odd, so Collatz tells us to replace it with $3\cdot(1/5)+1=8/5$
  • $8/5$, an even 2-adic, can obviously be divided by two thrice before we finally get an odd 2-adic $1/5$.

My point (if any) is that any putative Collatz period, no matter how long, has a solution in the 2-adics (most likely only as an infinitely repeating periodic 2-adic integer). So some special property of finite bit strings needs to be discovered to prove Collatz.

$\endgroup$
0
$\begingroup$

Okay this is complicated but go through $n = 1.....$ to determine the first of these to be true.

$x \equiv 0 \mod 2; x \not \equiv 1 \mod 2; n = 0$ if so $g(3x+1) = 1$

$x \equiv 3 \mod 4; x \not \equiv 1 \mod 4; n = 1$ if so $g(3x+1) = 2$

$x \equiv 1 \mod 8; x \not \equiv 5 \mod 8; n = 2$ if so $g(3x+1) = 4$

$x \equiv 13 \mod 16; x \not \equiv 5 \mod 16; n = 3$ if so $g(3x+1) = 8$

$x \equiv 13 \mod 32; x \not \equiv 1 + 4 + 16\mod 32; n = 4$ if so $g(3x+1) = 16$

.....

$x \not \equiv 1 + 4 + .... + 2^{2\lfloor n/2\rfloor}; $ if so $g(3x+1) = 2^{n}$.

Example $n = 21$.

$x \equiv 1 \mod 2$ so $g(3x + 1) > 1$

$n \equiv 1 \mod 4$ so $g(3x + 1) > 2$

$n \equiv 5 \mod 8$ so $g(3x + 1) > 4$

$x \equiv 5 \mod 16$ so $g(3x+1) > 8$

$x \equiv 1+4+16\mod 32$ so $g(3x+1) > 16$.

$x \equiv 1+4 +16\mod 64$ so $g(3x + 1) > 32$.

$x \not \equiv 1+ 4 + 16 + 64=85 \mod 128$ so $g(3x+1) = 64$ and $3x+1 \equiv 64 \mod 128$.

Another example.

$x = 93$ $1 + 4 + 16 + 64 < x < 1 + 4 + 16 + 64$. So "key" values are $ 1,1, 5,5, 21,21, 85$

$x \equiv 1 \mod 2$ check

$ \equiv 1 \mod 4$ check

$\equiv 5 \mod 8$ check

$\equiv 13 \mod 16$ not $5$ so $g(3*93 + 1) = 8$

$\endgroup$
  • $\begingroup$ I need a function that I can iterate though. This seems like a good algorithm, but I'm struggling to find a function that can do this. $\endgroup$ – ChemiCalChems Mar 17 '17 at 20:06
  • $\begingroup$ I'll make your list complete. You can write the following. Decompose your odd number $a$ as $ a=2^{A+1} k + r_A $ with $k$ odd then $b=(3a+1)/2^A$ and $b = 6k + 1$ and $r = {2^A-1\over 3 }$ for even $A$ or $b=6k+5$ and $r = {5 \cdot 2^A-1\over 3 }$ for odd $A$ $\endgroup$ – Gottfried Helms Mar 18 '17 at 6:58
0
$\begingroup$

No answer, rather a comment and request for clarification

What you're doing is actually the "Syracuse"-definition of the Collatz (see wikipedia).

I don't know really know what you mean "how to find a function which returns the largest power-of-2-factor of x", perhaps I'm only mideducated by the programming-languages. In Pari/GP you ask only

h(x)= x=3*x+1; A=valuation(x,2); return(x/2^A)

Of course you need to check whether x is odd before (this is also the implementation how I calculate in the Collatz-study).

The valuation()- function itself can be implemented by iteratively checking, whether x is divisible by 2 and so on, so I'm possibly missing the point in your question ...


Hmm, perhaps this is helpful , which I looked sometimes at myself...

Once I've decided to use the odd-only-version/Syracuse-notation of the Collatz-iteration the corrolary is implied, that a proof of the Collatz-conjecture has as well been done, when I have a proof for the odd numbers only.

One can proceed: if the odd-numbers-only version is a useful/sufficient one, then I can as well use the subset of numbers $b=3a+1$ (where $a=2k+1$ is odd) and can base my lemmas and theorems on analysis of numbers of that form $ b = 3(2k+1) + 1 = 6k+4$ and an adapted transformation. Of course the transformation is now even simpler: $$h(b) = \{b\} \cdot 3 + 1$$ where the curly-braces mean the extraction of the powers of 2 of an even number (your function $g(x)$ if I got that right). So if $b$ in bitstring-representation is $b="100110100"_2$ then $\text{bitstring} \{b\}="1001101"_2 $.
The collatz-conjecture in this transformation is now:

Choose any natural number of the form $b_0=6j+4, j \in \mathbb N_0$ . Then iterated transformation by $b_{k+1}=h(b_k)$ enters the cycle $b_{k+1}=h(b_k) = b_k = 4$ with some finite $k \ge 0$

But well - again this is no mathematical formula in the sense of finite compositions of elementary continuous functions in some formula...

$\endgroup$
  • $\begingroup$ The thing is I want a function I can iterate and that doesn't rely on me checking if the number can be divisible or not. I just want the function to give me the result. I'm currently looking for patterns in the biggest power of 2 that can divide a number, and I've found something, but I have no clue as to how I could express it in a functional. $\endgroup$ – ChemiCalChems Mar 18 '17 at 6:21
  • $\begingroup$ Hmm, after software-solutions are there and it is easy to use the binary representation of a number $n$ to cut the rightmost zero-bits you are asking for a "mathematical"-function? I think, there's no finite combination of for example $\exp()$, $1/x$ , $x^2$ etc... $\endgroup$ – Gottfried Helms Mar 18 '17 at 6:46
  • $\begingroup$ Well, I have my computer checking all the natural numbers, it's over the whole human population already. I know this is true for a fact, I need to prove it though, that's all. I can't prove it number by number, because there are infinitely many. $\endgroup$ – ChemiCalChems Mar 18 '17 at 6:50
  • $\begingroup$ Hmm, it seems I can be of no more help here. But just for couriosity: why would it be not sufficient for you to have some formula: if (an odd) a is $a = 2^{A+1}\cdot k + r_A$ then $b = (3a+1)/2^A $ and $b = 6k \pm 1$ and to use this in some (attempt of) proof? There's a lot of general theorems using primefactorization and they consist also only of thought primefactor-decomposition (without being able to do that for each number) and still are general theorems? $\endgroup$ – Gottfried Helms Mar 18 '17 at 7:13
  • $\begingroup$ My wish is to be able to prove that applying the jump-to-next odd number infinitely many times tends to 1. If this is true, the conjecture is true. If this isn't true for all x in the naturals, then the conjecture is false. To apply this jump-to-next odd number infinitely many times, I have to know what power of 2 divides every number in the naturals. As they are infinitely many, I have to generalize a solution for this problem. Only then can I prove this conjecture. $\endgroup$ – ChemiCalChems Mar 18 '17 at 7:31

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.