# Biggest factor of 2 of any number N

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

• 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. – fleablood Mar 17 '17 at 16:41
• 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. – ChemiCalChems Mar 17 '17 at 16:42
• 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 – Jean Marie Mar 17 '17 at 18:43
• @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! – ChemiCalChems Mar 17 '17 at 20:07
• 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 – Gottfried Helms Mar 18 '17 at 3:13

## 4 Answers

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.

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

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.

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$

• 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. – ChemiCalChems Mar 17 '17 at 20:06
• 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$ – Gottfried Helms Mar 18 '17 at 6:58

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

• 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. – ChemiCalChems Mar 18 '17 at 6:21
• 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... – Gottfried Helms Mar 18 '17 at 6:46
• 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. – ChemiCalChems Mar 18 '17 at 6:50
• 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? – Gottfried Helms Mar 18 '17 at 7:13
• 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. – ChemiCalChems Mar 18 '17 at 7:31