I'm offering 100,000 CE to anyone who can PROVE or provide a counter example to the Collatz Conjecture.
Take any natural number n. If n is even, divide it by 2 to get n / 2. If n is odd, multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process indefinitely. The conjecture is that no matter what number you start with, you shall always eventually reach 1
http://en.wikipedia.org/wiki/Collatz_conjecture
So can you do it?
I'm not in any way connected to mathematics as a field, but it seems there is some debate as to whether or not 0 is included among the natural numbers, and that leaves the door open to its use as a counter example since 0 is even. Flaw in how natural numbers are defined rather than in the Collatz Conjecture, but I didn't find anything that limited the conjecture to "a-natural-number-as-long-as-we're-defining-natural-numbers-as-not-including-0." At any rate, interesting problem.
[EDIT: And I guess alternatively, if there were a way to prove 0 as an odd number (I have no idea if such a proof might exist as I again am not a mathematician), if you are including 0 as a natural number it would be another example of the conjecture being true since 0 x 3 +1 = 1. Neat!]
If mathematicians suddenly turned an about face on centuries of standardization and declared 0 a natural number then this problem would simply be restated with "positive integer" instead of "natural number". Sorry :) .
Woah... Smart person thread... My brain is about to explode.
How I feel about not being able to answer the question.
(Only video I could find).
Dude I am raging soooooooooooo much!,!,!,!,!,!,,,,,!,!,,,,,,,!!!!!!!!!
I did the number 1245 and it took a zillion calculations to do and I ended up with 0 RAGEEEE
BTW it is impossible to find a counter because of this:
Example:
1--> trivial solution
2-->2/2=1-->(collatz conjectue satisfied)
3-->33+1=10-->10/2-->53+1-->16=2^4-->(collatz conjectue satisfied)
4-->2^2-->(collatz conjectue satisfied)
5-->5*3+1=16=2^4---->(collatz conjectue satisfied)
6-->3(since collatz conjectyre is true for 3 it is true for 6 as well)
7-->22-->11-->34-->17-->52-->26-->13-->40-->20-->10-->5 which is satisifying collatz conjecture -->(collatz conjectue satisfied)
8-->2^3-->(collatz conjectue satisfied)
9-->28-->14-->7 which is satisifying collatz conjecture -->(collatz conjectue satisfied)
10-->we arlready encountered 0 in the above simplifications(SO satisfies Collatz conjecture)
SO every number can be ultimately reduced to the form 2^k using the collatz conjecture function and thus the loop definitely terminates
Can ize have tha 100k ce plox? Since I went to the trouble to calculate the number 1245... :|
My IGN is Xfight
If someone in the planet has enough time to find a counter example then that person deserves that much CE. That's why Crossproduct isn't giving away free CE. Anyways, I don't know a counter example.
Such a hard question!!! I don't have time for this....
Xfight, you've shown that 1 through 10 and 1245 converge, however you have to show the sequence converges for all natural numbers. One way you can prove a problem like this is by induction, assume starting with a number n it converges, and then show that (n+1) converges.
@narfle , some mathematicians barely recognize 0 as a real number, because technically it is just a value we use to signify abscence of quantifyable matter.
some mathematicians barely recognize 0 as a real number, because technically it is just a value we use to signify abscence of quantifyable matter.
Every mathematician in nearly a millennium has recognized 0 as a number, also as a REAL number.
The answer is we don't know if it's possible to prove, or to disprove it, it's an open problem. This problem is simple enough that potentially anyone can solve it, yet no one has.
This problem is simple enough that potentially anyone can solve it, yet no one has.
Anyone can solve it but no one has.
I tried to READ the wiki page.
My brain exploded.
I tried to read this thread.
My brain exploded.
What do you mean by counter example and prove you have the ce( you just look like a troll...)
For the Conjecture to be wrong, n must be equal to (3n+1)/2^k for k is the number of times (3n+1) needs to be divided by 2 to reach n. n must also be a prime number.
By reconstructing the equation, n = 1/(3-2^k). The only natural number this equation could derive is n=2, for all natural values of k. This is however a flaw, because n=2 is not an odd number, thus it could not follow the equation, and can be immediately divided by 2.
To prove why 0 does not work, plot a graph of n = 1/(3-2^k). The graph will never touch n=0 as k lim-> infinite. Anyway 0 is not a natural number.
At least I disprove that the Conjecture will not work for all values.
What do you mean by counter example and prove you have the ce( you just look like a troll...)
Here's your proof: http://cloud.steampowered.com/ugc/577869710575572816/C6F1E5C35EF84D1EF30...
A counter example in this case would be a number n, such that when going through the process you do not reach 1. A way this might happen is if while going through this process you come back to the same number and thus have found a loop. Say n1->n2->n3->n4->n1. That would be a successful counter example. The loop may be really long. Another possible counter example is if starting at a number n, the chain keeps growing, larger and larger and approaches infinity.
@Curious Mewkat
Wanted to point out that if n=(3n+1)/2^k, then solving for n yields n=1/(2^k-3).
Going off of what Curious-Mewkat said, for the given conjecture to be wrong, n must be a number such that:
n=(3n+1)/2^k (in which case we would have a repeating sequence)
and so:
n=1/((2^k)-3)
the only value of k that produces a natural number for n is k=2, which yields n=1(a trivial solution). Therefore, the conjecture must be true.
1. THREAD NECROED!
2. You blew up my Clock Drive.
3. What are yo-
MALFUNCTION!
SYSTEM DRIVE DAMAGED.
IF THIS HAPPENS FIRST TIME...
WAIT FOR SYSTEM RESTART.
IF YOU EXPECTED THIS SITUATION...
SELF-DESTRUCT MATIKCLOCKER AND RESPAWN HIM.
CLOSING MATIKCLOCKER...
I've actually put in a considerable amount of time trying to prove it back in High School. The discussion here isn't even scratching the surface (no offense). The are professional mathematicians who have made a lot more progress. People who are interested in proving it should do some research first*.
The generalized version (over all real numbers) has been proven to be undecideable. The tricky part about the original conjecture is that everything occurs in integer-land. We don't have as many mathematical tools for analyzing the behavior of integer-mapping algorithms.
*For example, all cycles that contain x odd iterations, where x is smaller than some number (forgot specific value) have been proven to not exist. That's not even close to the proof though. To prove it, you have to prove no cycle of any finite length exists AND the values do not increase indefinitely.
I apologize for the necro...I saw the 100k CE reward and I figured I might throw out a response as a gimme :P. I'm not an expert on formal mathematical proofs, but I did notice something that I thought was pretty pertinent: the algorithm will cause your number to decrease and increase until you hit a power of 2, at which point it is halved until it reaches 1. So wouldn't you just need to show that your starting number n after some number p iterations will become a power of 2? Or, put another way ((3n+1)^b)/(2^k)=2^x, where b+k=p (your number of iterations)? In fact, I may try and whip up a python implementation that gets the corresponding powers of 2 for each n in a finite integer set and set if there's a pattern.
It is ok, Giga. This was not a bad necro. :)
Thanks for the reassurance, lol xD. Heck, who wouldn't wanna cash in on this thing(even if it is a hopeless endeavor)!?
A person who doesn't play the game? lol.
now here is a quote from cleverbot.
"You're a [kid-lover]."- Gbot
"Thanks for noticing!"- Cleverbot.
Perhaps a person who doesn't play wouldn't be interested, but perhaps they may become so. Suppose that some person(who doesn't play but lurks on the forms for whatever reason) solves this and is able to claim the CE. If they did a little googling, they'd probably come to understand that 100k CE is A LOT of in-game currency, and may, as a result of their findings, decide to give Spiral knights a try. Of course, it could be that the person remains disinterested even after such a search, which is why I left both possibilities open xD. If it was you that you were referring to specifically, may I ask why you don't play yet decide to remain on the forums?
I don't know how to conjure collapses, but this topic collapsed my drive.
Now I'm respawned. But 100000 crowns is a big deal... 1000 energy for this amount.
Sorry. i meant to edit post, not make a new one. >:(
"why you don't play yet decide to remain on the forums?" because Crazee Pi is here. If i had a youtube account i would be there all the time. This place is the only place i can talk to Pi. Otherwise i wouldn't even be here. He is one of my only friends other than Red-Galaxy.
Gigawattx,
I think you are misinterpreting the problem. The trajectories are not modeled by ((3n+1)^b)/(2^k).
n -> 3n+1 -> (3n+1)/2 -> (3n+1)/4 OR 3(3n+1)/2 + 1)/2 = (9n + 5)/4
Notice that (3n+1)^2 = 9n^2 + 6n + 1, which is not the same as 9n+5
You are correct in saying that proving it goes to a power of 2 would prove it goes to 1. That doesn't help though. Because you end up with this:
((3n+1)/2^(x1))3 + 1)/2^(x2))3 + 1)/2^(x3))3 + 1)/2^(x4))3 + 1)/2^(x5))... = 2^m
Like I said before, seriously do some research before you attempt anything. It will save you from wasting a good portion of your life. The problem is addictive, but very, very hard.
PS: If you do manage to prove it, 100,000 energy is worthless compared to what you would receive from the global mathematics community.
^ That is so true. Just so true It makes me cry.
@deleted-Knight
Sorry, that was my mistake. I didn't mean to the power of, I meant it as a counting number for each iteration the new n is odd(i'm talking about the ^b). I sort of mindlessly did that, since 2^k is the proper behavior for k iterations where n is even. Essentially, the way you wrote out that series is the way I intended it to be. For each odd n, n-->3n+1 and divide it by 2 x(1,2,3...) times until the next odd. Are there more profitable sources to look at other than wikipedia?
@Mechathglxclone
Who is Crazee Pi?
Well, if you accept 0 as a natural number, then the Collatz Conjecture doesn't work because 0 divided by 2 is still 0. Can haz 100k ce, plox? ;)