0710: "Collatz Conjecture"
Moderators: Moderators General, Prelates, Magistrates

 Posts: 548
 Joined: Tue Jan 12, 2010 1:04 am UTC
 Contact:
0710: "Collatz Conjecture"
Title text: "The Strong Collatz Conjecture states this hold for any set of obsessivelyhandapplied rules.
Funny. To save you trouble of actually typing it into the search bar (oh no!) you can read about the conjecture here. It says that, under the rule of dividing by two if n is even, and tripling and adding one if n is odd, you always eventually end up at one. I can't find anything on a "Strong Collatz Conjecture". I wonder if it also holds true, however, if you have the Microsoft captives down in the basement obsessively handapply it for you...
Last edited by squareroot on Fri Mar 05, 2010 5:18 am UTC, edited 3 times in total.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me  __ 
Good fucking job Will Yu, you found me  __ 
Re: Collatz Conjecture
Not a bad comic. Quite funny actually.
 Magic Molly
 Posts: 94
 Joined: Sat Sep 26, 2009 10:42 pm UTC
Re: Collatz Conjecture
I was told this by my maths teacher a few months ago, and then programmed a little bit of code to test it for every number it could, and note any that didn't work.
Spoiler:
Re: Collatz Conjecture
you need to have discussion after the title. edit it.
3x+1 conjecture FTW!
I also obsesively hand applied this. no one ever called me
3x+1 conjecture FTW!
I also obsesively hand applied this. no one ever called me
Re: Collatz Conjecture
I actually drew a similar looking chart when I first came across the formula in Gödel, Escher, Bach. Although, mine was more of a table than a directed graph.
Code: Select all
from __future__ import skynet

 Posts: 199
 Joined: Sat May 24, 2008 4:17 am UTC
Re: Collatz Conjecture
(Looks at timestamp)...is my computer's clock slow?
This would have been better if the numbers had been purely 1 to some N and incident numbers, although it might not have been as neat looking.
This would have been better if the numbers had been purely 1 to some N and incident numbers, although it might not have been as neat looking.
Re: Collatz Conjecture
I was about to click "submit" when I decided to check if someone beat me to it I've never started a comic discussion
also, I see that I was also beaten to mention GEB. I'm reading the book so this was pretty cool.
This reminds me of several hours wasted shutting myself from society...making up languages/codes, doing math, logic puzzles, etc....good times.
also, I see that I was also beaten to mention GEB. I'm reading the book so this was pretty cool.
This reminds me of several hours wasted shutting myself from society...making up languages/codes, doing math, logic puzzles, etc....good times.
Magus wrote:If history is to change, let it change. If the world is to be destroyed, so be it. If my fate is to die, I must simply laugh.
Just as you touch the energy of every life form you meet, so, too, will will their energy strengthen you.
Re: Collatz Conjecture
I am not enough of a geek to have heard this one before
but I AM enough of a geek to find it pretty cool
sigh, the lonely, uncool middle again
but I AM enough of a geek to find it pretty cool
sigh, the lonely, uncool middle again
Last edited by syko_lozz on Fri Mar 05, 2010 5:13 am UTC, edited 1 time in total.
Debate politics with a fern. If you lose, refuse to water it.
Re: Collatz Conjecture
Well, that's a new thing I learned the existence of today. Nice.

 Posts: 548
 Joined: Tue Jan 12, 2010 1:04 am UTC
 Contact:
Re: "Collatz Conjecture" Discussion
Fixed the title. Actually, I just realized it 8:58, so then I refreshed my internet time, got the "template" ready, and kept obsessively refreshing the page until it changed. "Sucess" and "Obsess" both follow the *s*ss pattern. Coincidence? I think not. (Btw, if that's wrong, I don't know regexp very well..)
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me  __ 
Good fucking job Will Yu, you found me  __ 
Re: Collatz Conjecture
SocialSceneRepairman wrote:(Looks at timestamp)...is my computer's clock slow?
This would have been better if the numbers had been purely 1 to some N and incident numbers, although it might not have been as neat looking.
actually, the forum time is ahead by about 34 minutes. found that out on monday
Re: "Collatz Conjecture" Discussion
The comic is linked to 709, not 710
I actually want to try this out
I actually want to try this out
Re: "Collatz Conjecture" Discussion
squareroot wrote:"Sucess" and "Obsess" both follow the *s*ss pattern. Coincidence? I think not. (Btw, if that's wrong, I don't know regexp very well..)
The regular expression would actually be more like /.+s.+ss/, but that's not why it's wrong. It's wrong because "success" does not have an s in the middle.
Re: the comic  nice twist at the end, but it didn't manage to make me laugh. I came close, though.
Re: "Collatz Conjecture" Discussion
How long before someone critics it on its humour?.
This theory would be of interest to solipsists, and they wouldn't care if noone rang* them.
*It just occurred to me that Americans say "call", we say "ring". Ours isn't confusing, "Ring your sister will you" means use a phone.
"Call your sister will you", could mean phone, or step outside and yell.
This theory would be of interest to solipsists, and they wouldn't care if noone rang* them.
*It just occurred to me that Americans say "call", we say "ring". Ours isn't confusing, "Ring your sister will you" means use a phone.
"Call your sister will you", could mean phone, or step outside and yell.
Abuse of words has been the great instrument of sophistry and chicanery, of party, faction, and division of society.
John Adams
John Adams
Re: "Collatz Conjecture" Discussion
So who has made a program that adds numbers to a similar looking graph already?

 Posts: 1140
 Joined: Wed Aug 27, 2008 4:29 am UTC
 Location: At the center of the observable universe.
Re: "Collatz Conjecture" Discussion
So, I'm guessing Randall made the graph using the reverse method (start with a number m, in this case 1, check if it is of the form 3n+1, if yes: 2 connecting numbers (n and 2m), repeat). Not to nitpick, but that is not exactly the same idea as the conjecture, which would have you start at the endpoints. (Sure, they should be the same in the end, but, well, its the principle of it.)
Good comic!
Good comic!
Look, you know it's serious when a bunch of people in full armor and gear come charging in to fight a pond of chickens  Steax
Re: "Collatz Conjecture" Discussion
I'm wondering how many other people took the 30 seconds to program this then spent 1015 minutes punching in random large numbers to see if it works.
Re: Collatz Conjecture
syko_lozz wrote:I am not enough of a geek to have heard this one before
but I AM enough of a geek to find it pretty cool
sigh, the lonely, uncool middle again
...here I am, stuck in the middle with you.

 Posts: 12
 Joined: Sun Aug 16, 2009 10:26 am UTC
Re: "Collatz Conjecture" Discussion
Last summer I went to a three week academic camp. I took a class on infinity there and on the last day my teacher introduced this problem. Of course he didn't tell us what the problem was called and he certainly didn't say it was a conjecture. He gave us the whole 3 hour class time to say our goodbyes to everyone and try to prove that you would always reach one. About half an hour in I asked our teacher if this was some unsolved problem and if he was going to steal our solution if one of us solved it and win some math prize. He quietly denied it and quickly changed the subject. He eventually told us a name for the problem, but used a name different from the collatz conjecture and made us promise not to go and look up the solution. I forgot the name the next day and never had the drive to go searching for it. Understandably, I was completely unsurprised that it was unsolved when I eventually did stumble upon that wikipedia page a month or so ago. This comic brought up some good memories, and now I'll probably end up spending half the weekend working on this problem even though I know I won't solve it.
Re: "Collatz Conjecture" Discussion
mania wrote:So who has made a program that adds numbers to a similar looking graph already?
http://www.graphviz.org/
 MystRivenExile
 Posts: 3
 Joined: Fri Feb 15, 2008 5:24 am UTC
Re: "Collatz Conjecture" Discussion
My favorite unsolved mathematics problem of which I have a completely healthy obsession. Currently working on one of the latest Project Euler problems involving a modification of the Conjecture. This comic made me quite happy to see.

 Posts: 30
 Joined: Tue Jun 05, 2007 12:41 am UTC
Re: Collatz Conjecture
syko_lozz wrote:I am not enough of a geek to have heard this one before
but I AM enough of a geek to find it pretty cool
sigh, the lonely, uncool middle again
I'm not enough of a geek to have heard of this one before either.
But I am enough of a geek to have written a script to test the conjecture as soon as I read the comic. I used PHP for it, which isn't as geeky as I'd like, but you work with what you have.
Not sure why anyone would try to work it out by hand. We have computers for a reason.
Powder wrote:I'm wondering how many other people took the 30 seconds to program this then spent 1015 minutes punching in random large numbers to see if it works.
I just set the program up to pick a random number on its own every time it runs. Much easier.
Re: "Collatz Conjecture" Discussion
That graph is a nice visualisation! How were the numbers (and layout!) chosen?
Erdős, who had a good intuition for the hardness of problems (many people have said he gave them problems exactly at their level), said that mathematics is not yet ready for problems like the Collatz conjecture (or whatever name it went by at the time). I believe it was one of the problems to which he had attached the highest prize money.
Edit: The conjecture has been verified for all starting values up to 20 × 2^{58} ≈ 5.764 × 10^{18} (Wikipedia reference: http://www.ieeta.pt/~tos/3x+1.html), so don't expect your scripts to find a counterexample soon.
Erdős, who had a good intuition for the hardness of problems (many people have said he gave them problems exactly at their level), said that mathematics is not yet ready for problems like the Collatz conjecture (or whatever name it went by at the time). I believe it was one of the problems to which he had attached the highest prize money.
Edit: The conjecture has been verified for all starting values up to 20 × 2^{58} ≈ 5.764 × 10^{18} (Wikipedia reference: http://www.ieeta.pt/~tos/3x+1.html), so don't expect your scripts to find a counterexample soon.
Last edited by svat on Fri Mar 05, 2010 5:44 am UTC, edited 1 time in total.

 Posts: 548
 Joined: Tue Jan 12, 2010 1:04 am UTC
 Contact:
Re: "Collatz Conjecture" Discussion
I wonder if anyone has ever generalized this to the dyadic rationals:
If the finite binary expansion of n is ...a4a3a2a1a0.a1a2a3a4...
then f(n) = 2n if it is an even integer, and f(n) = 3n+2^k, where ak is the last 1 digit. For example, 2.25 = 10.01. This maps to 3*10.01+.01=111=7. And 7.375=111.011 maps to 3*111.011+.001=10110.01=22.25. This does the same thing of adding a factor of two if it is "odd" to any amount, and removes a factor of two if it's even.
However, you couldn't do this in reverse, because there are infinite numbers that map to any given one.
Anyone want to try writing a program for that? After all, rationals are countable, so one should be able to work through them...
If the finite binary expansion of n is ...a4a3a2a1a0.a1a2a3a4...
then f(n) = 2n if it is an even integer, and f(n) = 3n+2^k, where ak is the last 1 digit. For example, 2.25 = 10.01. This maps to 3*10.01+.01=111=7. And 7.375=111.011 maps to 3*111.011+.001=10110.01=22.25. This does the same thing of adding a factor of two if it is "odd" to any amount, and removes a factor of two if it's even.
However, you couldn't do this in reverse, because there are infinite numbers that map to any given one.
Anyone want to try writing a program for that? After all, rationals are countable, so one should be able to work through them...
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me  __ 
Good fucking job Will Yu, you found me  __ 
Re: "Collatz Conjecture" Discussion
I am no mathematician, probably the diametric opposite in fact, so can someone explain to me, how anyone COULD prove this theory.
What would a proof entail?.
What would a proof entail?.
Abuse of words has been the great instrument of sophistry and chicanery, of party, faction, and division of society.
John Adams
John Adams

 Posts: 27
 Joined: Sat Aug 22, 2009 1:21 am UTC
Re: "Collatz Conjecture" Discussion
In python, for your convenience:
Yeah. Good comic.
Spoiler:
Yeah. Good comic.

 Posts: 129
 Joined: Wed Jan 14, 2009 6:09 am UTC
Re: "Collatz Conjecture" Discussion
This made me laugh:
(Emphasis added)
Wikipedia wrote:Paul Erdős said about the Collatz conjecture: "Mathematics is not yet ready for such confusing, troubling, and hard problems." He offered $500 for its solution.
(Emphasis added)
Re: "Collatz Conjecture" Discussion
So, could you make fractals with this?
Cynical Idealist wrote:Velict wrote:Good Jehova, there are cheesegraters on the blagotube!
This is, for some reason, one of the funniest things I've read today.
 The Scyphozoa
 Posts: 2871
 Joined: Sun Jun 01, 2008 6:33 pm UTC
 Location: Sector 5
Re: "Collatz Conjecture" Discussion
Least funny comic in quite a while, actually.
3rdtry wrote:If there ever is another World War, I hope they at least have the decency to call it "World War 2: Episode One"
doogly wrote:murder is a subset of being mean
Re: "Collatz Conjecture" Discussion
Wrote a little program to generate the closure of the graph from 11024.
Result images (gigantic) are here: http://hubrisarts.com/collatz.png and http://hubrisarts/collatz.svg.
Result images (gigantic) are here: http://hubrisarts.com/collatz.png and http://hubrisarts/collatz.svg.
Re: "Collatz Conjecture" Discussion
Powder wrote:I'm wondering how many other people took the 30 seconds to program this then spent 1015 minutes punching in random large numbers to see if it works.
Those familiar with the UVa Online Judge have done this problem long ago. In fact, it is the very first problem in their archive
For those interested, http://uva.onlinejudge.org/index.php?op ... problem=36
 phlip
 Restorer of Worlds
 Posts: 7569
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: "Collatz Conjecture" Discussion
Apteryx wrote:I am no mathematician, probably the diametric opposite in fact, so can someone explain to me, how anyone COULD prove this theory.
What would a proof entail?.
One potential method would be induction: for example if you could prove that, for any starting number, you eventually end up at a number less than your starting number, then you'd always end up at one (because that lesser number would in turn have to eventually end up at an even smaller number, and so on, and there's only so many times you can do that before you'll end up at 1). However, this might not be true... if you have an odd number, and you do 3n+1, you get an even number, so you halve that, but that's still bigger than your original number... and then the number might be odd or even, so you might have to do the tripling thing again... noone's proven that this can't happen forever (though noone's proven that it can happen forever either).
Another is that there are only three possibilities: either every number reaches 1, or there exists some number that eventually cycles (ie you perform the steps a lot and end up back at your original starting number), or there exists some number that grows continually without bound. If you can prove that the second and third options don't exist, then the first must be true by default.
GreenStormElf: use [
VHBT wrote:The regular expression would actually be more like /.+s.+ss/, but that's not why it's wrong. It's wrong because "success" does not have an s in the middle.
They both match /.*s.*ss/i, though...
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: "Collatz Conjecture" Discussion
Apteryx wrote:I am no mathematician, probably the diametric opposite in fact, so can someone explain to me, how anyone COULD prove this theory.
What would a proof entail?.
Induction perhaps?
http://en.wikipedia.org/wiki/Mathematical_induction
edit: ninja'd...
"We should take harpoons!"
"And dynamite!"
"Don't you think that is going a bit overboard..."
"These aren't regular sharks..."
"And dynamite!"
"Don't you think that is going a bit overboard..."
"These aren't regular sharks..."
 eviloatmeal
 Posts: 570
 Joined: Thu Dec 11, 2008 9:39 am UTC
 Location: Upside down in space!
 Contact:
Re: "Collatz Conjecture" Discussion
Apteryx wrote:*It just occurred to me that Americans say "call", we say "ring". Ours isn't confusing, "Ring your sister will you" means use a phone.
"Call your sister will you", could mean phone, or step outside and yell.
At the risk of being redundant as I stopped here to quote this; "Ring your sister will you" could also imply picking her up and shaking her like a bell.
GreenStormElf wrote:In python, for your convenience:Spoiler:
Yeah. Good comic.
Dude, it's python, you can't just break the whitespace like that·
Last edited by eviloatmeal on Fri Mar 05, 2010 6:15 am UTC, edited 1 time in total.
Re: "Collatz Conjecture" Discussion
luqui wrote:Wrote a little program to generate the closure of the graph from 11024.
Result images (gigantic) are here: http://hubrisarts.com/collatz.png and http://hubrisarts/collatz.svg.
beautiful! thanks for sharing
Magus wrote:If history is to change, let it change. If the world is to be destroyed, so be it. If my fate is to die, I must simply laugh.
Just as you touch the energy of every life form you meet, so, too, will will their energy strengthen you.
Re: "Collatz Conjecture" Discussion
Shouldn't there be an arrow from 1 to 4?
Re: "Collatz Conjecture" Discussion
Shouldn't there be an arrow from 1 to 4?
No, once you reach 1 you're done.
 eviloatmeal
 Posts: 570
 Joined: Thu Dec 11, 2008 9:39 am UTC
 Location: Upside down in space!
 Contact:
Re: "Collatz Conjecture" Discussion
Ok, so is there a simple explanation why odds need to be multiplied by 3? It seems to work by just adding one, and logically, it should, no?

 Posts: 90
 Joined: Wed Apr 01, 2009 6:11 pm UTC
Re: "Collatz Conjecture" Discussion
I thought it was so obvious until I put my thoughts onto paper (yes, I was wondering how it could appear so obvious to me, yet no committed mathematicians have figured it out). I started with this:
Start with positive integer n.
Case 1: n is even, so n is of the form 2k (an even can always be represented by 2 times some constant). Applying the procedure and dividing by 2 will obtain 2k/2 = k, where k is even or odd. If k is even (of form 2k), this process will repeat until k is odd (lowest even k is 2, in which case 2k/2 = 1).
Case 2: n is odd, so form is 2k+1. Applying the procedure 3n+1 obtains 3(2k+1)+1 = 6k+4 = 2(3k+2) which is of form 2k. Therefore, applying the procedure to an odd number will always result in an even, which as shown in Case 1 converges to 1.
As you can see, this proof is completely invalid (but it made sense in my head!). It seemed brilliant until I realized that Case 1 doesn't necessarily converge to 1; by counterexample k=3 in Case 1, 2*3/2 = 3. 3 is NOT even. :S
I'm going to try not wasting time on this.
Start with positive integer n.
Case 1: n is even, so n is of the form 2k (an even can always be represented by 2 times some constant). Applying the procedure and dividing by 2 will obtain 2k/2 = k, where k is even or odd. If k is even (of form 2k), this process will repeat until k is odd (lowest even k is 2, in which case 2k/2 = 1).
Case 2: n is odd, so form is 2k+1. Applying the procedure 3n+1 obtains 3(2k+1)+1 = 6k+4 = 2(3k+2) which is of form 2k. Therefore, applying the procedure to an odd number will always result in an even, which as shown in Case 1 converges to 1.
As you can see, this proof is completely invalid (but it made sense in my head!). It seemed brilliant until I realized that Case 1 doesn't necessarily converge to 1; by counterexample k=3 in Case 1, 2*3/2 = 3. 3 is NOT even. :S
I'm going to try not wasting time on this.
Re: "Collatz Conjecture" Discussion
The Scyphozoa wrote:Least funny comic in quite a while, actually.
thanks for making me spend half an hour googling for code lyoko because of your user avatar. great show... too bad they stopped showing it.
Return to “Individual XKCD Comic Threads”
Who is online
Users browsing this forum: No registered users and 50 guests