Login | Register

Nerd Paradise

a2 = b2 + c2 - 2bc * cos(θ)
The Forum > Math & Science > Collatz Conjecture
Here here and here.
go.

I've heard of it before but I haven't looked into it much.
[Quote] [Link]
Run the following python program to see the collatz conjecture in action:

while (True):
    collatzNum = 0;

    while(True):
        try:
            collatzNum = int(input("Enter an integer greater than 1...\n"));  

            if(collatzNum <= 1):
                print("ERROR: invalid input.");
                continue;
            
            break;
        except (ValueError):
            print("ERROR: invalid input.");
            continue;

    steps = 0;

    while (collatzNum != 1):
        print(str(steps) + ") " + str(collatzNum));

        if(collatzNum % 2 == 0):
            collatzNum = int(collatzNum / 2);
        else:
            collatzNum *= 3;
            collatzNum = int(collatzNum +1);

        steps += 1;

    print(str(steps) + ") 1");

    again = False;

    while(True):
        againStr = input("Would you like to test another number? (y/n)");

        if(againStr == "y" or againStr == "yes"):
            print("Going again...");
            again = True;
            break;
        elif(againStr == "n" or againStr == "no"):
            print("Goodbye.");
            again = False;
            break;
        else:
            print("ERROR: invalid input.");
            continue;

    if (again):
        continue;
    else:
        break;
[Quote] [Link]
^
Traceback (most recent call last):
File "C:/Python27/Collatz Conjecture", line 35, in <module>
againStr = input("Would you like to test another number? (y/n)");
File "<string>", line 1, in <module>
NameError: name 'y' is not defined

EDIT: raw_input fixed that

EDIT: It also crashes when not given an integer ;)
[Quote] [Link]
crashes when not given an integer
*poke*
[Quote] [Link]
raw_input
Doesn't exist in Python 3
C:/Python27/...
Ah, there's the problem.
It also crashes when not given an integer ;)
Bad user! Bad!
[Quote] [Link]
Here's a very fast implementation that starts at 2 and runs until a loop is found.

#include <iostream>
#include <cstring>
#include <gmp.h>
#include <string.h>
#include <alloca.h>
#include <cstdlib>

int main() {
  mpz_t step,num,num_iter;
  mpz_init(step);
  mpz_init(num);
  mpz_init(num_iter);
  mpz_set_ui(step,2);
  for ( ; ; ) {
    mpz_set(num,step);
    while(mpz_cmp(num,step) >= 0){//num > step (we've already evaluated all numbers less than this one.) 
      if(!mpz_divisible_2exp_p(num,1)) {//num%2
        mpz_mul_ui(num,num,3);
        mpz_add_ui(num,num,1);//num=3*num+1
      }
      mpz_divexact_ui(num,num,2);//num/=2
      if(!mpz_cmp(num,step)) {//num==step
        std::cout<<"We have reached a loop, please evalute this number by hand.\n"<<mpz_get_str(NULL,10,step)<< std::endl;
        return(0);
      }
    }
    mpz_add_ui(step,step,1);
    mpz_set_ui(num_iter,0);
    if(mpz_divisible_2exp_p(step,24)) {
      char* str_ptr_step = mpz_get_str(NULL,10,step); //need to save pointers to free later
      std::cerr << "\r" << str_ptr_step;
      free(str_ptr_step);
    }
  }
}
[Quote] [Link]
Well, I have already written a highly optimized program and stuff, by why is it so hard to prove/disprove?
[Quote] [Link]
also, doesn't adding 1 to odd numbers work just as well?
[Quote] [Link]
Well, I have already written a highly optimized program and stuff, by why is it so hard to prove/disprove?


It has to do with the distribution of primes and how the factors of a number chaotically or even randomly change when you add another number to it.

For instance:

165 = 3*5*11
166 = 2*83
167 = prime
168 = 2*2*2*3*7
169 = 13*13

There isn't any simple pattern to prime factorization.

The Collatz conjecture says pretty much that if you triple a number and then add one, then remove all multiples of two from it, that the number of factors will get less and less and the number will condense out all the multiples of two until it leaves one.

Sometimes this process is very short:
11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Sometimes this process is very very long:
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

Here's what the process looks like in binary:
27: 
000000011011
000000101001
000000011111
000000101111
000001000111
000001101011
000010100001
000001111001
000001011011
000010001001
000001100111
000010011011
000011101001
000010101111
000100000111
000110001011
001001010001
000110111101
000010100111
000011111011
000101111001
000100011011
000110101001
000100111111
000111011111
001011001111
010000110111
011001010011
100101111101
001110001111
010101010111
100000000011
110000000101
001001000001
000110110001
000101000101
000000111101
000000010111
000000100011
000000110101
000000000101
000000000001


Which reminds me of a cellular automata.

Also, I'm willing to bet you my implementation is faster. ;) I can verify the first billion integers in about 3 and a half minutes.
[Quote] [Link]
also, doesn't adding 1 to odd numbers work just as well?


It does! But that pattern is way less interesting compared to Collatz.
[Quote] [Link]
Yes, yours is. It's about 6 times faster than mine (although mine was run on a Pentium 4).

I would like to see how you did it.
[Quote] [Link]
I learned this as "Hailstone Numbers", so I'm not sure if this is good, but...


>>> def hailstone(a):
    list=[a]
    while a!=1:
        if a%2==0:
            a=a/2
        else:
            a=a*3+1
        list.append(int(a))
    print(list)
[Quote] [Link]
The Forum > Math & Science > Collatz Conjecture
Current Date: 13 Ineo 10:0Current Time: 12.60.46Join us in IRC...
Server: irc.esper.net
Channel: #nerdparadise
Your IP: 23.22.212.158Browser: UnknownBrowser Version: 0