Biggest factor of 2 of any number N

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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$

Answer 4

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