Thread: Collatz's Conjecture

*Hi there,

So there is this math conjecture which essentially says you can pick any positive integer, aply two rules and it shall always come to 1. The rules are, if the integer is even, divide it by 2. If it is odd, then multiply it by 3 and add 1. So if you had 5 it'd go: 5-16-8-4-2-1. The conjecture holds to the number 5.

So, I've put together a small code to compute the number of steps necessary to come to 1, given an integer. It works fine but I can't use int variables to really large numbers like 1 000 000 000 000 and larger. I've tried to use floating, but then the condition

Code:

if(iter%2==0)

doesn't work because iter isn't an integer.

What can I do to solve this problem? I have to use floats, right?

Thanks for any help.

Code:

#include<stdio.h>
int main(void){
	float i,cont,iter;
	cont=0;
	for(i=10000000000;i<=1000000000;i++){
		iter=i;
		do{
			if(iter%2==0){
				iter/=2;
				cont++;}
			else{
				iter=iter*3+1;
				cont++;}
		}while(iter!=1);
		printf("Collatz Conjecture - iteration: %f\t\t\tsteps:%f\t\t\t\n",i,cont);
		cont=0;}
	return 0;
}

You could use an arbitrary precision math library like GMP.

Originally Posted by Matticus

Have you tried "long int" (long integer)? Or, if your compiler supports it, "long long int."

Long integer - Wikipedia, the free encyclopedia

So if I want to use this long int, can I simply put 'long' before int followed by the variables or do I need to change anything else? Like the %d

Originally Posted by anduril462

I recommend GMP, and you pretty much need it if you want it to work with arbitrarily large numbers. Otherwise, you can try unsigned long long (or uint64_t), which will get you up to 18,446,744,073,709,551,615. Or you can try switching your floats to long doubles and use fmodl instead of %. That should get you up to 1.189731495357231765085759326628007 × 10^4932, though I haven't given any thought to how floating point inaccuracy might affect your algorithm, so that should be your last resort.

If I want to use the unsigned long long, do I just write 'unsigned long long int var1,var2...'? Or do I need to change the %d as well? And do I need to #include something?

Originally Posted by laserlight

You could use an arbitrary precision math library like GMP.

Hello, I downloaded the gmp-5.0.2.tar.bz2 file from the GMP page but I can't make anything with what I found inside.
How can I use this math library to work with extremely large numbers in my compiler (I'm an Ubuntu user).

Originally Posted by KAUFMANN

Hello, I downloaded the gmp-5.0.2.tar.bz2 file from the GMP page but I can't make anything with what I found inside.
How can I use this math library to work with extremely large numbers in my compiler (I'm an Ubuntu user).

Read the documentation

Originally Posted by laserlight

You could use an arbitrary precision math library like GMP.

Damn! I was afraid you were going to say that... I'll read it then. Thanks anyway.

Originally Posted by nonoob

This won't go far...

Code:

for(i=10000000000;i<=1000000000;i++){

Yes I know. I was changing the range around and didn't see that when I copied the code onto here. But it's irrelevant to the actual issue at hand.

Originally Posted by KAUFMANN

So, I've put together a small code to compute the number of steps necessary to come to 1, given an integer. It works fine but I can't use int variables to really large numbers like 1 000 000 000 000 and larger.

If only there were some way to make big numbers from small numbers.

Code:

for( onetrillion = 0; onetrillion < 1000; onetrillion++ )
    for( onebillion = 0; onebillion< 1000; onebillion++ )
        for( onemillion = 0; onemillion < 1000; onemillion++ )
            for( onethousand = 0; onethousand < 1000; onethousand++ )
            {
                if( onetrillion ) printf( "%d ", onetrillion );
                if( onebillion ) printf( "%d ", onebillion );
                if( onemillion ) printf( "%d ", onemillion );
                printf( "%d\n", onethousand );
            }

Quzah.