Collatz conjecture

There's no reason why the Collatz sequence can't blow up to infinity. Consider the similar recurrence C:N->N given by:

C(n)=n/2 if n is even
C(n)=3n+1 if n is odd and 3n+1 is not a power of two
C(n)=3n+3 if n is odd and 3n+1 is a power of two

For any n, this sequence never terminates unless n is a power of two (proof: if C^m(n)=1 for some finite m, where C^m denotes m-fold composition, then C^(m-1)(n)=2, C^(m-2)(n)=4, ... ).

people need to read a fucking book before claiming a decades old unsolved problem with prize money attached to it is going to be solved in the length of a Veeky Forums post

Another conjecture: if you have an even number (x -1) % 3 == 0 and then do 3x+1 instead of /2 the conjecture will always blow up and there will be no loops

Sry it should be (x-1)%3!=0

>For any n, this sequence never terminates unless n is a power of two
Never terminating is different from exploding to infinity. Even your sequence will result in a loop, so your proof must be wrong. Starting with n=5, the sequence will be:
5, 18, 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, ...

you guys are really stupid

Doesn't that disprove the conjecture?.I mean, you can see 5 doesn't end in 1 since it gets back to 5, and there's a finite amount of steps for it to reach 5 again without ever reaching 1?

If n is even, n/2
If n is odd, an+1

Will n always reach 1 if a is odd?
----------------------------------------------------------------------------------------------
If n is even, n/2
If n is odd, an+b

Will n always reach 1 if a is odd and b is odd?
----------------------------------------------------------------------------------------------
If n is even, n/c
If n is odd, an+b

Will n always reach 1 if a is odd and b is odd and c is even?
----------------------------------------------------------------------------------------------
If n is even, n/c
If n is odd, an+b

Will n always reach and odd number if a is odd and b is odd and c is even?
----------------------------------------------------------------------------------------------
If n is even, (n/c)^d
If n is odd, ((an)^d)+(b)^d

Will n always reach and odd number if a is odd and b is odd and c is even and d is odd?

wat

>Will n always reach 1 if a is odd?
No, consider the case of a = 1

It's a sketch of what I would look at if I was to try and take a crack at "proving" the collatz conjecture. Just looking at what happens when you change the scope of the variables based on their properties, from 1 to all odd numbers, from 2 to all even numbers.

There are some typos and I would need to "reformat" some of the questions as they get more general but you should get the idea of what I am doing. It's a pretty basic technique.

Right, but the idea is to look at what happens when a is odd, rather than just when a is equal to just 3. I mean, why 3? What if it is any odd number? Same for the other placeholders in the general form of the function, including the exponents.

That loop is only possible because of the additional part that user added. It's not apart of the original conjecture

>solved in the length of a Veeky Forums post
challenge accepted
Lets to this Veeky Forums broskies.

These are the functions I would look at.

[math]
f(n)=
\begin{cases}
3n+1& \text{if } n \text{ is odd}\\
n/2 & \text{if } n \text{ is even}
\end{cases}[/math]

[math]
f(n)=
\begin{cases}
an+1& \text{if } n, a \text{ are odd}\\
n/2 & \text{if } n \text{ is even}
\end{cases}[/math]

[math]
f(n)=
\begin{cases}
an+b& \text{if } n, a, b \text{ are odd}\\
n/2 & \text{if } n \text{ is even}
\end{cases}[/math]

[math]
f(n)=
\begin{cases}
an+b& \text{if } n, a, b \text{ are odd}\\
n/c & \text{if } n, c \text{ are even}
\end{cases}[/math]

[math]
f(n)=
\begin{cases}
(an)^d+b^d& \text{if } n, a, b, d \text{ are odd}\\
(n/c)^d & \text{if } n, c \text{ are even}
\end{cases}[/math]

Am I retarded or doesn't 1 map to 4, not 2? (Why does it loop to 2 on the cover?)

>k will always result in a smaller positive integer
yes
but 3n+1 always results in a larger integer

You can optimize the problem by making it [math]\frac{3n+1}{2}[/math] because you know that 3n+1 is always even when n is odd. That's what most implementations do.

Makes sense, thanks brah.

>Am I missing something?
Yes.
There are lots of other systems that have loops, so there's no trivial reason to think that 3n+1 has no loops.

Example:
[math]f(n)= \begin{cases} 3n+1& \text{if } n \text{ is odd}\\ n/2 & \text{if } n \text{ is even} \end{cases}[/math]

Starting with 13 leads to a loop that never reaches 1:
13
66
33
166
83
416
208
104
52
26
13

Woops.
That's supposed to be 5n+1, not 3n+1.

>prize money
Yeah a whopping $2000, maybe, if the guys actually pay up. It's not even an official prize, just a couple of professors betting that no one can solve it.

You still can show everybody your proof like it was a foot long penis.

not necessarily, you could have multiple even numbers in a row, you can't optimize the problem like that.
Here's an example
27(odd), 82(even), 41(odd), 124(even), 62(even), 31(odd)
However you can't have multiple odd numbers in a row, that's why it always tends towards the patterns

Fun fact: If you start with a prime, you end up with a prime by the time you're done dividing by 2 (however many times that is).

Fun fact #2: When applied to primes, the formula always gets to 1 in the end.

Fun fact #3: The question can therefore be restated as "Is there any non-prime you can apply the formula to, wherein it eventually returns the same non-prime?"

Fun fact #4: Such a non-prime would also need to be odd, otherwise you'd just divide by 2 and start with an odd number anyway (which might be prime!)

Yet it's still a fun fact in the end, such an odd non-prime would neccisarily contain a finite number of odd, non-1 primes composing it. If each of these eventually reduce to 1 independently, yeah, plug in your Ns. You'll get 1 in the end.

Didn't think to look at primes, was only thinking about even/odd. Thanks for sharing.

What?

An odd times an odd is always an odd. For a number to be even, it must have a factor of two. Multiplying two numbers with no factors of two will never yield a number with a factor of two.

Therefore, odd times odd is always odd.
Therefore, odd times odd plus one is always even.
Therefore, you will always divide by two after doing 3n+1.
Therefore, you can optimize the 3n+1 to (3n+1)/2.
Therefore, GTFO my Veeky Forums.

I think the primes are a distraction, honestly, but who knows. They might have something to do with the answer.

I think the solution is something like this, but I'm too lazy to finish it...

Assumptions:
A) All numbers 4^k - 1 are divisibly by 3... definitely true but too lazy to find a proof

1) Let S be the set of numbers that reduce (eventually) to 1.
2) Trivially, 1 is in S by definition.
3) For any number n that is in S, every number (n)(2^m) is in S, for all m. (because they all reduce to n by dividing by 2 m times)
4) All numbers (4^k - 1) / 3 are in S. (because doing the step 3n+1 gives you 4^k, which must be in S from step 3)
5) All numbers (2^p)((4^k - 1) / 3) are in the set for all p and all k. (because they all reduce to ((4^k - 1) / 3) by dividing by 2 p times)

After that the proof kind of becomes recursive and a big pain in the ass.

The gist of it is that steps 2 and 3 give you all the numbers like this:
1, 2, 4, 8, 16, 32, 64, ...

Then step 4 gives you all the numbers like this:
5, 21, 85, 341, 1365, ...

But then applying step 2 again gives you all of those numbers times 2^m:
5, 10, 20, 40, 80, 160, ...
21, 42, 84, 168, 336, 672, ...
85, 170, 340, 680, 1360, ...

Maybe a better way to say it is like this...
Let S1 be every power of two. Those are all in S.
Let S2 be every *other* element of S1, minus 1, divided by 3. These are all in S because applying 3n+1 yields an element of S1.
Let S3 be every element of S2 multiplied by every power of two. These are all in S because you just divide by 2 until you get an element of S2.
Let S4 be every *other* element of S3, minus 1, divided by 3. These are all in S because applying 3n+1 yields an element of S3.
Let S5 be every element of S4 multiplied by every power of two. These are all in S because you just divide by 2 until you get an element of S4.

... and so on and so on, forever, which eventually puts all positive integers in S. This is left as an exercise for the reader.

Nah that not a good try. Pro tip there is a way to get rid of the recursion

I think the immediate generalization would be something like:
[eqn]f(n)= \begin{cases} an+b& \text{if } n \equiv -b \mod c\\ n/c & \text{if } n \equiv 0 \mod c \end{cases}\\ (a \not\equiv 0 \mod c)[/eqn]

e.g.
[eqn]f(n)= \begin{cases} 4n+1& \text{if } n \equiv 2 \mod 3\\ 4n+2& \text{if } n \equiv 1 \mod 3\\ n/3 & \text{if } n \equiv 0 \mod 3 \end{cases}[/eqn]

Step away from generalisations, it will make the problem much harder

This.

There are specific choices of parameters for which f(n) can simulate a universal Turing machine, with n simulating input and convergence to 1 simulating halting. In this case the corresponding conjecture is provably unprovable since it amounts to solving the halting problem.

This finding (along with the details) is due to Conway, I think.