An Attempt at the Collatz Conjecture

When I was searching for a problem to solve on the problem-solving wiki, a problem that "may resist all your attempts to solve" caught my eye. I was curious about how "resisting" the problem is, so here is my attempt at finding a solution for it.

Question: Suppose n stands for some positive whole number. Define a function f(n) that associates n with another positive whole number, as follows:

• If n is even, then f(n) is n/2
• If n is odd, then f(n) is 3n+1

Since f(n) takes any positive whole number as input, and produces a positive whole number as output, it makes sense to talk about f(f(n)) or f(f(f(n))) --- composing f with itself several times. Let's define F(m,n) as f(f(...f(n)...), where f is composed with itself m times. Is the following statement true or false? For each [positive] natural number n there exists a [positive] natural number m such that F(m,n) = 1.

Attempt:
I first start by making sure that I understand the problem. Given the definitions of f(n) and F(m, n), I either need to prove that the statement above is true, or find a counterexample. So first I list some examples to try to find some patterns:

n    m    f(n) recursion results
1    3    4,2,1
2    1    1
3    7    10,5,16,8,4,2,1
4    2    2,1
5    5    16,8,4,2,1
6    8    3,10,5,16,8,4,2,1
7   16   22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
8    3    4,2,1
9   19   28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
10  6    5,16,8,4,2,1
11  14  34,17,52,26,13,40,20,10,5,16,8,4,2,1

So far, no counterexamples are found. I begin to suspect that the statement is true, although I cannot be sure. More examples would strengthen my thinking that the statement is true. But finding m for a large number n can become tedious. The natural thing to do is to write a program that helps me with this task:

def f(n):
    if n % 2 == 0:
        return n / 2
    else:
        return 3 * n + 1
 
   
def F(n):
    m = 1
    n = f(n)
    while n != 1:
        n = f(n)
        m += 1
    return m

The program successfully executes. There does not seem to be any obvious pattern associated with n and m, although for larger numbers n, sometimes m repeats itself for consecutive numbers n. For example:

n           m
940      129
941      129
942      129
943      36
944      36
945      36
946      36
947      36
948      36
949      36

F(m, n) does have a pattern when n is a power of 2 though. In these cases, m is the exponent of that power. For example, when n = 2^1, m = 1;  when n = 2^2 = 4, m = 2;  when n = 2^3 = 8, m = 3, etc. This is due to the fact that a postive power of 2 is always even, so f(n) = n/2 is always executed. After executing m times, f(n) = 1. Since powers of 2 work nicely, what if I write every postive natural number n in terms of powers of 2 plus any remainder? Perhaps m has an indirect relationship with all these powers of 2s.

n
1 = 1
2 = 2^1
3 = 2^1 + 1
4 = 2^2
5 = 2^2 + 1
6 = 2^2 + 2^1
7 = 2^2 + 2^1 + 1
8 = 2^3
9 = 2^3 + 1
10 = 2^3 + 2^1
11 = 2^3 + 2^1 + 1  

After some trial-and-error scratch work on trying to find a pattern between m and n written as powers of 2 and the remainder, I derived no useful results.

Now I list some facts about f(n), F(m, n) and the examples above to see if anything would help to prove the statement:

 n/2 always decreases, while 3n + 1 always increases for a positive natural number n.

 The only way to get down to  1 is if at some point of the recursion, F(k, n), where 1 <= k < m, is a positive power of 2. So we could try to prove that every natural number n, after performing a finite number of f(n), becomes a power of 2.

3n + 1 = 2n + (n + 1). 2n is always even. Since n is odd, n + 1 is even. Then an even number plus an even number is always even. So 3n + 1 is always even. If n is currently odd, then after executing 3n + 1, n becomes even, in which case the new n will be reduced by half using n/2. Thus we know that F(m, n) is not infinitely increasing. Instead, the function F generally goes up and down.

None of these facts directly help with the actual proof. However, the second point leads me to a new direction. I know that every number have a prime factorization. We can separate the prime factorizations into powers of 2 and all others. Then every positive natural number n can be written as n = 2^k * t, where k >= 0, and t is odd (since t contains no more powers of 2). Then it looks like this proof could take the form of Complete Induction, where the two parts 2^k and t may become useful in the induction step.

Let P(n) be the following predicate:
P(n): there exists a positive natural number m such that F(m, n) = 1.

Base Case: n = 1. Then n is odd, so f(n) is executed as follows: 3(1) + 1 = 4, 4/2 = 2, 2/2 = 1. Thus m exists. So P(1) holds.

Induction step:
Assume i is a positive natural number such that 1 <= i < n, and P(i) is true; i.e. there exists a positive natural number r such that F(r, i) = 1. Then there are two cases:

Case1: n is even. Then n = 2^k * t, where k >= 1. Then t = n/(2^k). Since n is at least 2 and 2^k is at least 2, 1 <= t < n, so P(t) is true. i.e. there exists a positive natural number r such that F(r, t) = 1. Also, t = F(k, n) because 2^k is a power of 2, so applying f to the power of 2 k times decreases the number by half until the number no longer contains any more powers of 2. So F(r, t) = F(r, F(k, n)) = 1. This means f is applied to F(k, n) r times. But F(k, n) means f is applied to n k times. So F(r, F(k, n)) = F(r + k, n) = 1. So there exists a positive natural number m = r + k such that F(m, n) = 1.

Case2: n is odd. Then f(n) gives 3n + 1, which is an even number according to my third point mentioned above. Call this number y. Since y is even, by case 1, there exists a positive natural number s such that F(s, y) = 1. But y = f(n). So  F(s, y) = F(s, f(n)) = F(s + 1, n) = 1. So there exists a positive natural number m = s + 1 such that F(m, n) = 1.

Then in both cases, there exists a positive natural number m such that F(m, n) = 1.
Since n is arbitrary, this means for all positive natural numbers n and, if P(i) is true, where 1 <= i < n, then P(n) is true.
Then for all positive natural numbers n, P(n) holds.

It looks like the induction works. But I have a feeling that there is something faulty that I did not catch about an assumption that I made. I will come back to this problem on another day to see if my brain can make some new progress.