# Collatz's Conjecture

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 06-29-2011
KAUFMANN
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; }```
• 06-29-2011
laserlight
You could use an arbitrary precision math library like GMP.
• 06-29-2011
Matticus
Have you tried "long int" (long integer)? Or, if your compiler supports it, "long long int."

Long integer - Wikipedia, the free encyclopedia
• 06-29-2011
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.
• 06-29-2011
KAUFMANN
Quote:

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
• 06-29-2011
KAUFMANN
Quote:

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?
• 06-29-2011
nonoob
In Microsoft Visual Studio it's called __int64 (64 bit integer).
• 06-29-2011
anduril462
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).
• 06-29-2011
Matticus
^ Yes, what anduril said.
• 06-29-2011
KAUFMANN
Quote:

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).
• 06-29-2011
laserlight
Quote:

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 :)
• 06-29-2011
nonoob
This won't go far...
Code:

`for(i=10000000000;i<=1000000000;i++){`
• 06-29-2011
KAUFMANN
Quote:

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.
• 06-29-2011
KAUFMANN
Quote:

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.
• 06-29-2011
quzah
Quote:

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.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last