Another way to look at it that doesn't require a convergence proof is to show that ℕ = S, where S = {1} ∪ {n×2 : n∈S} ∪ {(n-1)÷3 : n∈S ∧ n-1|3}.

Not a mathematician but that is too close to mesenne primes to make a quite fun possible connection. Since messene you have points that 3n cannot hit.

But it's 3n+1, so you're always getting an even number 50% of the time.

And for every number you hit along the way, assuming you make it down to 1, you can stop your iteration if you've previously seen the number

> And for every number you hit along the way, assuming you make it down to 1, you can stop your iteration if you've previously seen the number

You can stop your iteration if you come to a previously encountered value, because the (n+1)th number in the sequence is strictly a function of the nth number. Assuming that you make it down to 1 gives you nothing.

The whole point is to prove that you always make it to 1, or -- equivalently -- to show that you can never reach a previously encountered number without first reaching 1.

But you'll always reach a previously seen number because 3n+1 will never be a prime number.

No. If you could prove that you'll always reach a previously seen number, then you could simply say "Let n be the smallest number for which the Collatz Conjecture is false, we have shown that we'll always reach a number < n for which the Collatz Conjecture is true, hence n does not exist."

I don't follow this either. ((3n+1) / 2) is always greater than n. If all Collatz sequences are periodic (or periodic after a finite prefix), how does that prove that they all achieve a value less than some constant k?

(Or even that they all achieve a value which is less than their own first element?)

(3n+1)/2 is always greater than n, yes, but you'd need to find a loop where you're always alternating 3n+1 and n/2 to reach a rate of increase which could not be overcome. Which I take to mean that if n/2 occurs > 50% of the time, will eventually take the series to a number lower than your starting value and eventually to 1.

Maybe the threshold isn't 50%, but the proof then becomes finding that threshold

EDIT:

I am satisfied that, under the assumption that all Collatz sequences are periodic[1], they must all achieve a value less than their own initial value. (Unless that initial value is 1.)

Because the sequence is periodic[1], the ratio of (3n+1) applications to (n/2) applications must be constant[1]. This implies that the value of a term of the sequence will look like ((3^pn)k / (2^qn)), where p/q is approximately equal to the ratio of (3n+1) applications to (n/2) applications. Since no integer greater than 1 is simultaneously a power of 2 and a power of 3, this must trend toward positive infinity or toward zero as n increases. But for the sequence to increase without bound violates the assumption that it is periodic[2] -- so the terms of the sequence must instead trend toward zero.

[1] I'll use the simplifying assumption that all Collatz sequences are periodic after a prefix of 0 terms. For sequences that are periodic after a prefix of more than 0 terms, just treat them as equivalent to the same sequence with the prefix removed.

[2] A periodic sequence can take on only a finite number of values (equal to the period). But if the sequence increases without bound, it must take on an infinite number of distinct values.

I can see that 3n+1 is never prime. Why does that guarantee that you will always reach a previously seen number?

The idea is that with 2n you always go down to one. But for some values of that happene to be messene prime + 1,they cannot be reached by 3*(whatever) + 1, only from above.

So focusing on the points that this conjecture reaches only that way, can probably give a faster way to find messene primes.

Since we're multiplying by 3 and adding 1 only if n is odd, i.e. for some n = 2k + 1, the result will be even 100% of the time, i.e. 3n + 1 = 3(2k + 1) + 1 = 6k + 4 = 2(3k + 2). Since this result is even, we'll immediately divide by 2 and we've gone from n = 2k + 1 to 3k + 2, a larger number. Of course this number could be even or odd but it's not immediately obvious that we'll ever encounter a number smaller than n.