0710: "Collatz Conjecture"
Moderators: Moderators General, Prelates, Magistrates
Re: "Collatz Conjecture" Discussion
I actually worked on the Collatz Conjecture for a while. I did a sortof simple way of proving that it will converge to 1 'most of the time'.
First, after a 3n+1 step, it will always be even:
3(2a+1) + 1, where a is a positive integer
6a + 3 + 1
6a + 4
2(3a+2) Even, since the number can be expressed as 2*x.
Once the number is even,
1/2 of all even numbers are divisible by a maximum of 2
1/4 of all even numbers are divisible by a maximum of 4
...
1/2^k of all even numbers are divisible by a maximum of 2^k. k > infinity
So, turning the previous into a probability die,
1/2 chance to roll 2
...
1/2^k chance to roll 2^k, k > infinity
Plotting the probability curve, and then underestimating the curve,
1/2 : 2
1/4 : 4
1/4 : 8
The area under a curve 1 + 1 + 2 = 4. So, on average, 4 is divided out on the n/2 step of the Collatz Conjecture.
(3n+1)/4 = n is only valid for n = 1, so the +1 term can be neglected.
lim( n>inf, (3/4)^n ) = 0, so the Collatz Conjecture will converge most of the time to 1.
The more daunting task, that I have no idea how to go about proving, is showing that it does not loop.
Editted because I forgot an exponent.
First, after a 3n+1 step, it will always be even:
3(2a+1) + 1, where a is a positive integer
6a + 3 + 1
6a + 4
2(3a+2) Even, since the number can be expressed as 2*x.
Once the number is even,
1/2 of all even numbers are divisible by a maximum of 2
1/4 of all even numbers are divisible by a maximum of 4
...
1/2^k of all even numbers are divisible by a maximum of 2^k. k > infinity
So, turning the previous into a probability die,
1/2 chance to roll 2
...
1/2^k chance to roll 2^k, k > infinity
Plotting the probability curve, and then underestimating the curve,
1/2 : 2
1/4 : 4
1/4 : 8
The area under a curve 1 + 1 + 2 = 4. So, on average, 4 is divided out on the n/2 step of the Collatz Conjecture.
(3n+1)/4 = n is only valid for n = 1, so the +1 term can be neglected.
lim( n>inf, (3/4)^n ) = 0, so the Collatz Conjecture will converge most of the time to 1.
The more daunting task, that I have no idea how to go about proving, is showing that it does not loop.
Editted because I forgot an exponent.
Last edited by Gypped on Mon Mar 15, 2010 11:39 pm UTC, edited 1 time in total.
Re: "Collatz Conjecture" Discussion
Nevvy wrote:Would it be possible to prove this statistically? Any odd n will go through (3n+1)/2. Any even n has a 50/50 shot at becoming another even n.
After a certain point the +1 becomes insignificant and you have a 50/50 chance between n*1.5 and n*.5. Since 1.5 * .5 is .75 over a long enough timeline n will reduce to the point where the +1 becomes significant, and at some point in there I become lost.
I think the problem with this is that there are infinite natural numbers, so even if you proved that there is a zero probability, it doesn't prove that there isn't some small group of numbers that don't converge to 1.
Re: "Collatz Conjecture" Discussion
ePaul wrote:And did you run your script for all 32bit numbers?
You can't run it for odd numbers larger than 1/31 of your max integer limit. You may even run into maxint long before that.

 Posts: 45
 Joined: Wed May 30, 2007 3:31 am UTC
 Contact:
Re: "Collatz Conjecture" Discussion
Glanced at some of the sample code ... not counting all the required stuff, this can easily be done in one line.
note that moving the cout into the curly braces would prevent the '1' from printing.
Code: Select all
#include <iostream>
using namespace std;
int main()
{
for(int num=21; (num1); num=(num%2)? (num*3)+1:num/2, cout<<num<<endl){}
return 0;
}
note that moving the cout into the curly braces would prevent the '1' from printing.
Re: "Collatz Conjecture" Discussion
Code: Select all
#include <stdio.h>
int main () {
int N;
printf("Number to start: ");
scanf("%i", &N);
while(N1) {
printf("%i\n", N);
if(N % 2) { N *=3; ++N;}
else { N /= 2;}
}
printf("1\n\n");
return 0;
}
I wrote it immediately after reading the comic
 super_aardvark
 Posts: 54
 Joined: Tue Jan 22, 2008 9:26 am UTC
Re: "Collatz Conjecture" Discussion
VHBT wrote: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.
I'm not sure why you would assume he's wrong three times instead of just once. He didn't say anything about "success" and "obsess" both having an 's' in the middle. He did say, though, that any error in his statement was only a matter of regex knowledge. If you take that assertion for granted, you'll come up with a different correction: /.*s.*ss/.
If he wanted to actually find words like that in a text, of course, he'd need /\w*s\w*ss(\W$)/ (assuming \w denotes the class of word characters and \W its complementI do most of my regex in java). Or maybe something like /\w+(sc[ei]x)\w+ss(\W$)/ which would match any 's' sound in the middle, including "success" and "priceless", which is what you seem to think he meant (and, yeah, maybe he did, but why assume that?).

 Posts: 7
 Joined: Fri Mar 05, 2010 7:29 pm UTC
Re: "Collatz Conjecture" Discussion
Here's a ruby script to do the calculations. Like all good programs, it was written in nano.
The code will print out the number it's testing and then print out the number of times it multiplied before hitting 1. The code will start counting from 1 and go until you stop it (it's not limited to 32 or even 64 bit numbers). The original version of the code would print out all the numbers in the chain from seed > 1, but that was a good bit slower and made it harder to see number you reached. Might run faster if you run it in a disconnected screen session (and only connect to it to see what number you were to).
Something I've found interesting is how slowly the number of times it has to multiply is increasing, and how it never really seems to have any large spikes.
Code: Select all
#!/usr/bin/ruby
Integer seed = 1
Integer curVal = seed
Integer totalMults = 0
while curVal >= 1 do
if curVal == 1
puts " failed. " + totalMults.to_s + " multiplications."
seed = seed + 1
curVal = seed
totalMults = 0
print seed.to_s
end
if curVal % 2 == 0
curVal = curVal / 2
else
curVal = (curVal * 3) + 1
totalMults = totalMults + 1
end
end
put "NUMBER " + seed.to_s + "MOO!"
The code will print out the number it's testing and then print out the number of times it multiplied before hitting 1. The code will start counting from 1 and go until you stop it (it's not limited to 32 or even 64 bit numbers). The original version of the code would print out all the numbers in the chain from seed > 1, but that was a good bit slower and made it harder to see number you reached. Might run faster if you run it in a disconnected screen session (and only connect to it to see what number you were to).
Something I've found interesting is how slowly the number of times it has to multiply is increasing, and how it never really seems to have any large spikes.
Re: "Collatz Conjecture" Discussion
Hey gypped that thing you posted look like what I posted. I feel smart . Is that a sufficient proof that there is no number that will make it grow forever?
I was thinking of it like flipping a coin to infinity, it's going to approach 50/50 on long enough timeline.
Is there a way to prove that if x goes to 1 then x^n goes to 1? Or perhaps that x*n goes to 1?
I can't stop looking at this as probability/statistics.
Would it be equivalent to prove the inverse? That if you stretched the graph to infinity it would have all numbers? That would prove the same. Going up you can always double your number, you can't always subtract 1 divide by 3. Only 1/3rd of the numbers let you branch to a smaller number.
I was thinking of it like flipping a coin to infinity, it's going to approach 50/50 on long enough timeline.
Is there a way to prove that if x goes to 1 then x^n goes to 1? Or perhaps that x*n goes to 1?
KitsuneKnight wrote:Here's a ruby script to do the calculations. Like all good programs, it was written in nano.
Something I've found interesting is how slowly the number of times it has to multiply is increasing, and how it never really seems to have any large spikes.
I can't stop looking at this as probability/statistics.
Would it be equivalent to prove the inverse? That if you stretched the graph to infinity it would have all numbers? That would prove the same. Going up you can always double your number, you can't always subtract 1 divide by 3. Only 1/3rd of the numbers let you branch to a smaller number.
Re: "Collatz Conjecture" Discussion
If I ever obsessively tried to prove the conjecture I would focus on the fact n and 3n + 1 are necessarily relatively prime. Or I would look for some kind of recursive proof.
Last edited by Jirin on Fri Mar 05, 2010 8:10 pm UTC, edited 1 time in total.
Re: "Collatz Conjecture" Discussion
Re: Collatz sequence programs: I'd like to see someone do it in x86 ASM
(I gather it would probably be long, annoying, and really difficult; hardly anyone programs in ASM these days, unless it's really really necessary)
edit: Actually, writing a pixel plotter in C/C++ with the Collatz sequence generator in assembly would probably make a decent fractal generator. (Not gonna try it myself, though...I prolly don't know enough about assembly to actually write anything LOL)
(I gather it would probably be long, annoying, and really difficult; hardly anyone programs in ASM these days, unless it's really really necessary)
edit: Actually, writing a pixel plotter in C/C++ with the Collatz sequence generator in assembly would probably make a decent fractal generator. (Not gonna try it myself, though...I prolly don't know enough about assembly to actually write anything LOL)
Last edited by MrCode on Fri Mar 05, 2010 8:27 pm UTC, edited 1 time in total.

 Posts: 34
 Joined: Mon Feb 22, 2010 5:11 am UTC
Re: "Collatz Conjecture" Discussion
I love how lots of people are writing basically the same program in different languages. And interlaced with those, there is a mathematical discussion about proving it.
I just love it.
maybe adding something like 'if b>9000: print 'ITS OVER NINE THOUSAND' ; break' too lazy to codetag and indent
Inorite?
I just love it.
Spoiler:
TimeSpaceMage wrote:SorryBoringNickName:
Now to keep it from going in infinite loops with 5n+1 and n=5...
maybe adding something like 'if b>9000: print 'ITS OVER NINE THOUSAND' ; break' too lazy to codetag and indent
TimeSpaceMage wrote:Ah dammit, Python is really fun...
Inorite?
Nothing to do, nowhere to gooh

 Posts: 6
 Joined: Fri Mar 05, 2010 8:06 pm UTC
Re: "Collatz Conjecture" Discussion
For the real math nerd. Let's see if the "Expanded Collatz Conjecture" helps or hurts your addiction.
The following is true for all positive integers
For a prime number n, establish a list (l) of all prime numbers < n.
For every positive integer x, if x is divisible by (l) then divide by (l), else, multiply by n and add one.
This will also always lead to 1
sample pseudocode to illustrate:
while t <> 1:
if divmod(t, 2)[1] == 0:
t = t/2
elif divmod(t, 3)[1] == 0:
t = t/3
elif divmod(t,5)[1] == 0:
t = t/5
else:
t = t*7 +1
Have fun this weekend
The following is true for all positive integers
For a prime number n, establish a list (l) of all prime numbers < n.
For every positive integer x, if x is divisible by (l) then divide by (l), else, multiply by n and add one.
This will also always lead to 1
sample pseudocode to illustrate:
while t <> 1:
if divmod(t, 2)[1] == 0:
t = t/2
elif divmod(t, 3)[1] == 0:
t = t/3
elif divmod(t,5)[1] == 0:
t = t/5
else:
t = t*7 +1
Have fun this weekend
Last edited by laxrulz777 on Fri Mar 05, 2010 8:42 pm UTC, edited 1 time in total.

 Posts: 1
 Joined: Fri Mar 05, 2010 8:21 pm UTC
Re: "Collatz Conjecture" Discussion
Here's a really crappy, yet working solution in XSLT. It's only good for the integer data type right now, but that's easily expanded. (The processor i was working with didn't support unsignedInt right now, and I didn't feel like reaching out to java to get it.) It obviously bombs when you start with huge numbers, but it works in theory.
The input document just needs the starting number you want.
The input document just needs the starting number you want.
Code: Select all
<ROOT>
<Number>101512222</Number>
</ROOT>
Code: Select all
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:xs="http://www.w3.org/2001/XMLSchema">
<xsl:stripspace elements="*"/>
<xsl:output method="xml" indent="yes"/>
<xsl:template match="/">
<xsl:applytemplates select="ROOT/Number"/>
</xsl:template>
<xsl:template match="Number">
<xsl:variable name="getResultTree">
<xsl:element name="StartingNumber">
<xsl:valueof select="."/>
</xsl:element>
<xsl:calltemplate name="getNumber">
<xsl:withparam name="currentNumber" select="."/>
</xsl:calltemplate>
</xsl:variable>
<xsl:element name="CollatzSequence">
<xsl:attribute name="Steps" >
<xsl:valueof select="(count($getResultTree/*)  1)" />
</xsl:attribute>
<xsl:copyof select="$getResultTree"/>
</xsl:element>
</xsl:template>
<xsl:template name="getNumber">
<xsl:param name="currentNumber" as="xs:integer"/>
<xsl:variable name="nextNumber" as="xs:integer">
<xsl:choose>
<xsl:when test="($currentNumber mod 2) = 0">
<xsl:valueof select="($currentNumber div 2)"/>
</xsl:when>
<xsl:when test="($currentNumber mod 2) = 1">
<xsl:valueof select="(($currentNumber * 3) + 1)"/>
</xsl:when>
<xsl:when test="($currentNumber = 1)">
<xsl:valueof select="$currentNumber"/>
</xsl:when>
</xsl:choose>
</xsl:variable>
<xsl:choose>
<xsl:when test="($nextNumber = 1)">
<xsl:element name="FinalNumber">
<xsl:valueof select="$nextNumber"/>
</xsl:element>
</xsl:when>
<xsl:otherwise>
<xsl:element name="NextNumber">
<xsl:valueof select="$nextNumber"/>
</xsl:element>
<xsl:calltemplate name="getNumber">
<xsl:withparam name="currentNumber" select="$nextNumber"/>
</xsl:calltemplate>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
</xsl:stylesheet>

 Posts: 6
 Joined: Fri Mar 05, 2010 8:06 pm UTC
Re: "Collatz Conjecture" Discussion
The above works for 7 (using primes 5, 3 and 2) and for 5 (using primes 3 and 2) but fails spectacularly for 11 (using 7, 5, 3 and 2).
Tested through 100000
Now tested through 1,000,000
I feel like the fact that it works for 7 (5,3, 2), 5 (3, 2) and 3 (2) but fails for 11 (7, 5, 3, 2) really should mean something...
Tested through 100000
Now tested through 1,000,000
I feel like the fact that it works for 7 (5,3, 2), 5 (3, 2) and 3 (2) but fails for 11 (7, 5, 3, 2) really should mean something...
Last edited by laxrulz777 on Fri Mar 05, 2010 8:58 pm UTC, edited 1 time in total.
Re: "Collatz Conjecture" Discussion
Here's my first stab at it in PostgreSQL:
It takes a lot of time to run though. My third sequence
has been going for ninety minutes.
Code: Select all
CREATE TABLE collatz (
val BIGINT primary key,
next_val BIGINT
);
CREATE OR REPLACE FUNCTION gen_collatz(BIGINT, BIGINT) RETURNS VOID AS
DECLARE
cnt BIGINT = $1;
x BIGINT;
n BIGINT;
BEGIN
WHILE cnt <= $2 LOOP
x = cnt;
WHILE x <> 1 OR x NOT IN (SELECT val FROM collatz) LOOP
IF x % 2 = 0 THEN
n = x / 2;
ELSE
n = x * 3 + 1;
END IF;
IF x NOT IN (SELECT val FROM collatz) THEN
INSERT INTO collatz (val, next_val) VALUES (x, n);
END IF;
x = n;
END LOOP;
cnt = cnt + 1;
END LOOP;
RETURN;
END
LANGUAGE PLPGSQL VOLATILE;
It takes a lot of time to run though. My third sequence
Code: Select all
collatz=> select gen_collatz(1001,10000);
has been going for ninety minutes.
Re: "Collatz Conjecture" Discussion
One more idea that, sadly, I can't implement myself, as I don't know the language (yet, ): GLSL fragment shader. If someone can write that, then they can certainly make a decent fractal viewer out of it...and lightning fast, too, since it would be run directly on the GPU.
Re: "Collatz Conjecture" Discussion
Nevvy wrote:Hey gypped that thing you posted look like what I posted. I feel smart . Is that a sufficient proof that there is no number that will make it grow forever?
I was thinking of it like flipping a coin to infinity, it's going to approach 50/50 on long enough timeline.
It's not really sufficient to prove that there isn't a blowup. Just that the blowup, if it occurs, has an almost zero probability.
Re: "Collatz Conjecture" Discussion
First post!
I got bored and wrote this up in Java:
Yes, I purposely used doubles.
Hello XKCD forum!
I got bored and wrote this up in Java:
Code: Select all
import java.util.Scanner;
public class comjec {
static Scanner keyboard = new Scanner(System.in);
public static void main(String[] args) {
System.out.print("Enter your whole number here: ");
//Input a freaking whole number
double num=keyboard.nextDouble();
int i=0;
while(num!=1){
if((num%2)==0){
num=num/2;
}else{
num=num*3+1;
}
System.out.println(num);
i++;
}
System.out.println("Number of times run: "+i);
}
}
Yes, I purposely used doubles.
Hello XKCD forum!
Re: "Collatz Conjecture" Discussion
I think I can prove that every number is on a graph of collatz. Maybe. I think that would work.
If all odd numbers are on the graph then all even numbers are, because all even numbers can be written as an odd number o*2^n. (is that last part true/provable? I feel like it is intuitively). Or to state it forwards, every even number reduces to an odd eventually. So now it must be proven that every odd number is on the graph.
This is hard. I can show that 5, 21, 85, and so on must be on the graph (1+2^e where e is an even number). This is done by finding the integer overlaps where 2^n = 3n+1. And of course every even multiple of each of of those numbers must be on the graph. I don't know where to go next though.
Well considering how little calculus I've had (or how little attention I paid, same thing) I feel pretty good about that.
In an infinite set isn't anything with a nonzero probability bound to happen? Shit.
If all odd numbers are on the graph then all even numbers are, because all even numbers can be written as an odd number o*2^n. (is that last part true/provable? I feel like it is intuitively). Or to state it forwards, every even number reduces to an odd eventually. So now it must be proven that every odd number is on the graph.
This is hard. I can show that 5, 21, 85, and so on must be on the graph (1+2^e where e is an even number). This is done by finding the integer overlaps where 2^n = 3n+1. And of course every even multiple of each of of those numbers must be on the graph. I don't know where to go next though.
Gypped wrote:Nevvy wrote:Hey gypped that thing you posted look like what I posted. I feel smart . Is that a sufficient proof that there is no number that will make it grow forever?
I was thinking of it like flipping a coin to infinity, it's going to approach 50/50 on long enough timeline.
It's not really sufficient to prove that there isn't a blowup. Just that the blowup, if it occurs, has an almost zero probability.
Well considering how little calculus I've had (or how little attention I paid, same thing) I feel pretty good about that.
In an infinite set isn't anything with a nonzero probability bound to happen? Shit.
Last edited by Nevvy on Fri Mar 05, 2010 10:35 pm UTC, edited 1 time in total.
Re: "Collatz Conjecture" Discussion
Dunno if this has been brought up yet, but I saw at least one inquisitive reference to fractals while skimming through. Approaching the problem another way can produce some cool visualizations. Taking a list of the first 20000 positive integers and then counting how many steps each one takes to get to 1, then making a simple scatterplot yields: http://picasaweb.google.com/lh/photo/Sz ... directlink
Re: "Collatz Conjecture" Discussion
Okay, after a little bit of thinking of this, I've proven that, with calculable values a and m, you are always 2m steps away from an even number a * 3^m  1.
I think it could be possible to prove based on my line of thinking that there are no loops, but you couldn't necessarily prove there are no infinite upward spirals.
You can use what I've done to predict which numbers will take the longest to get down to 1. (Mostly ones where m is prime or a is divisible by 3.)
I think it could be possible to prove based on my line of thinking that there are no loops, but you couldn't necessarily prove there are no infinite upward spirals.
You can use what I've done to predict which numbers will take the longest to get down to 1. (Mostly ones where m is prime or a is divisible by 3.)

 Posts: 111
 Joined: Tue Feb 24, 2009 7:51 pm UTC
Re: "Collatz Conjecture" Discussion
A few disjoint points to make:
This brings back memories of Nerd Sniping: http://www.xkcd.com/356/
I can't resolve where "ours" is. But I'm in England, and I personally think it would be natural to hear / use either
I wonder how a scattergraph of inputs v. the maximum number they reach or inputs v. number of steps would look for the numbers 0 to 1000
Don't run this with anything important open  it keeps runningo ut of memory and dying Long Live Excel! And it's ****** massive
Interesting cases for maximum value (or implementation bugs):
input 703 with maximum 250504
input 871 with maximum 190996
input 937 with maximum 250504
This brings back memories of Nerd Sniping: http://www.xkcd.com/356/
*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.
I can't resolve where "ours" is. But I'm in England, and I personally think it would be natural to hear / use either
I wonder how a scattergraph of inputs v. the maximum number they reach or inputs v. number of steps would look for the numbers 0 to 1000
Don't run this with anything important open  it keeps runningo ut of memory and dying Long Live Excel! And it's ****** massive
Interesting cases for maximum value (or implementation bugs):
input 703 with maximum 250504
input 871 with maximum 190996
input 937 with maximum 250504
 Attachments

 Collatz.zip
 Sheet 1: Input and each step, maximum value reached
Sheet 2: Number of steps taken
Sheet 3: Graphs
Caveat: not debugged seriously. Consider case when more steps than columns ...  (4.19 MiB) Downloaded 82 times
Re: "Collatz Conjecture" Discussion
Did someone say ASM?
Spoiler:
 meat.paste
 Posts: 404
 Joined: Fri Apr 25, 2008 3:08 pm UTC
Re: "Collatz Conjecture" Discussion
First off, the comic should have said for any natural number (and I think there should be a link to the endless cycle 1  4  2 1 despite what the other entries in this forum say)
Second, here's my crackpot addition to the proof.
1) If n is even, then n_{1} = n/2 and n_{1} < n
2) If n was odd and the resultant was even, then n_{1} = 3n+1 and n_{2} = (3n+1)/2 = 1.5n + 0.5 so n_{2} > n
3) If n was odd and the resultant was odd, then n_{1} = 3n+1 and n_{2} = 3(3n+1)+1 = 9n + 4, so n_{2} > n
So, if n is odd, the n2 will always be larger. The only way for an arbitrary number to reach 1 is to show that any arbitrary number will eventually reach a natural number power of 2.
Is there a way to show this function will always be a power of 2? In other words, can it be shown that n_{i} must eventually be equal to 2^{x}? If we could show that the function can create any natural number, then that should work because eventually, the natural number created must be 2^{x}. There may be something in equating the infinity of natural numbers with the infinity of natural numbers returned by the function in question.
Second, here's my crackpot addition to the proof.
1) If n is even, then n_{1} = n/2 and n_{1} < n
2) If n was odd and the resultant was even, then n_{1} = 3n+1 and n_{2} = (3n+1)/2 = 1.5n + 0.5 so n_{2} > n
3) If n was odd and the resultant was odd, then n_{1} = 3n+1 and n_{2} = 3(3n+1)+1 = 9n + 4, so n_{2} > n
So, if n is odd, the n2 will always be larger. The only way for an arbitrary number to reach 1 is to show that any arbitrary number will eventually reach a natural number power of 2.
Is there a way to show this function will always be a power of 2? In other words, can it be shown that n_{i} must eventually be equal to 2^{x}? If we could show that the function can create any natural number, then that should work because eventually, the natural number created must be 2^{x}. There may be something in equating the infinity of natural numbers with the infinity of natural numbers returned by the function in question.
Huh? What?
Re: "Collatz Conjecture" Discussion
boring bore wrote:I don't think doing (3x+1)/2 infinitely to any natural number will continually result in a natural number. Take any odd number that works for the Collatz conjecture, for example, 11: doing (3x+1)/2 infinitely gives you 11>17>26>14.5, which is not a natural number and will only get worse from there.
11 > 34 > 17 > 52 > 26 > 13 > 40 > 20 > 10 > 5 > 16 > 8 > > 4 > 2 > 1.
The sequence of numbers produced are always natural numbers, because given a natural number n, 3n + 1 is a natural number for all odd n (for all n in general, but in particular for all odd n) and n/2 is a natural number for all even n.
Re: "Collatz Conjecture" Discussion
meat.paste wrote:First off, the comic should have said for any natural number (and I think there should be a link to the endless cycle 1  4  2 1 despite what the other entries in this forum say)
3) If n was odd and the resultant was odd, then n_{1} = 3n+1 and n_{2} = 3(3n+1)+1 = 9n + 4, so n_{2} > n
.
This can't actually happen. The resultant is always even, so step 2 happens, and then we check to see if that resultant is even or odd. So the third iteration is either 2.25n+1 or .75n + .25. And if It's the first one there is guaranteed to be another even and thus another /2. So the here the number of steps before the next check diverges. 1.125n+.5 or .75n+.25, then check even or odd again.
Re: "Collatz Conjecture" Discussion
I felt really odd and geeky because as soon as I read this comic, I wrote a quick Java program to test this.
Then I came here, and now I feel... inferior.
Then I came here, and now I feel... inferior.

 Posts: 1
 Joined: Sat Mar 06, 2010 12:04 am UTC
Re: "Collatz Conjecture" Discussion
I don't really see the magic in that conjecture. 3n+1 of an uneven number gives an even number. Half of that number can be even or uneven, but if it at any point hits a 2^x number it's bound to converge on zero.
There's probably interesting mathematics involved in solving the minute details of why no number subjected to a faceful of Collatz will hit avoid a 2^x number at some point, but.. I'm not really blown away...
There's probably interesting mathematics involved in solving the minute details of why no number subjected to a faceful of Collatz will hit avoid a 2^x number at some point, but.. I'm not really blown away...
Re: "Collatz Conjecture" Discussion
Apocryphite wrote:I don't really see the magic in that conjecture. 3n+1 of an uneven number gives an even number. Half of that number can be even or uneven, but if it at any point hits a 2^x number it's bound to converge on zero.
There's probably interesting mathematics involved in solving the minute details of why no number subjected to a faceful of Collatz will hit avoid a 2^x number at some point, but.. I'm not really blown away...
Yep, the frustrating thing about the Collatz Conjecture is that is seems so *nearly* to yield to simple logic, and in practice has stymied some great mathematical minds over the years. There are people who see how near the logic gets, and shrug about the gap  they couldn't really care less. These people tend to be good at knitting. There are people who see how near the logic gets and who become increasingly frustrated that the logic gap doesn't seem to be easy to close, and who gnaw away at the problem and others like it for some time. These people tend to be good at mathematics.
mooncow
Re: "Collatz Conjecture" Discussion
mooncow wrote:These people tend to be good at mathematics.
...and not have many friends
As the cartoon implies, an unhealthy amount of obsessive hand manipulation would certainly seem to suggest an insufficient number of certain kinds of friends.
mooncow

 Posts: 548
 Joined: Tue Jan 12, 2010 1:04 am UTC
 Contact:
Re: "Collatz Conjecture" Discussion
super_aardvark wrote:VHBT wrote: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.
I'm not sure why you would assume he's wrong three times instead of just once. He didn't say anything about "success" and "obsess" both having an 's' in the middle. He did say, though, that any error in his statement was only a matter of regex knowledge. If you take that assertion for granted, you'll come up with a different correction: /.*s.*ss/.
If he wanted to actually find words like that in a text, of course, he'd need /\w*s\w*ss(\W$)/ (assuming \w denotes the class of word characters and \W its complementI do most of my regex in java). Or maybe something like /\w+(sc[ei]x)\w+ss(\W$)/ which would match any 's' sound in the middle, including "success" and "priceless", which is what you seem to think he meant (and, yeah, maybe he did, but why assume that?).
I meant "A word with one s, possibly preceded with one or more characters, possibly followed by one or more characters, ending with two s's."
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me  __ 
Good fucking job Will Yu, you found me  __ 

 Posts: 548
 Joined: Tue Jan 12, 2010 1:04 am UTC
 Contact:
Re: "Collatz Conjecture" Discussion
laxrulz777 wrote:For the real math nerd. Let's see if the "Expanded Collatz Conjecture" helps or hurts your addiction.
The following is true for all positive integers
For a prime number n, establish a list (l) of all prime numbers < n.
For every positive integer x, if x is divisible by (l) then divide by (l), else, multiply by n and add one.
This will also always lead to 1
sample pseudocode to illustrate:
while t <> 1:
if divmod(t, 2)[1] == 0:
t = t/2
elif divmod(t, 3)[1] == 0:
t = t/3
elif divmod(t,5)[1] == 0:
t = t/5
else:
t = t*7 +1
Have fun this weekend
Are you saying divide by *all* the prime factors in x? Or just the smallest (what you coded)? Or the largest? All would produce different, and probably equally enticing, results.
<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
Did this real quickly in ActionScript 3.0 in Flash, and am running it while I work, so far nothing has stopped it from reaching one, and whenever flash crashes, I update count to the number that cause it to crash.:
var count:Number=378;
var number:Number=count;
var iterations:Number=0;
function CollatzConjecture(e:Event):void{
/***********To Keep me Occupied*********/
square.x=mouseX30;
square.y=mouseY30;
if (number==1){
trace("count is now " + count);
trace("Steps: " + iterations);
number=count;
count++;
number=count;
iterations=0;
}
else{
if(number%2==1){
// trace("odd");
number=number*3+1;
iterations++;
}
else{
// trace("even");
number=number/2;
iterations++;
}
}
}
this.addEventListener(Event.ENTER_FRAME, CollatzConjecture);
var count:Number=378;
var number:Number=count;
var iterations:Number=0;
function CollatzConjecture(e:Event):void{
/***********To Keep me Occupied*********/
square.x=mouseX30;
square.y=mouseY30;
if (number==1){
trace("count is now " + count);
trace("Steps: " + iterations);
number=count;
count++;
number=count;
iterations=0;
}
else{
if(number%2==1){
// trace("odd");
number=number*3+1;
iterations++;
}
else{
// trace("even");
number=number/2;
iterations++;
}
}
}
this.addEventListener(Event.ENTER_FRAME, CollatzConjecture);
Re: "Collatz Conjecture" Discussion
I'm pretty sure there was a lowlevel Project Euler problem involving the Collatz Conjecture that involved searching every thread starting from the numbers one to maybe over a million and logging their lengthto1. It was pretty clear that, for efficiency, you eventually had to store "previously found" numbers in a dictionary/hash along with their found length, and then when you search, say, 295813, and one of the steps was found in your hash, you tacked on the number of steps you already took with the number stored in the hash and then add that into the dictionary.
I can't really find the problem anymore. Does anyone know what I am talking about? It was on http://www.projecteuler.net
I can't really find the problem anymore. Does anyone know what I am talking about? It was on http://www.projecteuler.net
 uncivlengr
 Posts: 1202
 Joined: Fri Nov 14, 2008 10:35 pm UTC
 Location: N 49°19.01 W 123°04.41
Re: "Collatz Conjecture" Discussion
MSTK wrote:I'm pretty sure there was a lowlevel Project Euler problem involving the Collatz Conjecture that involved searching every thread starting from the numbers one to maybe over a million and logging their lengthto1. It was pretty clear that, for efficiency, you eventually had to store "previously found" numbers in a dictionary/hash along with their found length, and then when you search, say, 295813, and one of the steps was found in your hash, you tacked on the number of steps you already took with the number stored in the hash and then add that into the dictionary.
I can't really find the problem anymore. Does anyone know what I am talking about? It was on http://www.projecteuler.net
That was #14
I should really get back into Project Euler... I started programming everything in Excel Visual Basic, because that's what I know, but I should start again to learn a new language.
I was thinking Fortran, only because one of the programs I used in my thesis was written in fortran  does that make sense?
I don't know what to do for you
 neoliminal
 Posts: 626
 Joined: Wed Feb 18, 2009 6:39 pm UTC
Re: "Collatz Conjecture" Discussion
uncivlengr wrote:I was thinking Fortran, only because one of the programs I used in my thesis was written in fortran is that a good choice?
Judging on by your avatar, yes.
http://www.amazon.com/dp/B0073YYXRC
Read My Book. Cost less than coffee. Will probably keep you awake longer.
[hint, scary!]
Read My Book. Cost less than coffee. Will probably keep you awake longer.
[hint, scary!]
Re: "Collatz Conjecture" Discussion
These things sure have a terrible power over us nerds. Heck, I couldn't resist making a function in C to get the number of steps an integer takes myself;
Now I wonder how we could check if the function fails without, you know, just not stopping or overflowing.
Code: Select all
int getCollatz(int param)
{
int steps=0;
while(param>1)
{
if (param%2) param=(param*3)+1;
else param/=2;
steps++;
}
return steps;
}
Now I wonder how we could check if the function fails without, you know, just not stopping or overflowing.
Last edited by DieJay on Sat Mar 06, 2010 3:42 am UTC, edited 1 time in total.
Proud DuctTape Programmer since 2000.
"More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason  including blind stupidity."
W.A. Wulf
"More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason  including blind stupidity."
W.A. Wulf
Re: "Collatz Conjecture" Discussion
I wrote up a code in PHP that shows some interesting statistics on each of the Collatz Conjectures you input; there's also a table feature that will let you view some interesting facts about a sequence of 1000 different trials.
http://quadium32.com/1/xkcdmarch5.php
Looking at it in a table format (and just trying various numbers) has brought up some interesting patterns!
http://quadium32.com/1/xkcdmarch5.php
Looking at it in a table format (and just trying various numbers) has brought up some interesting patterns!
Re: "Collatz Conjecture" Discussion
Well, here's my Python version of the program.
Code: Select all
'''
Created on 20100305
@author: Nomadluap
'''
print 'This is the Collatz Conjecture.'
print 'It will preform the Collatz Conjecture on a given number.'
while True:
numb = int(input('Number?: '))
steps = 0
orignum = numb
while True:
if numb == 1:
print 'Collatz Conjecture complete. '
print 'The number {0} took {1} steps. '.format(orignum, steps)
break
if numb%2 == 0:
numb = numb / 2
steps += 1
print numb
else:
numb = numb * 3 + 1
steps += 1
print numb
I'm thinking in a way...
Spoiler:

 Posts: 548
 Joined: Tue Jan 12, 2010 1:04 am UTC
 Contact:
Re: "Collatz Conjecture" Discussion
That question reminds me of the Busy Beaver problem  how many steps can a Turing machine run for before it stops, if it stops at all? This is asking how many steps the function can "run" for before stopping  and we don't even know if the possibility of stopping exists. To contribute to the discussion of proof, here's something I noticed:
If we remove any initial factors of two, then the function behaves the same as iterating f(n)={if (n%4==1){return (n1)/4}{else return 1.5*n+0.5}}. I think this can provide a very good optimization for running it on a computer, by basically skipping all divisions of two. I'm not sure, though, because the iterations going through the the (n1)/4 might take just as long. Either way, it somewhat interesting. I think maybe one good approach for a proof would be to come up with a simple(ish) formula for the coefficient and addend (in mx+b or something) and then try to show that every number can be written in that form. Maybe something derived from the fact that each number has a unique binary expansion; or at least similar in proof.
If we remove any initial factors of two, then the function behaves the same as iterating f(n)={if (n%4==1){return (n1)/4}{else return 1.5*n+0.5}}. I think this can provide a very good optimization for running it on a computer, by basically skipping all divisions of two. I'm not sure, though, because the iterations going through the the (n1)/4 might take just as long. Either way, it somewhat interesting. I think maybe one good approach for a proof would be to come up with a simple(ish) formula for the coefficient and addend (in mx+b or something) and then try to show that every number can be written in that form. Maybe something derived from the fact that each number has a unique binary expansion; or at least similar in proof.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me  __ 
Good fucking job Will Yu, you found me  __ 
Return to “Individual XKCD Comic Threads”
Who is online
Users browsing this forum: No registered users and 95 guests