Results 1 to 6 of 6
  1. #1
    tbrowne03 is offline Member
    Join Date
    Nov 2011
    Posts
    5
    Rep Power
    0

    Default Disproof to a conjecture or a programming error?

    Hi!
    So I am very new to java, and I have recently been reading about variables and operators. (very basic stuff)
    However, I wanted to write a program that challenged my very limited skill so far, and I decided to write a program to test the Collatz conjecture.
    (Basically it is a series of equations. You take any positive integer and, if its even, divide by 2. If its not, multiply by 3 and add 1. The conjecture states that if you do this enough times it will always eventually equal 1.)
    The problem is that I have heard that this conjecture is true, and yet I keep getting one number that proves the conjecture false. It is 113383.
    Please help me identify if this is just a programming error (which I'm pretty sure it is).
    (Also if its possible could you guys help me improve my programming style so it's easier to read! thanks!)
    Here is the code:
    Java Code:
    class CollatzConjecture
    {
     public static void main (String[] args)
     {
      int variable = 1;
      int variable2 = 0;
      while (variable > 0){
       while (variable >= 2){
       
       if (variable % 2 == 1){
        variable *= 3;
        variable += 1;
        }
       else{
        variable /= 2;}
      }
     if (variable == 1){ System.out.println("True");
         } 
         else {
    System.out.println("False");
    System.exit(0); 
    }
     ++variable2;
    variable += variable2;
    System.out.println(variable2);
    
      }
     }
    }
    Last edited by pbrockway2; 11-26-2011 at 06:04 AM. Reason: code tags added

  2. #2
    tbrowne03 is offline Member
    Join Date
    Nov 2011
    Posts
    5
    Rep Power
    0

    Default Re: Disproof to a conjecture or a programming error?

    Oh and yes I know that this will loop forever I sorta wanted it that way :D
    and just to clarify "variable" is the number that the program checks, and "variable2" simply increases "variable" so that the program keeps checking bigger and bigger numbers

  3. #3
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,585
    Rep Power
    12

    Default Re: Disproof to a conjecture or a programming error?

    Hi tbrowne03, welcome to the forum.

    I have added "code" tags to your post. Basically you put [code] to the start of your code and [/code] at the end to ensure that the code is readable when it appears here.

    You ask about style and readability... I might have gone for a more straight forward way of increasing the number being test, but let that pass. Just getting indentation consistent (and of a reasonable size) would be a good start. Here's how I might have written your code:

    Java Code:
    class CollatzConjecture {
        public static void main(String[] args) {
            int variable = 1;
            int variable2 = 0;
            while(variable > 0) {
                System.out.println("testing " + variable);
                while(variable >= 2) {
                    if(variable % 2 == 1) {
                        variable *= 3;
                        variable += 1;
                    } else {
                        variable /= 2;
                    }
                    System.out.println("    " + variable);
                }
                if(variable == 1) {
                    System.out.println("True");
                } else {
                    System.out.println("False");
                    System.exit(0);
                }
                ++variable2;
                variable += variable2;
                System.out.println(variable2);
            }
        }
    }
    As you can see I've added a couple of lines. That's to see what is going on. The program takes somewhat longer to run this way but you (eventually) find something rather interesting.

    (Do think and/or look at a textbook, online tutorial or whatever before posting back "why's that?". But, if all else fails, do post back with "why's that?")

  4. #4
    tbrowne03 is offline Member
    Join Date
    Nov 2011
    Posts
    5
    Rep Power
    0

    Default Re: Disproof to a conjecture or a programming error?

    Thank you so much for the helpful tips! From now on I will most certainly use "code" and "/code"! And I believe that I have solved my problem! The last digit that the program uses before it crashes (thanks to your edit of the code which show the steps) is around 800 million, and its odd. I suppose that this means that when you multiply it by 3, it exceeds the 2 billion cap that "int" allows for! Thank you so much again for all your help!
    I would, however, love to know how you got it to show all the steps. I assume that is in the line System.out.println(" " + variable); but I don't quite see how that would make that change. Also, i am using notepad right now, and so I don't have the best ability to indent nicely and keep my code organized. What do you use to code java? I've heard that Eclipse is alright but I am still new and would love any extra opinions I can get!
    Thanks again!

  5. #5
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,585
    Rep Power
    12

    Default Re: Disproof to a conjecture or a programming error?

    it exceeds the 2 billion cap that "int" allows for!
    Well done! You can use long rather than int to give yourself some more digits, and Java also has a BigInteger class where your computer's memory is the only limit. (On the other hand this conjecture has already been tested out to 20*2^58 (according to Wikipedia) so the important thing is more your program rather than the (already known) result. You could actually test for that bogus negative (it's called overflow) after the inner while loop and report "Unknown" or something. Note in that case "variable += variable2;" won't be any good as the variable increment.

    I would, however, love to know how you got it to show all the steps.
    Both System.out.println() statements are involved. This is a handy method because it will print whatever you throw at it. Here is the code annotated a little:

    Java Code:
    while(variable > 0) {
            /*
             * Begin the loop by displaying a message saying what number is
             * being tested.  This will occur one time for each time around
             * the outer loop.
             */
        System.out.println("testing " + variable);
        while(variable >= 2) {
            if(variable % 2 == 1) {
                variable *= 3;
                variable += 1;
            } else {
                variable /= 2;
            }
                /*
                 * For each change we make to variable print the new value so we can see
                 * what it's changed to.  We may go round this inner loop many times
                 * producing a new message each time.  This message is indented a little
                 * by putting "    " at the start to show that it is coming from this inner loop.
                 */
            System.out.println("    " + variable);
        }
        // report result
        // increment variable
    }
    I use Eclipse - it is free and straight forward to install and use (I think). It will also encourage some good habits like "always have the javadoc available" and "correct syntax errors as soon as you can". That said it is *not* a reason to avoid learning how to compile/run/jar from the command line. From the command you get to set all the various options (and hence are forced to find out what they are and what they mean), in Eclipse those same options are hidden away in dialogs. It is also a Big Temptation for some and I would strongly urge you *not* to let an IDE write code for you. If you see "do not edit below this line" then turn off features or use a different IDE: it's your code and you should edit any d@mn line you want. With power comes responsibility and you will have to know what you're doing... But that's the whole point! Don't let an IDE rob you of the opportunity to learn.

    (Could say much the same for Netbeans where the Bright Lights of drag and drop gui building are, sadly, even more alluring. If you are after all sorts of bells and whistles, NB tends to be more easily installable and useable. Or at least that's been my experience: Eclipse tends to send you all over teh internet looking for addon packages.)

    On Windows I also use Textpad, and on Linux, Kate. Both are plain text editors, but both will also syntax colour.

    Thanks again!
    You're welcome.
    Last edited by pbrockway2; 11-26-2011 at 08:20 AM.

  6. #6
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,585
    Rep Power
    12

    Default Re: Disproof to a conjecture or a programming error?

    I misspoke before. Because you multiply by three it is quite possible that a *really* big number will wrap around twice and end up positive. So you can't really check for negative values and report them as "unknown".

    Not a big deal, but I thought I would get in and correct this before Jos comes on line...

    Anyway, and since I'm posting, here's what a BigInteger version might look like:

    Java Code:
    import java.math.BigInteger;
    
    class CollatzConjecture {
    	
        static final BigInteger THREE = new BigInteger("3");
    	
        public static void main(String[] args) {
        	BigInteger toTest = new BigInteger("12");
        	    // 12,6,3,10,5,16,8,4,2,1 should be 9 steps
        	System.out.println(toTest + " reaches 1 after " + check(toTest) + " steps");
        	
                // big base 16 number
        	toTest = new BigInteger("CAFEBABE0000DEADBEEF00001337", 16); 
        	System.out.println(toTest + " reaches 1 after " + check(toTest) + " steps");
        	
                // *really* big number
        	toTest = new BigInteger("1337").pow(1337); 
        	System.out.println(toTest + " reaches 1 after " + check(toTest) + " steps");
        }
        
            /** Returns the length of the "hailstone" sequence for a given value. */
        static int check(BigInteger val) {
        	int ret = 0;
            while(true) {
                //System.out.println(val);
                if(val.equals(BigInteger.ONE)) {
                    return ret;
                }
                if(!val.testBit(0)) { // ie if val is even
                    val = val.shiftRight(1);
                } else {
                    val = val.multiply(THREE).add(BigInteger.ONE);
                }
                ret++;
            }
        }
    }
    It's interesting how even insanely large numbers collapse quite quickly. Or at least 1337^1337 does in just 100K steps.

Similar Threads

  1. Socket Programming ERROR : Socket not connected
    By vishrut_n_shah in forum Networking
    Replies: 0
    Last Post: 11-04-2011, 10:32 AM
  2. Socket applet programming error?
    By Master Zero in forum Java Applets
    Replies: 6
    Last Post: 10-05-2011, 10:15 PM
  3. programming help!!??
    By lestweremember in forum New To Java
    Replies: 8
    Last Post: 04-13-2011, 02:09 AM
  4. GPS programming.
    By santa in forum New To Java
    Replies: 7
    Last Post: 02-06-2011, 11:21 AM
  5. programming
    By abcdefg in forum New To Java
    Replies: 9
    Last Post: 03-10-2008, 11:34 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •