So playing with the Collatz conjecture, and I feel like this is something where if we can show for any n > 1, there exists a m such that f_m(n) < n , and then we simply prove this by induction, and we’ll be done.
I can show this is true for a list of items mod 3, 9, etc. and there is a clear pattern to demonstrate this by building on this:
n = k (mod 4) has 3n+1 = 3k+1 (mod 4), thus if k=1, 3n+1 | 4, thus Collatz will go 3n+1 / 4 before it could possibly become odd again, and thus we simply show 3n/4+1/4 <= n , which is relatively easy and we are good to go with this one.
Similarly if n is even, we have immediately that n -> n/2 which is less than n.
So we have if n=k (mod 4) k=0,1,2, then n will eventually drop below itself using the Collatz procedure. What about if k=3?
Well, we have
3k+1 = 10 = 2 (mod 4). Now, obviously we will need to divide by 2, and we will get another odd number, because 2 / 2 (mod 4) = 1 (mod 2) (since 3*2, and 1*2 = 2 (mod 4)). This means though, that we have (3n+1)/2 = 1 or 3 (mod 4), and it isn’t hard to see how this becomes exponentially complex. Yet, to me, I feel like if I can show that f_m(n) < n for some m, then we have proven the conjecture. It just would take some chewing of this irritant to get there. It isn’t hard to see that you can expand this to cover n = k (mod 8) and get most n’s covered in this circumstance, but then you miss a few and have to go to mod 16, etc.
The question is, is there an obvious enough pattern to be able to prove that for n = k (mod 2^l) and use that as leverage…
We can wash rinse and repeat somewhat, but the math becomes somewhat complicated (and ugly) as the different pathways diverge. Yet, I think if there is a way to chew up the modular arithmetic, you’d be able to approach this using an inductive method.
Hrm… Times like this makes me wonder how hard it would be to get paid a decent salary doing math research again.