0710: "Collatz Conjecture"

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

Moderators: Moderators General, Prelates, Magistrates

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

Re: "Collatz Conjecture" Discussion

eviloatmeal wrote: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?

The function was not made with the goal of reaching 1. It was simply discovered by Collatz who conjectured that it always reached 1.

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

Re: "Collatz Conjecture" Discussion

eviloatmeal wrote: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?

I think you're right. It doesn't seem like they should have to be multiplied by 3. Applying the procedure to an odd number, as shown in my last post (that part was valid), always results in an even number, and an even number is always 1 after an odd number.

However, Collatz wanted to get to bigger numbers faster so that his conjecture would seem EPIC.

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

Re: "Collatz Conjecture" Discussion

eviloatmeal wrote: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?

If you do that, you get "if it's even, divide by 2, if not, add 1, then divide by 2"...that's not fun! if the only thing you do is divide evens, it's pretty obvious you'll get to 2 (and then 1), but if you do "n*3+1", then you can get odds from odds and get really high numbers before going down again! you could go up-down-up-down...there's no immediate guarantee the sequence will ever get to 1, it could just keep going up (there's no way of knowing, since if it had no end, you would just keep searching for it forever)

EDIT: I know this is wrong, I'm just not changing it because I have no problem with everyone knowing I made a stupid mistake (actually I can't stand it, but I have to learn to cope with failure...I'm not good at it)

Now, to correct myself:
3n+1 CAN'T be odd, BUT (3n+1)/2 can, and is also larger than n, so you can "keep going up" indefinitely, just with big bumps on the way (if you get an odd-even-odd pattern, for example, you'll keep going up...until you get even-even (odd-even-even would be (3n+1)/4)
Last edited by -.Mateo.- on Fri Mar 05, 2010 6:44 am UTC, edited 1 time in total.
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.

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

Re: "Collatz Conjecture" Discussion

Ah, ok, that seems simple enough. Wonder if it works with other numbers...

Edit: Seems as though it does not.
Last edited by eviloatmeal on Fri Mar 05, 2010 6:35 am UTC, edited 1 time in total.
*** FREE SHIPPING ENABLED *** Riddles are abound tonight mmaluff
Posts: 12
Joined: Wed May 13, 2009 10:38 pm UTC

Re: "Collatz Conjecture" Discussion

Oh man!!! I love the Collatz conjecture! Probably my favourite unsolved problem so far.

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

Re: "Collatz Conjecture" Discussion

-.Mateo.- wrote:but if you do "n*3+1", then you can get odds from odds

An odd number times an odd number + 1 is always even, so you can't get odds from odds. However, since (3n+1)/2 is larger than n, it isn't trivial to prove that n will always reach 1. For the example above where you simply do n + 1 for odds instead of 3n+1, (n + 1)/2 will be smaller than n and it is very simple to prove with induction that that sequence will always reach 1.

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

Re: "Collatz Conjecture" Discussion

DT_ wrote:
-.Mateo.- wrote:but if you do "n*3+1", then you can get odds from odds

An odd number times an odd number + 1 is always even, so you can't get odds from odds. However, since (3n+1)/2 is larger than n, it isn't trivial to prove that n will always reach 1. For the example above where you simply do n + 1 for odds instead of 3n+1, (n + 1)/2 will be smaller than n and it is very simple to prove with induction that that sequence will always reach 1.

right. sorry...I skipped a step to get to "it's larger than n", and that messed the rest up in my head
Last edited by -.Mateo.- on Fri Mar 05, 2010 6:33 am UTC, edited 2 times in total.
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.

brakos82
Posts: 536
Joined: Tue Feb 24, 2009 12:06 am UTC
Location: My happy place :)

Re: "Collatz Conjecture" Discussion

I'm stealing 247's title text idea and putting it to use here in a couple weeks.
I am Brakos, and I may or may not approve this message.

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

Re: "Collatz Conjecture" Discussion

DT_ wrote:For the example above where you simply do n + 1 for odds instead of 3n+1, (n + 1)/2 will be smaller than n and it is very simple to prove with induction that that sequence will always reach 1.

Math doesn't work by induction. We want a deductive proof!!!

EDIT: I posted this, then I read a chapter in my Discrete Math textbook called "Why Mathematical Induction Is Valid". I thought you were referring to inductive reasoning. :S
Last edited by chocolate.razorblades on Mon Mar 08, 2010 3:49 am UTC, edited 1 time in total.

compro01
Posts: 27
Joined: Wed Nov 26, 2008 4:45 pm UTC

Re: "Collatz Conjecture" Discussion

eviloatmeal wrote:
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·

for some reason, when you have the quote in the reply screen, it has the proper whitespace, but not in the post after.
Last edited by compro01 on Fri Mar 05, 2010 6:34 am UTC, edited 1 time in total.

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

Re: "Collatz Conjecture" Discussion

DT_ wrote:For the example above where you simply do n + 1 for odds instead of 3n+1, (n + 1)/2 will be smaller than n and it is very simple to prove with induction that that sequence will always reach 1.

Math doesn't work by induction. We want a deductive proof!!!

you just want the \$500
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.

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

Re: "Collatz Conjecture" Discussion

Is there a way to calculate the limit as n approaches infinity of a conditional function like {3n+1 if nmod2=1, n/2 if nmod2=0}?

It seems like graphs would make suitable proofs for these, but there are already a lot and I don't understand why the math community won't accept them.

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

Re: "Collatz Conjecture" Discussion

compro01 wrote:
eviloatmeal wrote:
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·

for some reason, when you have the quote in the reply screen, it has the proper whitespace, but not in the post after.

Should I just default to clicking quote before I read every new post, in order to save everyone else the 5 seconds it takes to highlight the code and press the "Code" button? *** FREE SHIPPING ENABLED *** Riddles are abound tonight DT_
Posts: 44
Joined: Mon Feb 01, 2010 4:41 am UTC

Re: "Collatz Conjecture" Discussion

chocolate.razorblades wrote:It seems like graphs would make suitable proofs for these, but there are already a lot and I don't understand why the math community won't accept them.

No one has yet proven that given the graph as constructed in the comic and any natural number n, that n is in the graph.

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

Re: "Collatz Conjecture" Discussion

eviloatmeal wrote: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?
Yes, but then the puzzle would be very simple - of course every natural number eventually reaches 1. Who wants a simple puzzle? Collatz is interesting because it appears to be simple, but it's still unsolved.

chocolate.razorblades wrote:Math doesn't work by induction.
What crazy maths system are you using? In the one I'm using, induction is perfectly valid.  Unless you think DT meant inductive reasoning... then your comment would make sense. It's still wrong though, as DT was referring to mathematical induction.

chocolate.razorblades wrote:Is there a way to calculate the limit as n approaches infinity of a conditional function like {3n+1 if nmod2=1, n/2 if nmod2=0}?
Yes, you can do it, the same way as any other limit... but most of the usual shortcuts won't work.
We don't want a limit here anyway, though... most of the sequences don't have a limit (since they end going 1,4,2,1,4,2,1,4,2,1...). We're more interested in the finite-though-possibly-very-long behaviour, not the infinite behaviour.

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

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

Re: "Collatz Conjecture" Discussion

DT_ wrote:
chocolate.razorblades wrote:It seems like graphs would make suitable proofs for these, but there are already a lot and I don't understand why the math community won't accept them.

No one has yet proven that given the graph as constructed in the comic and any natural number n, that n is in the graph.

This may call for some extension of Cantor diagonalization. I don't think this is worth the \$500. I'm done with this.

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

Re: "Collatz Conjecture" Discussion

DT_ wrote:
chocolate.razorblades wrote:It seems like graphs would make suitable proofs for these, but there are already a lot and I don't understand why the math community won't accept them.

No one has yet proven that given the graph as constructed in the comic and any natural number n, that n is in the graph.

This may call for some extension of Cantor diagonalization. I don't think this is worth the \$500. I'm done with this.

has anyone here NOT read GEB?
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.

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

Re: "Collatz Conjecture" Discussion

chocolate.razorblades wrote:This may call for some extension of Cantor diagonalization.

Hmm? What does that have to do with the price of chickens in Turkmenistan?

Cantor's diagonalisation proofs (of which there are two rather unrelated ones, but in the same field) are related to cardinality of infinite sets... whether or not a particular set has as many elements as the natural numebrs.

But we don't care about the "size" of the graph - it's obvious that the graph has as many nodes as there are naturals. That doesn't mean that every natural appears in it somewhere. For analogy, there are the same number of even numbers as there are integers, that doesn't mean that every integer is even!

Just accept that if the solution was as simple as that, someone would've thought of it by now.

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

plut0nium
Posts: 1
Joined: Fri Mar 05, 2010 6:50 am UTC

Re: "Collatz Conjecture" Discussion

hu...

if first read the lolcatz conjecture Posts: 90
Joined: Wed Apr 01, 2009 6:11 pm UTC

Re: "Collatz Conjecture" Discussion

phlip wrote:
chocolate.razorblades wrote:This may call for some extension of Cantor diagonalization.

Hmm? What does that have to do with the price of chickens in Turkmenistan?

Cantor's diagonalisation proofs (of which there are two rather unrelated ones, but in the same field) are related to cardinality of infinite sets... whether or not a particular set has as many elements as the natural numebrs.

But we don't care about the "size" of the graph - it's obvious that the graph has as many nodes as there are naturals. That doesn't mean that every natural appears in it somewhere. For analogy, there are the same number of even numbers as there are integers, that doesn't mean that every integer is even!

Just accept that if the solution was as simple as that, someone would've thought of it by now.

I was thinking about something like

1/1 -> 1/2 -> 1/3 -> 1/4 -> 1/5 -> ...
2/1 -> 2/2 -> 2/3 -> 2/4 -> 2/5 -> ...
3/1 -> 3/2 -> 3/3 -> 3/4 -> 3/5 -> ...
4/1 -> 4/2 -> 4/3 -> 4/4 -> 4/5 -> ...
5/1 -> 5/2 -> 5/3 -> 5/4 -> 5/5 -> ...
...

in which we know that every rational number will be represented, so I was thinking that maybe we could do something similar to show that all natural numbers are represented in a graph of the Collatz conjecture.

valbaca
Posts: 9
Joined: Tue Nov 20, 2007 7:00 am UTC

Re: "Collatz Conjecture" Discussion

In C w/ infinite loop:

Code: Select all

`#include <stdio.h>unsigned long collatz(unsigned long n);int main(){   unsigned long n = 2;   while(1){      printf("Number: %d",n);      unsigned long iterations = collatz(n);      printf("Iterations: %d\n\n",iterations);      n++;   }   return 0;}unsigned long collatz(unsigned long n){   unsigned long iterations = 1;   while(n != 1){      if(n % 2 == 0)    // even         n /= 2;      else      // odd         n = (3*n) + 1;      printf("->%d",n);      iterations = iterations + 1;   }   printf("\n");   return iterations;}`

Edit: I'll leave my computer running this tonight and see how far it gets Posts: 1
Joined: Fri Mar 05, 2010 7:03 am UTC

Re: "Collatz Conjecture" Discussion

I'll admit, I'm way too stupid to be reading this comic and appreciating its humor. I shouldn't even be posting on these forums, however I have to know what so special about the Collatz Conjecture?

If you multiply any odd number by 3 and add 1 it become even.

If you multiply any even number by 3 and add 1 it become odd.

If you divide any even number by 2, and keep dividing by 2 you will eventually reach 1.

So if you start with an even number you will change it to an odd which you will change back to an even, and then just keep halving it until you reach 1.

If you start with an odd number you will make it even and then keep halving it until you reach 1.

Interesting observation, but unless I'm missing something it doesn't seem to be anything mind-blowing.

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

Re: "Collatz Conjecture" Discussion

TheShadow wrote:If you multiply any odd number by 3 and add 1 it become even.

Correct.
TheShadow wrote:If you multiply any even number by 3 and add 1 it become odd.

True in general but if n is even then the next value in the sequence will be n/2, not (3n + 1).
TheShadow wrote:If you divide any even number by 2, and keep dividing by 2 you will eventually reach 1.

Not true. Consider 6: 6/2 = 3. What is true is that after finitely many divisions by 2, you will reach an odd number, not necessarily 1. As you stated above, the Collatz conjecture will then produce another even number out of this odd one, but the new even number is larger than your odd number, even after division by 2.

In general the sequences goes up and down and up and down and so far it has reached 1 for all tested values. However, it's possible that there exists some number n for which either:
1) The sequence of numbers continues growing forever (it does not monotonically increase, since every odd number produces an even number which is then reduced, but it's still possible that the values could approach infinity).
2) The sequence of numbers produced by n is a cycle: n -> n1 -> n2 -> ... -> nk -> n

TheShadow wrote:So if you start with an even number you will change it to an odd which you will change back to an even, and then just keep halving it until you reach 1.

If you start with an odd number you will make it even and then keep halving it until you reach 1.

The problem with this argument is that the even number produced is larger than the odd number you started with.
Last edited by DT_ on Fri Mar 05, 2010 7:29 am UTC, edited 3 times in total.

s0merand0mdude
Posts: 37
Joined: Fri Dec 04, 2009 6:35 am UTC

Re: "Collatz Conjecture" Discussion

Oddly enough, my geometry class spent yesterday and today working on calculator programs on the TI-83 and TI-84. Here's a quick program I made after seeing this comic to test the conjecture using a given number.

Code: Select all

`PROGRAM:COLLATZ:Disp "ENTER A NUMBER":Input N:0→I:Lbl 3:While N=int(N):While N≠1:I+1→I:If N/2=int(N/2):Then:Disp N/2:N/2→N:Else:Disp 3*N+1:3*N+1→N:End:Goto 3:End:0.5→N:Disp "NUMBER OF STEPS":Disp I:End:`

I probably didn't need that many "if-then-else" statements, but it was a fun program to write.

Edit: If you add I+1→I after the second ":Else" and put ":Disp "NUMBER OF STEPS",:Disp I", you can even count the number of steps used to get to 1. Although, you probably would need to put 0→I before the ":Lbl 3" to make sure you don't carry over any values of I previously used.

Edit 2: After a quick read of the manual and some outside-of-the-box thinking, I removed all the goto's except for the one causing the main loop.

Edit 3: Using one more While loop, I got rid of all the goto's and now the program runs much much faster, especially when there are many steps.
Last edited by s0merand0mdude on Fri Mar 05, 2010 8:23 am UTC, edited 4 times in total.
unus vox wrote:Then again, you're looking for characterization, compelling dialogue, and cohesion in a 3-panel web comic with stick figures.

TimeSpaceMage
Posts: 23
Joined: Thu Nov 26, 2009 4:05 am UTC
Contact:

Re: "Collatz Conjecture" Discussion

valbaca: You might consider using fprintf to output to a file instead of the screen, both to speed up the program and so you can more easily check the output when you wake up.

TheShadow: Not all even numbers are direct powers of 2. Say you have the number 86. Dividing by 2 gives 43, which is odd. This requires the 3n+1 step, giving 130 which is higher than the original 86. Dividing by 2 gives 65, again odd, and 3n+1 = 196. Some numbers go up for awhile before they reach a direct power of 2.

Oh bah, ninja'd. Posting anyway!

Also s0merand0mdude, if the user doesn't input an integer then your program infinite loops. It's a funny error message, but you may just want to go with a While loop instead.
Last edited by TimeSpaceMage on Fri Mar 05, 2010 7:31 am UTC, edited 1 time in total.

Tychomonger
Posts: 13
Joined: Tue Oct 10, 2006 5:58 pm UTC

Re: "Collatz Conjecture" Discussion

I have to say that I have shown by counter example that the Strong Collatz Conjecture does not hold true. I have charted out happy numbers in bases over 36 (I had to start using greek letters to represent digits) to the point at which all other numbers reduce down to one of the ones I had checked, while trying to stay awake at my job in a call center. I maintained a healthy social life throughout, and my obsession was deemed as cute by some close to me! Nothing was more exciting than finding a new cycle of sad numbers.

tagno25
Posts: 36
Joined: Wed Dec 30, 2009 8:10 am UTC

Re: "Collatz Conjecture" Discussion

This is not code just to display 1450 9s I needed the code tags

Code: Select all

`9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 takes 43439 steps 43439 takes 150 steps150 takes 15 steps15 takes 17 steps17 takes 12 steps12 takes 9 steps9 takes 19 steps19 takes 20 steps20 takes 7 steps7 takes 16 steps16 takes 4 steps4 takes 2 steps2 takes 1 stepand if you start at one it can either take 4 or 0 steps`

randomdragoon
Posts: 1
Joined: Fri Mar 05, 2010 7:28 am UTC

Re: "Collatz Conjecture" Discussion

s0merand0mdude wrote:Oddly enough, my geometry class spent yesterday and today working on calculator programs on the TI-83 and TI-84. Here's a quick program I made after seeing this comic to test the conjecture using a given number.

Code: Select all

`PROGRAM:COLLATZ:Disp "ENTER A NUMBER":Input N:Lbl 3:If N≠int(N):Then:Disp "NOT AN INTEGER":Else:If N=1:Then:Goto 1:Else:If N/2=int(N/2):Then:Disp N/2:N/2→N:Else:Disp 3*N+1:3*N+1→N:End:End:End:Goto 3:Lbl 1:`

I probably didn't need that many "if-then-else" statements, but it was a fun program to write.

You'll want to avoid using Goto in TI basic code, instead using While or For. The reason being that using Goto to break out of a loop causes memory leaks, which can cause bad things to happen. And generally Goto is slower and less safe.

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

Re: "Collatz Conjecture" Discussion

TheShadow wrote:I'll admit, I'm way too stupid to be reading this comic and appreciating its humor. I shouldn't even be posting on these forums, however I have to know what so special about the Collatz Conjecture?

If you multiply any odd number by 3 and add 1 it become even.

If you multiply any even number by 3 and add 1 it become odd.

If you divide any even number by 2, and keep dividing by 2 you will eventually reach 1.

So if you start with an even number you will change it to an odd which you will change back to an even, and then just keep halving it until you reach 1.

If you start with an odd number you will make it even and then keep halving it until you reach 1.

Interesting observation, but unless I'm missing something it doesn't seem to be anything mind-blowing.

well, first, an even number doesn't always get you to 1, so we now know that from an even you can get either an odd or an even, and from an odd you'll always get an even. Now, the catch? the even (m) you get from doing (3n+1) will be larger than 2n, which means that m/2 will be larger than n...as long as you keep getting odds in every (even)/2 you'll keep getting larger and larger number, with no guarantee you'll ever get back to 1...I believe a number exists that will never get to 1, but if that number is "tested", you'll never find out the answer: the test will go on forever.

then there's the possibility you'll get a loop: ((3n+1)/4)=n, would be a loop (this one is the loop 4-2-1-4, which "doesn't count" since the procedure stop when you get to 1)
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.

imatrendytotebag
Posts: 152
Joined: Thu Nov 29, 2007 1:16 am UTC

Re: "Collatz Conjecture" Discussion

Is n -> 5n + 1 when n odd, n -> n/2 when n even an interesting problem? How about n -> kn + 1 when n odd, n -> n/2 when n even, for some odd positive integer k?

Actually, before I submitted this post I spent a little bit of time thinking it over and realized n -> 5n + 1 is not always going to stop: 13 -> 66 -> 33 -> 166 -> 83 -> 416 -> 208 -> 104 -> 52 -> 26 -> 13, which is a cycle.
Hey baby, I'm proving love at nth sight by induction and you're my base case.

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

Re: "Collatz Conjecture" Discussion

phlip wrote:
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.

.

Thank you for that, it was very clearly expressed. And covered what I saw ( using my three brain cells till they squealed ) as the problem, you could never prove it correct, because of an infinity of potential numbers, right?.. So you prove first that there are only three possibilities, then disprove the other two.
Abuse of words has been the great instrument of sophistry and chicanery, of party, faction, and division of society.

s0merand0mdude
Posts: 37
Joined: Fri Dec 04, 2009 6:35 am UTC

Re: "Collatz Conjecture" Discussion

TimeSpaceMage wrote:Also s0merand0mdude, if the user doesn't input an integer then your program infinite loops. It's a funny error message, but you may just want to go with a While loop instead.

We haven't learned about While loops yet... Anyway, I just fixed it by shifting the error message to the bottom of the program and using some goto action.
unus vox wrote:Then again, you're looking for characterization, compelling dialogue, and cohesion in a 3-panel web comic with stick figures.

phillipsjk
Posts: 1213
Joined: Wed Nov 05, 2008 4:09 pm UTC
Contact:

Re: "Collatz Conjecture" Discussion

svat wrote: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. When I read that, I thought: Wouldn't it just be easier to prove? Of course, I was ignoring the part where you have to prove it eventually terminates for all positive integers.

Edit: goto is a JMP or long jump instruction; how can that be slower than a conditional jump?
(I created a memory leak once using GOSUB instead of GOTO in qbasic).
Did you get the number on that truck?

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

Re: "Collatz Conjecture" Discussion

Apteryx wrote:Thank you for that, it was very clearly expressed. And covered what I saw ( using my three brain cells till they squealed ) as the problem, you could never prove it correct, because of an infinity of potential numbers, right?

Not quite - it is possible to prove results for infinitely many numbers using mathematical induction. Suppose you want to prove some result for all natural numbers. Well, you could first show that the result is true for n = 1. Then you could assume the result is true for n = k and use this assumption to prove that the result is true for n = k + 1. Then the proposition being true for 1 implies it is true for 2, which implies it is true for 3, and so on.

This is the proof method that phlip's first paragraph outlines.

Here's an example:
Suppose that you wanted to prove that the number [imath](n^4 + 6n^3 + 11n^2 + 6n)[/imath] is always divisible by [imath]4[/imath], for all [imath]n[/imath].

Well, check that it's true for [imath]n = 1:[/imath]
[imath]1 + 6 + 11 + 6 = 24[/imath], which is divisible by [imath]4[/imath].

Now assume it's true for [imath]n = k[/imath]:
1) [imath]k^4 + 6k^3 + 11k^2 + 6k[/imath] is divisible by [imath]4[/imath].

What can we say about [imath]n = k + 1[/imath]? Well,
2) [imath](k + 1)^4 + 6(k + 1)^3 + 11(k + 1)^2 + 6(k + 1) = k^4 + 10k^3 + 35k^2 + 50k + 24[/imath]

If we subtract the first number from the second number, we get:
[imath](k^4 + 10k^3 + 35k^2 + 50k + 24) - (k^4 + 6k^3 + 11k^2 + 6k) = 4k^3 + 24k^2 + 44k + 24 = 4 * (k^3 + 6k^2 + 11k + 6)[/imath]

Notice that the difference of the two numbers is divisible by [imath]4[/imath], and (by our assumption) the first number was divisible by [imath]4[/imath], which means that the second number must also be divisible by [imath]4[/imath].

Hence we have proven with mathematical induction that [imath]n^4 + 6n^3 + 11n^2 + 6n[/imath] is divisible by 4 for all natural numbers.
Last edited by DT_ on Fri Mar 05, 2010 8:09 am UTC, edited 1 time in total.

pbnjstowell
Posts: 74
Joined: Wed Jul 01, 2009 5:35 am UTC
Location: Middle of Washington, USA

Re: "Collatz Conjecture" Discussion

-.Mateo.- wrote:has anyone here NOT read GEB?

Uh. Skimmed it once. Does that count?
Never trust a dog with orange eyebrows.

funda
Posts: 35
Joined: Wed Jan 28, 2009 10:04 am UTC

Re: "Collatz Conjecture" Discussion

Python in code

GreenStormElf wrote:In python, for your convenience:

Code: Select all

`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.
Poorly updated Blog http://johndasfundas.blogspot.com
Yes, I will clean it up.... later

boring bore
Posts: 270
Joined: Mon Aug 17, 2009 5:23 am UTC
Location: Don't stalk me, it's not worth it

Re: "Collatz Conjecture" Discussion

It's always interesting to me how, when mathematics has advanced so unbelievably far, a problem an elementary schooler (or maybe a middle schooler, depending on their education) could easily grasp is able to be a puzzle for the world's greatest mathematicians. So, as far as I can tell, we're basically trying to find whether there exists an odd number that can be put through (3x+1)/2, or 1.5x+.5, infinitely without becoming a non-natural number. Had I only just seen the problem and committed no thought or research to it, my first thought would be that a mathematician would have no trouble with this; it seems that isn't so! Guys you should totally register for this and join the xkcd team! Rath358 started us off and we're kinda small so the more people who join us, the better for our team and, hopefully, for humanity!

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

Re: "Collatz Conjecture" Discussion

boring bore wrote:So, as far as I can tell, we're basically trying to find whether there exists an odd number that can be put through (3x+1)/2, or 1.5x+.5, infinitely without becoming a non-natural number.

Given any natural number as input, the sequence of numbers produced by the Collatz conjecture for that natural number will always themselves be natural numbers. The question is whether or not the sequence will eventually (i.e. after a finite number of steps) reach 1.

DavidRoss
Posts: 96
Joined: Fri Mar 05, 2010 8:04 am UTC

Re: "Collatz Conjecture" Discussion

DT_ wrote:
eviloatmeal wrote: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?

The function was not made with the goal of reaching 1. It was simply discovered by Collatz who conjectured that it always reached 1.

no, no, no. He was asking a very metaphysical question. There is no reason why the odd numbers need to be multiplied by 3. Of course, then it's not the Collatz Conjecture, it's the "if you divide by two and round up, you will monotonically decrease" Theorem that posits that if you keep decreasing whole positive numbers, you will end up in the 1-2-1-2-1 loop. somebody_else
Posts: 8
Joined: Fri Mar 05, 2010 8:08 am UTC

Re: "Collatz Conjecture" Discussion

What I find interesting is that is doesn't work when you treble the value and subtract 1, as opposed to adding. Just look at 7 for example.