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

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

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

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

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.

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

### Re: "Collatz Conjecture" Discussion

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

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

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

Code: Select all

`#!/usr/bin/rubyInteger seed = 1Integer curVal = seedInteger totalMults = 0while 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        endendput "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

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.

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

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

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

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

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

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

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

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 ASDECLARE    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;ENDLANGUAGE 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

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

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

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

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

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

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

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

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

### Re: "Collatz Conjecture" Discussion

Did someone say ASM?
Spoiler:

Code: Select all

`extern _printf, _scanfsection .rdataprompt: 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 .textglobal _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`

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

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

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

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

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

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

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

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

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

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++;
}
}
}

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

### Re: "Collatz Conjecture" Discussion

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

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

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

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

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

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

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

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

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

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

### Re: "Collatz Conjecture" Discussion

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

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