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.

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

Long integer - Wikipedia, the free encyclopedia

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.

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?

In Microsoft Visual Studio it's called __int64 (64 bit integer).

You technically only need "unsigned long long", but the extra "int" shouldn't hurt. And yes, that's how you declare it. Of course, your compiler must support that type (it probably does if it's not Turbo C or Dev-C++). Pelles C and GCC (and MinGW) support the standard uint64_t. If you're using Visual Studio, version 2010 has stdint.h, which allows uint64_t, but if you have an older version, you will have to use __int64 as nonoob suggested (and you should upgrate to VS2010 Express if possible).

As for the format specifier, you will need to change it. printf uses the %d to pick the size of the next parameter, so giving the wrong format specifier gives the wrong output. Probably "%ull" for unsigned long long, or "%dll" for signed long long (__int64).

^ Yes, what anduril said.

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

This won't go far...

Code:

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

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.