Collatz conjecture

>Am I missing something?
You didn't make a claim.

If you're implying that because of the succession you'd necessarily end up with 1, you're mistaken. Time 3 followed by times 0.5 gives you an average that's still a factor of 1.5, so it's not evident that you eventually fall far

>If odd : a*n+1 where a equals any positive integer
Sorry I mean to say "where a equals any positive odd integer"

>>8773726
>Take any positive integer n.
0.5 isn't a whole number

>>8773734
What he meant:

Start with n, n odd.=>
n, 3n+1, (3n+1)/2, ...

But n < 1.5n+0.5, and not clear wheter 1.5n+0.5 is odd or even => not clear if the sequence always will decrease.

>>8773723

>k will always result in a smaller positive integer.
>The smallest natural number is 1.

It's pretty hard to find a flaw in this reasoning, but after thinking it over for a little bit, the only thing that this "proves" is that the sequence cannot blow up to infinity. It is still possible that there is a loop (similar to 4=>2=>1=>4=>2=>1) somewhere in the integers that has not been found yet.

>if odd : 3n+1
>if odd : 3n+1 ( odd * odd ) + odd = even;
>if odd : replace with even;

I think what you're missing is that the even number you replace it with will be larger than the original odd number. So even if the even numbers constantly decrease, this increase could
balance that out.

>>8773766
if you use
if even, n=n/2
if odd, n=n+1

you end up with the pattern 2->1 which seems natural since thats what both functions do.
5 -> 6 -> 3 -> 4 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1
10 -> 5 -> 6 -> 3 -> 4 -> 2 -> 1 -> 2 ->1
11 -> 12 -> 6 -> 3 -> 4 -> 2 -> 1 -> 2 -> 1
23 -> 24 -> 12 -> 6 -> 3 -> 4 -> 2 -> 1 -> 2 -> 1

I mean surely you will end with a loop but no matter what number you put in you arrive to that loop so you eventually reach 1

>>8773777
>I mean surely you will end with a loop but no matter what number you put in you arrive to that loop so you eventually reach 1
That's what we are trying to prove. It's not enough to just assert it. I'm not sure if there are other loops in the integers, but I'm fairly positive that it cannot blow up to infinity. That would mean there would need to be infinitely many numbers outside of the "tree" that leads down to 1, which I just can't wrap my head around.

>>8773766

>I think what you're missing is that the even number you replace it with will be larger than the original odd number. So even if the even numbers constantly decrease, this increase could
balance that out.
since even and odds number are alternative, it can't possibly increase enough to balance out a division since we're only using natural numbers
>It's pretty hard to find a flaw in this reasoning, but after thinking it over for a little bit, the only thing that this "proves" is that the sequence cannot blow up to infinity. It is still possible that there is a loop (similar to 4=>2=>1=>4=>2=>1) somewhere in the integers that has not been found yet.
I guess I just need to elaborate my proof

>>8773723
There are two things needed to prove the conjecture.

1. Prove that the operations result in strictly decreasing numbers. This isn't too hard except that it requires that you prove the next part true.

2. Prove that there are no closed loops that don't involve 2 and 1. This is a bit harder. I've tried to take a crack at it with friends late at night, but I was never serious about it.

>>8773766
>>8773787

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

File: 41FpZ7ULcoL._SX348_BO1,204,203,200_.jpg (29KB, 350x499px) Image search: [Google]

29KB, 350x499px

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 4chan 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

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

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

>>8774323
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?

>>8775543
wat

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

>>8775550

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.

>>8775564

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.

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

File: Challenge-Accepted-Meme-07.jpg (43KB, 600x600px) Image search: [Google]

43KB, 600x600px

>>8774167
>solved in the length of a 4chan post
challenge accepted
Lets to this 4chan broskies.

>>8775571
>>8775565
>>8775564
>>8775550

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]

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

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

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

>>8775914
Makes sense, thanks brah.

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

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

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

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

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

>>8776086

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

>>8776050
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 /sci/.

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

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

>>8775597
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]

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

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