0710: "Collatz Conjecture"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

0710: "Collatz Conjecture"

Postby squareroot » Fri Mar 05, 2010 5:05 am UTC

Image

Title text: "The Strong Collatz Conjecture states this hold for any set of obsessively-hand-applied rules.

Funny. :D 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 hand-apply 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 - __ -

cleverdan
Posts: 56
Joined: Sat Feb 23, 2008 5:41 am UTC

Re: Collatz Conjecture

Postby cleverdan » Fri Mar 05, 2010 5:08 am UTC

Not a bad comic. Quite funny actually.

User avatar
Magic Molly
Posts: 94
Joined: Sat Sep 26, 2009 10:42 pm UTC

Re: Collatz Conjecture

Postby Magic Molly » Fri Mar 05, 2010 5:08 am UTC

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:
They all worked

User avatar
hintss
Posts: 1294
Joined: Wed Nov 25, 2009 7:19 am UTC
Contact:

Re: Collatz Conjecture

Postby hintss » Fri Mar 05, 2010 5:08 am UTC

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 :-)

User avatar
jspenguin
Posts: 84
Joined: Wed Apr 16, 2008 7:39 pm UTC
Contact:

Re: Collatz Conjecture

Postby jspenguin » Fri Mar 05, 2010 5:09 am UTC

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

SocialSceneRepairman
Posts: 199
Joined: Sat May 24, 2008 4:17 am UTC

Re: Collatz Conjecture

Postby SocialSceneRepairman » Fri Mar 05, 2010 5:10 am UTC

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

User avatar
-.Mateo.-
Posts: 264
Joined: Sun Jun 28, 2009 12:01 am UTC
Location: Location Location

Re: Collatz Conjecture

Postby -.Mateo.- » Fri Mar 05, 2010 5:11 am UTC

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

User avatar
syko_lozz
Posts: 53
Joined: Fri Jan 11, 2008 5:30 am UTC
Location: Oz

Re: Collatz Conjecture

Postby syko_lozz » Fri Mar 05, 2010 5:12 am UTC

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

User avatar
Omegaton
Posts: 700
Joined: Sun Apr 19, 2009 6:23 pm UTC

Re: Collatz Conjecture

Postby Omegaton » Fri Mar 05, 2010 5:13 am UTC

Well, that's a new thing I learned the existence of today. Nice.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Re: "Collatz Conjecture" Discussion

Postby squareroot » Fri Mar 05, 2010 5:16 am UTC

Fixed the title. :D 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 - __ -

User avatar
hintss
Posts: 1294
Joined: Wed Nov 25, 2009 7:19 am UTC
Contact:

Re: Collatz Conjecture

Postby hintss » Fri Mar 05, 2010 5:22 am UTC

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 3-4 minutes. found that out on monday

Roflchaos
Posts: 1
Joined: Wed Dec 09, 2009 2:08 am UTC

Re: "Collatz Conjecture" Discussion

Postby Roflchaos » Fri Mar 05, 2010 5:25 am UTC

The comic is linked to 709, not 710 :P

I actually want to try this out :D

VHBT
Posts: 50
Joined: Fri Mar 28, 2008 8:18 pm UTC

Re: "Collatz Conjecture" Discussion

Postby VHBT » Fri Mar 05, 2010 5:25 am UTC

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.

Apteryx
Posts: 174
Joined: Tue Feb 09, 2010 5:41 am UTC

Re: "Collatz Conjecture" Discussion

Postby Apteryx » Fri Mar 05, 2010 5:26 am UTC

How long before someone critics it on its humour?.

:wink:

This theory would be of interest to solipsists, and they wouldn't care if no-one 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

mania
Posts: 24
Joined: Sat Sep 20, 2008 9:44 am UTC

Re: "Collatz Conjecture" Discussion

Postby mania » Fri Mar 05, 2010 5:28 am UTC

So who has made a program that adds numbers to a similar looking graph already?

Kain
Posts: 1140
Joined: Wed Aug 27, 2008 4:29 am UTC
Location: At the center of the observable universe.

Re: "Collatz Conjecture" Discussion

Postby Kain » Fri Mar 05, 2010 5:29 am UTC

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

Powder
Posts: 7
Joined: Mon Sep 03, 2007 5:38 am UTC
Location: OKC
Contact:

Re: "Collatz Conjecture" Discussion

Postby Powder » Fri Mar 05, 2010 5:30 am UTC

I'm wondering how many other people took the 30 seconds to program this then spent 10-15 minutes punching in random large numbers to see if it works.

Jay_au
Posts: 7
Joined: Mon Jan 11, 2010 10:44 am UTC

Re: Collatz Conjecture

Postby Jay_au » Fri Mar 05, 2010 5:32 am UTC

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.

fleshBasedProcessor
Posts: 12
Joined: Sun Aug 16, 2009 10:26 am UTC

Re: "Collatz Conjecture" Discussion

Postby fleshBasedProcessor » Fri Mar 05, 2010 5:34 am UTC

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.

erpo41
Posts: 7
Joined: Fri Jun 20, 2008 7:49 am UTC

Re: "Collatz Conjecture" Discussion

Postby erpo41 » Fri Mar 05, 2010 5:34 am UTC

mania wrote:So who has made a program that adds numbers to a similar looking graph already?

http://www.graphviz.org/

User avatar
MystRivenExile
Posts: 3
Joined: Fri Feb 15, 2008 5:24 am UTC

Re: "Collatz Conjecture" Discussion

Postby MystRivenExile » Fri Mar 05, 2010 5:36 am UTC

My favorite unsolved mathematics problem of which I have a completely healthy obsession. :D Currently working on one of the latest Project Euler problems involving a modification of the Conjecture. This comic made me quite happy to see.

Drooling Iguana
Posts: 30
Joined: Tue Jun 05, 2007 12:41 am UTC

Re: Collatz Conjecture

Postby Drooling Iguana » Fri Mar 05, 2010 5:37 am UTC

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 10-15 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.

svat
Posts: 2
Joined: Fri Mar 05, 2010 5:36 am UTC

Re: "Collatz Conjecture" Discussion

Postby svat » Fri Mar 05, 2010 5:41 am UTC

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 × 258 ≈ 5.764 × 1018 (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.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Re: "Collatz Conjecture" Discussion

Postby squareroot » Fri Mar 05, 2010 5:44 am UTC

I wonder if anyone has ever generalized this to the dyadic rationals:
If the finite binary expansion of n is ...a4a3a2a1a0.a-1a-2a-3a-4...
then f(n) = 2n if it is an even integer, and f(n) = 3n+2^-k, where a-k 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... :D
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

Apteryx
Posts: 174
Joined: Tue Feb 09, 2010 5:41 am UTC

Re: "Collatz Conjecture" Discussion

Postby Apteryx » Fri Mar 05, 2010 5:48 am UTC

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?.
Abuse of words has been the great instrument of sophistry and chicanery, of party, faction, and division of society.
John Adams

GreenStormElf
Posts: 27
Joined: Sat Aug 22, 2009 1:21 am UTC

Re: "Collatz Conjecture" Discussion

Postby GreenStormElf » Fri Mar 05, 2010 5:55 am UTC

In python, for your convenience:
Spoiler:
while(0==0):
a=int(raw_input("A="))
b=0
c=0

while(c==0):
if(a%2==0):
a=a/2
else:
a=a*3+1

print a
b=b+1
if(b%1000==1):
print b

if a==1:
c=1
print("End")
print("Steps="+str(b))


Yeah. Good comic.

The Mad Scientist
Posts: 129
Joined: Wed Jan 14, 2009 6:09 am UTC

Re: "Collatz Conjecture" Discussion

Postby The Mad Scientist » Fri Mar 05, 2010 5:58 am UTC

This made me laugh:

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)

User avatar
LuNatic
Posts: 973
Joined: Thu Nov 20, 2008 4:21 am UTC
Location: The land of Aus

Re: "Collatz Conjecture" Discussion

Postby LuNatic » Fri Mar 05, 2010 5:59 am UTC

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.

User avatar
The Scyphozoa
Posts: 2871
Joined: Sun Jun 01, 2008 6:33 pm UTC
Location: Sector 5

Re: "Collatz Conjecture" Discussion

Postby The Scyphozoa » Fri Mar 05, 2010 6:02 am UTC

Least funny comic in quite a while, actually.
Image
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

luqui
Posts: 4
Joined: Fri Apr 13, 2007 6:24 am UTC
Location: Boulder, CO

Re: "Collatz Conjecture" Discussion

Postby luqui » Fri Mar 05, 2010 6:03 am UTC

Wrote a little program to generate the closure of the graph from 1-1024.

Result images (gigantic) are here: http://hubrisarts.com/collatz.png and http://hubrisarts/collatz.svg.

knightry
Posts: 4
Joined: Wed May 27, 2009 4:56 am UTC

Re: "Collatz Conjecture" Discussion

Postby knightry » Fri Mar 05, 2010 6:03 am UTC

Powder wrote:I'm wondering how many other people took the 30 seconds to program this then spent 10-15 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

User avatar
phlip
Restorer of Worlds
Posts: 7569
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: "Collatz Conjecture" Discussion

Postby phlip » Fri Mar 05, 2010 6:04 am UTC

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 [code][/code] tags... otherwise, all your whitespace disappears. And whitespace is important for Python.

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)⚠);}
[he/him/his]

User avatar
tpow
Posts: 27
Joined: Tue Apr 28, 2009 9:30 pm UTC

Re: "Collatz Conjecture" Discussion

Postby tpow » Fri Mar 05, 2010 6:06 am UTC

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 over-board..."
"These aren't regular sharks..."

User avatar
eviloatmeal
Posts: 570
Joined: Thu Dec 11, 2008 9:39 am UTC
Location: Upside down in space!
Contact:

Re: "Collatz Conjecture" Discussion

Postby eviloatmeal » Fri Mar 05, 2010 6:09 am UTC

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:
while(0==0):
a=int(raw_input("A="))
b=0
c=0

while(c==0):
if(a%2==0):
a=a/2
else:
a=a*3+1

print a
b=b+1
if(b%1000==1):
print b

if a==1:
c=1
print("End")
print("Steps="+str(b))


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.
*** FREE SHIPPING ENABLED ***
Image
Riddles are abound tonightImage

User avatar
-.Mateo.-
Posts: 264
Joined: Sun Jun 28, 2009 12:01 am UTC
Location: Location Location

Re: "Collatz Conjecture" Discussion

Postby -.Mateo.- » Fri Mar 05, 2010 6:12 am UTC

luqui wrote:Wrote a little program to generate the closure of the graph from 1-1024.

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.

mankoff
Posts: 2
Joined: Fri Mar 05, 2010 6:15 am UTC

Re: "Collatz Conjecture" Discussion

Postby mankoff » Fri Mar 05, 2010 6:16 am UTC

Shouldn't there be an arrow from 1 to 4?

DT_
Posts: 44
Joined: Mon Feb 01, 2010 4:41 am UTC

Re: "Collatz Conjecture" Discussion

Postby DT_ » Fri Mar 05, 2010 6:19 am UTC

Shouldn't there be an arrow from 1 to 4?

No, once you reach 1 you're done.

User avatar
eviloatmeal
Posts: 570
Joined: Thu Dec 11, 2008 9:39 am UTC
Location: Upside down in space!
Contact:

Re: "Collatz Conjecture" Discussion

Postby eviloatmeal » Fri Mar 05, 2010 6:21 am UTC

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?
*** FREE SHIPPING ENABLED ***
Image
Riddles are abound tonightImage

chocolate.razorblades
Posts: 90
Joined: Wed Apr 01, 2009 6:11 pm UTC

Re: "Collatz Conjecture" Discussion

Postby chocolate.razorblades » Fri Mar 05, 2010 6:22 am UTC

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.

User avatar
hintss
Posts: 1294
Joined: Wed Nov 25, 2009 7:19 am UTC
Contact:

Re: "Collatz Conjecture" Discussion

Postby hintss » Fri Mar 05, 2010 6:24 am UTC

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