Like Tree1Likes

Collatz's Conjecture

This is a discussion on Collatz's Conjecture within the C Programming forums, part of the General Programming Boards category; *Hi there, So there is this math conjecture which essentially says you can pick any positive integer, aply two rules ...

  1. #1
    Registered User KAUFMANN's Avatar
    Join Date
    Jan 2011
    Location
    Coimbra, Portugal
    Posts
    31

    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;
    }
    ˙uıɐƃɐ ʎɐq-ǝ ɯoɹɟ pɹoqʎǝʞ ɹǝɥʇouɐ ƃuıʎnq ʇou ɯı

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,712
    You could use an arbitrary precision math library like GMP.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jun 2011
    Posts
    2,332
    Have you tried "long int" (long integer)? Or, if your compiler supports it, "long long int."

    Long integer - Wikipedia, the free encyclopedia

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,481
    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.

  5. #5
    Registered User KAUFMANN's Avatar
    Join Date
    Jan 2011
    Location
    Coimbra, Portugal
    Posts
    31
    Quote Originally Posted by Matticus View Post
    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
    ˙uıɐƃɐ ʎɐq-ǝ ɯoɹɟ pɹoqʎǝʞ ɹǝɥʇouɐ ƃuıʎnq ʇou ɯı

  6. #6
    Registered User KAUFMANN's Avatar
    Join Date
    Jan 2011
    Location
    Coimbra, Portugal
    Posts
    31
    Quote Originally Posted by anduril462 View Post
    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?
    ˙uıɐƃɐ ʎɐq-ǝ ɯoɹɟ pɹoqʎǝʞ ɹǝɥʇouɐ ƃuıʎnq ʇou ɯı

  7. #7
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    In Microsoft Visual Studio it's called __int64 (64 bit integer).

  8. #8
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,481
    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).

  9. #9
    Registered User
    Join Date
    Jun 2011
    Posts
    2,332
    ^ Yes, what anduril said.

  10. #10
    Registered User KAUFMANN's Avatar
    Join Date
    Jan 2011
    Location
    Coimbra, Portugal
    Posts
    31
    Quote Originally Posted by laserlight View Post
    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).
    ˙uıɐƃɐ ʎɐq-ǝ ɯoɹɟ pɹoqʎǝʞ ɹǝɥʇouɐ ƃuıʎnq ʇou ɯı

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,712
    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
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    This won't go far...
    Code:
    for(i=10000000000;i<=1000000000;i++){

  13. #13
    Registered User KAUFMANN's Avatar
    Join Date
    Jan 2011
    Location
    Coimbra, Portugal
    Posts
    31
    Quote Originally Posted by laserlight View Post
    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.
    ˙uıɐƃɐ ʎɐq-ǝ ɯoɹɟ pɹoqʎǝʞ ɹǝɥʇouɐ ƃuıʎnq ʇou ɯı

  14. #14
    Registered User KAUFMANN's Avatar
    Join Date
    Jan 2011
    Location
    Coimbra, Portugal
    Posts
    31
    Quote Originally Posted by nonoob View Post
    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.
    ˙uıɐƃɐ ʎɐq-ǝ ɯoɹɟ pɹoqʎǝʞ ɹǝɥʇouɐ ƃuıʎnq ʇou ɯı

  15. #15
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by KAUFMANN View Post
    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.
    Adak likes this.
    Hope is the first step on the road to disappointment.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Collatz Conjecture
    By eebank in forum C Programming
    Replies: 1
    Last Post: 10-27-2010, 08:51 PM
  2. Goldbach's Conjecture
    By cashmerelc in forum C Programming
    Replies: 7
    Last Post: 07-19-2010, 10:41 PM
  3. Help With Collatz Conjecture
    By Dougal in forum C Programming
    Replies: 3
    Last Post: 10-20-2009, 10:01 PM
  4. Godbach conjecture!!
    By Leojeen in forum C Programming
    Replies: 10
    Last Post: 04-20-2008, 06:42 PM
  5. Goldbach Conjecture
    By StarOrbs in forum C++ Programming
    Replies: 19
    Last Post: 03-17-2005, 03:42 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21