Euler's project number 14

I have the following problem (from ProjectEuler.net - Issue 14 )

The following iteration sequence is defined for a set of natural numbers:

n -> n/2 (n is even)
n -> 3n + 1 (n is odd)

      

Using the rule above and starting at 13, we create the following sequence:

13 β†’ 40 β†’ 20 β†’ 10 β†’ 5 β†’ 16 β†’ 8 β†’ 4 β†’ 2 β†’ 1

      

You can see that this sequence (starting with 13

and ending with 1

) contains 10 members. While this has not yet been proven (Collatz problem), all seeds are believed to end in 1

.

Which seed less than a million produces the longest chain?

NOTE. Once the chain begins, terms are allowed to exceed one million.

I used:

   static int road (int n)
   {
       int road = 0;
       while (n != 1)
       {
           if (n % 2 == 0)
               n = n / 2;
           else
               n = 3 * n + 1;
           road++;
       }
       return road;
   }
   static void Main(string[] args)
   {
       int max = 0, num = 0;
       for (int i = 1; i < 1000000; i++)
       {
           if (road(i) > max)
           {
               max = road(i);
               num = i;
           }
       }
       Console.WriteLine(num);
   }

      

But no output is displayed.

+3


source to share


4 answers


(I'm not going to give you a complete solution, as Project Euler is about making you think, not us, who have already solved the problems.)



Try to figure out how big the values ​​are in your chain and be aware of the constraints on integer types .

+11


source


function problem14(){

    function r(p,n){
        return cl(p)>cl(n)?p:n;
    }

    function c(n){
        return n%2===0?n/2:3*n+1;
    }

    function cl(n){
        var _a = 1;
        var _n = n;
        while(_n !== 1){
            _a++;
            _n = c(_n);
        }
        return _a;
    }

    var b = [];
    var m = 20;
    var i = 500000;
    while(i < 1000000){
        var _n = cl(i);
        if(_n>m){
            b.push(i);
            m = _n;
        }
        i++;
    }

    return b.reduce(r);

}

      




Here is my js code.

+1


source


This does not mean that "nothing is displayed", it works for a very long time. If you change the upper bound for the for-loop to 100000, you can see that you get the output pretty quickly. The reason it works for a very long time is because you are using unverified integers and you are not getting overflow where you need it. Break after a few seconds, you will see negative n

.

Try the following i.e. with a keyword checked

, this will illustrate what I mean:

// will now throw OverflowException with large n
checked
{
    int road = 0;
    while (n != 1)
    {
        if (n%2 == 0)
            n = n/2;
        else
            n = 3*n + 1;
        road++;
    }
    return road;
}

      

0


source


First, notice that you are calling road () twice per iteration, which is a waste of processing time (and may have unwanted consequences for a function with side effects).

Second, due to integer overflow, you cannot get an answer - for example, the value 113383 ends up looping around the same 20 or so numbers

-122, -61, -182, -91, -272, -136, -68, -34, -17, -50, -25, -74, -37, -110, -55, - 164, -82 , -41, -122

Oops!

0


source







All Articles