0710: "Collatz Conjecture"

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

Moderators: Moderators General, Prelates, Magistrates

Gypped
Posts: 42
Joined: Tue Nov 17, 2009 6:12 am UTC

Re: "Collatz Conjecture" Discussion

Postby Gypped » Fri Mar 05, 2010 4:27 pm UTC

I actually worked on the Collatz Conjecture for a while. I did a sort-of 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.
Last edited by Gypped on Mon Mar 15, 2010 11:39 pm UTC, edited 1 time in total.

pscottdv
Posts: 67
Joined: Fri Feb 19, 2010 4:32 pm UTC

Re: "Collatz Conjecture" Discussion

Postby pscottdv » Fri Mar 05, 2010 4:44 pm UTC

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.

leifbk
Posts: 33
Joined: Wed Nov 26, 2008 7:24 am UTC
Location: Bærum, Norway
Contact:

Re: "Collatz Conjecture" Discussion

Postby leifbk » Fri Mar 05, 2010 5:09 pm UTC

ePaul wrote:And did you run your script for all 32-bit numbers?


You can't run it for odd numbers larger than 1/3-1 of your max integer limit. You may even run into maxint long before that.

UltramaticOrange
Posts: 45
Joined: Wed May 30, 2007 3:31 am UTC
Contact:

Re: "Collatz Conjecture" Discussion

Postby UltramaticOrange » Fri Mar 05, 2010 5:36 pm UTC

Glanced at some of the sample code ... not counting all the required stuff, this can easily be done in one line.

Code: Select all

#include <iostream>
using namespace std;

int main()
 {
        for(int num=21; (num-1); 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.
Image

JH999
Posts: 3
Joined: Sat Jan 30, 2010 4:07 pm UTC

Re: "Collatz Conjecture" Discussion

Postby JH999 » Fri Mar 05, 2010 7:39 pm UTC

Code: Select all

#include <stdio.h>

int main () {
   int N;
    printf("Number to start: ");
   scanf("%i", &N);
   while(N-1) {
      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

User avatar
super_aardvark
Posts: 54
Joined: Tue Jan 22, 2008 9:26 am UTC

Re: "Collatz Conjecture" Discussion

Postby super_aardvark » Fri Mar 05, 2010 7:40 pm UTC

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 complement--I do most of my regex in java). Or maybe something like /\w+(s|c[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?).

KitsuneKnight
Posts: 7
Joined: Fri Mar 05, 2010 7:29 pm UTC

Re: "Collatz Conjecture" Discussion

Postby KitsuneKnight » Fri Mar 05, 2010 7:41 pm UTC

Here's a ruby script to do the calculations. Like all good programs, it was written in nano. :twisted:

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.

Nevvy
Posts: 7
Joined: Fri Mar 05, 2010 8:18 am UTC

Re: "Collatz Conjecture" Discussion

Postby Nevvy » Fri Mar 05, 2010 7:48 pm UTC

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?

KitsuneKnight wrote:Here's a ruby script to do the calculations. Like all good programs, it was written in nano. :twisted:

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.

Jirin
Posts: 32
Joined: Wed Sep 03, 2008 10:18 pm UTC

Re: "Collatz Conjecture" Discussion

Postby Jirin » Fri Mar 05, 2010 8:06 pm UTC

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.

MrCode
Posts: 27
Joined: Fri Mar 05, 2010 9:05 am UTC

Re: "Collatz Conjecture" Discussion

Postby MrCode » Fri Mar 05, 2010 8:08 pm UTC

Re: Collatz sequence programs: I'd like to see someone do it in x86 ASM :twisted:

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

SorryBoringNickName
Posts: 34
Joined: Mon Feb 22, 2010 5:11 am UTC

Re: "Collatz Conjecture" Discussion

Postby SorryBoringNickName » Fri Mar 05, 2010 8:16 pm UTC

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.

Spoiler:
The only thing I'm missing is someone writing code optimized for CUDA. IDK why CUDA, it just sounds freaky enough. No wait-- Assembly wins this round.


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 go-oh

laxrulz777
Posts: 6
Joined: Fri Mar 05, 2010 8:06 pm UTC

Re: "Collatz Conjecture" Discussion

Postby laxrulz777 » Fri Mar 05, 2010 8:22 pm UTC

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

iceandrews
Posts: 1
Joined: Fri Mar 05, 2010 8:21 pm UTC

Re: "Collatz Conjecture" Discussion

Postby iceandrews » Fri Mar 05, 2010 8:27 pm UTC

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.

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:strip-space elements="*"/>
   <xsl:output method="xml" indent="yes"/>

   <xsl:template match="/">
      <xsl:apply-templates select="ROOT/Number"/>
   </xsl:template>

   <xsl:template match="Number">
      <xsl:variable name="getResultTree">
         <xsl:element name="StartingNumber">
            <xsl:value-of select="."/>
         </xsl:element>
         <xsl:call-template name="getNumber">
            <xsl:with-param name="currentNumber" select="."/>
         </xsl:call-template>
      </xsl:variable>
      <xsl:element name="CollatzSequence">
         <xsl:attribute name="Steps" >
            <xsl:value-of select="(count($getResultTree/*) - 1)" />
         </xsl:attribute>
         <xsl:copy-of 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:value-of select="($currentNumber div 2)"/>
            </xsl:when>
            <xsl:when test="($currentNumber mod 2) = 1">
               <xsl:value-of select="(($currentNumber * 3) + 1)"/>
            </xsl:when>
            <xsl:when test="($currentNumber = 1)">
               <xsl:value-of select="$currentNumber"/>
            </xsl:when>
         </xsl:choose>
      </xsl:variable>
      <xsl:choose>
         <xsl:when test="($nextNumber = 1)">
            <xsl:element name="FinalNumber">
               <xsl:value-of select="$nextNumber"/>
            </xsl:element>
         </xsl:when>
         <xsl:otherwise>
            <xsl:element name="NextNumber">
               <xsl:value-of select="$nextNumber"/>
            </xsl:element>
            <xsl:call-template name="getNumber">
               <xsl:with-param name="currentNumber" select="$nextNumber"/>
            </xsl:call-template>
         </xsl:otherwise>
      </xsl:choose>
   </xsl:template>
</xsl:stylesheet>

laxrulz777
Posts: 6
Joined: Fri Mar 05, 2010 8:06 pm UTC

Re: "Collatz Conjecture" Discussion

Postby laxrulz777 » Fri Mar 05, 2010 8:31 pm UTC

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...
Last edited by laxrulz777 on Fri Mar 05, 2010 8:58 pm UTC, edited 1 time in total.

leifbk
Posts: 33
Joined: Wed Nov 26, 2008 7:24 am UTC
Location: Bærum, Norway
Contact:

Re: "Collatz Conjecture" Discussion

Postby leifbk » Fri Mar 05, 2010 8:34 pm UTC

Here's my first stab at it in PostgreSQL:

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.

MrCode
Posts: 27
Joined: Fri Mar 05, 2010 9:05 am UTC

Re: "Collatz Conjecture" Discussion

Postby MrCode » Fri Mar 05, 2010 8:56 pm UTC

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.

Gypped
Posts: 42
Joined: Tue Nov 17, 2009 6:12 am UTC

Re: "Collatz Conjecture" Discussion

Postby Gypped » Fri Mar 05, 2010 9:46 pm UTC

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 blow-up. Just that the blow-up, if it occurs, has an almost zero probability.

cookrw
Posts: 8
Joined: Fri Mar 05, 2010 9:42 pm UTC

Re: "Collatz Conjecture" Discussion

Postby cookrw » Fri Mar 05, 2010 9:48 pm UTC

First post!

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!

Nevvy
Posts: 7
Joined: Fri Mar 05, 2010 8:18 am UTC

Re: "Collatz Conjecture" Discussion

Postby Nevvy » Fri Mar 05, 2010 10:30 pm UTC

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.

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 blow-up. Just that the blow-up, 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 non-zero probability bound to happen? Shit.
Last edited by Nevvy on Fri Mar 05, 2010 10:35 pm UTC, edited 1 time in total.

mjkelly42
Posts: 1
Joined: Fri Mar 05, 2010 10:26 pm UTC

Re: "Collatz Conjecture" Discussion

Postby mjkelly42 » Fri Mar 05, 2010 10:33 pm UTC

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

Jirin
Posts: 32
Joined: Wed Sep 03, 2008 10:18 pm UTC

Re: "Collatz Conjecture" Discussion

Postby Jirin » Fri Mar 05, 2010 10:53 pm UTC

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

andy33gmail
Posts: 111
Joined: Tue Feb 24, 2009 7:51 pm UTC

Re: "Collatz Conjecture" Discussion

Postby andy33gmail » Fri Mar 05, 2010 10:58 pm UTC

A few disjoint points to make:

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

User avatar
Dropzone
Posts: 405
Joined: Sun Dec 30, 2007 10:12 pm UTC
Location: North Lincs., UK

Re: "Collatz Conjecture" Discussion

Postby Dropzone » Fri Mar 05, 2010 11:01 pm UTC

Did someone say ASM?
Spoiler:

Code: Select all

extern _printf, _scanf

section .rdata

prompt: db `Enter a positive integer: \0`
inFormat: db `%u\0`
outFormat: db `%u\n\0`
stepsFormat: db `Reached 1 in %u steps\n\0`

section .text

global _main
_main:
        pushad

        push    prompt
        call    _printf
        push    esp
        push    inFormat
        call    _scanf
        add     esp, 8
        pop     ebx

        xor     esi, esi

.loop:
        push    ebx
        push    outFormat
        call    _printf
        add     esp, 8

        cmp     ebx, 1
        je      .done

        inc     esi

        test    ebx, 1
        jnz     .odd

        shr     ebx, 1
        jmp     .loop

.odd:
        lea     ebx, [3*ebx + 1]
        jmp     .loop

.done:
        push    esi
        push    stepsFormat
        call    _printf
        add     esp, 8

        popad
        ret

User avatar
meat.paste
Posts: 404
Joined: Fri Apr 25, 2008 3:08 pm UTC

Re: "Collatz Conjecture" Discussion

Postby meat.paste » Fri Mar 05, 2010 11:03 pm UTC

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 n1 = n/2 and n1 < n
2) If n was odd and the resultant was even, then n1 = 3n+1 and n2 = (3n+1)/2 = 1.5n + 0.5 so n2 > n
3) If n was odd and the resultant was odd, then n1 = 3n+1 and n2 = 3(3n+1)+1 = 9n + 4, so n2 > 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 ni must eventually be equal to 2x? If we could show that the function can create any natural number, then that should work because eventually, the natural number created must be 2x. 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?

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

Re: "Collatz Conjecture" Discussion

Postby DT_ » Fri Mar 05, 2010 11:07 pm UTC

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.

Nevvy
Posts: 7
Joined: Fri Mar 05, 2010 8:18 am UTC

Re: "Collatz Conjecture" Discussion

Postby Nevvy » Fri Mar 05, 2010 11:40 pm UTC

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 n1 = 3n+1 and n2 = 3(3n+1)+1 = 9n + 4, so n2 > 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.

Arvedui
Posts: 9
Joined: Fri Dec 25, 2009 7:47 am UTC

Re: "Collatz Conjecture" Discussion

Postby Arvedui » Fri Mar 05, 2010 11:56 pm UTC

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.

Apocryphite
Posts: 1
Joined: Sat Mar 06, 2010 12:04 am UTC

Re: "Collatz Conjecture" Discussion

Postby Apocryphite » Sat Mar 06, 2010 12:09 am UTC

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

mooncow
Posts: 48
Joined: Fri Jan 15, 2010 2:12 pm UTC

Re: "Collatz Conjecture" Discussion

Postby mooncow » Sat Mar 06, 2010 12:47 am UTC

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

mooncow
Posts: 48
Joined: Fri Jan 15, 2010 2:12 pm UTC

Re: "Collatz Conjecture" Discussion

Postby mooncow » Sat Mar 06, 2010 12:48 am UTC

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

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

Re: "Collatz Conjecture" Discussion

Postby squareroot » Sat Mar 06, 2010 12:55 am UTC

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 complement--I do most of my regex in java). Or maybe something like /\w+(s|c[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 - __ -

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

Re: "Collatz Conjecture" Discussion

Postby squareroot » Sat Mar 06, 2010 1:02 am UTC

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 pseudo-code 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 - __ -

alemfi
Posts: 2
Joined: Sat Mar 06, 2010 12:13 am UTC

Re: "Collatz Conjecture" Discussion

Postby alemfi » Sat Mar 06, 2010 1:15 am UTC

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=mouseX-30;
square.y=mouseY-30;

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

MSTK
Posts: 123
Joined: Fri Oct 31, 2008 5:43 am UTC

Re: "Collatz Conjecture" Discussion

Postby MSTK » Sat Mar 06, 2010 1:30 am UTC

I'm pretty sure there was a low-level 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 length-to-1. 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

User avatar
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

Postby uncivlengr » Sat Mar 06, 2010 1:50 am UTC

MSTK wrote:I'm pretty sure there was a low-level 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 length-to-1. 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

User avatar
neoliminal
Posts: 626
Joined: Wed Feb 18, 2009 6:39 pm UTC

Re: "Collatz Conjecture" Discussion

Postby neoliminal » Sat Mar 06, 2010 2:10 am UTC

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

User avatar
DieJay
Posts: 93
Joined: Tue Jun 30, 2009 4:45 pm UTC
Location: here be dragons
Contact:

Re: "Collatz Conjecture" Discussion

Postby DieJay » Sat Mar 06, 2010 2:28 am UTC

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;

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 Duct-Tape 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

quadium32
Posts: 1
Joined: Sat Mar 06, 2010 3:07 am UTC

Re: "Collatz Conjecture" Discussion

Postby quadium32 » Sat Mar 06, 2010 3:10 am UTC

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/xkcd-march5.php

Looking at it in a table format (and just trying various numbers) has brought up some interesting patterns!

User avatar
nomadluap
Posts: 10
Joined: Wed Jan 06, 2010 11:22 pm UTC

Re: "Collatz Conjecture" Discussion

Postby nomadluap » Sat Mar 06, 2010 3:11 am UTC

Well, here's my Python version of the program.

Code: Select all

'''
Created on 2010-03-05

@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:
that isn't usually how I think.

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

Re: "Collatz Conjecture" Discussion

Postby squareroot » Sat Mar 06, 2010 4:07 am UTC

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 (n-1)/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 (n-1)/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 - __ -


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: No registered users and 95 guests