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.
source to share
(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 .
source to share
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.
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;
}
source to share
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!
source to share