3
\$\begingroup\$

This is my solution to Project Euler 14:

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

<?php
$count = 0 ;
$max = 0;

for($n = 2 ; $n < 1000000 ; $n++){
    while ($n > 1)
    {
        if ($n % 2 == 0 )
        {
            $n = $n/2;

        }
        else
        {
            $n = 3*$n + 1 ;

        }               
        $count += 1;

       if($count > $max )
       {
            $max = $count;
            $final = $n;    
       }
    }
 }
 echo $final;
?>

It took so long to run. I looked at some other solutions and they were very similar to my code logically, but they were running way much faster than mine. My question is, what is it that makes my code inefficient?

\$\endgroup\$
  • \$\begingroup\$ Please consider to add the requirements into your question verbatim, instead of providing just a link. Links are likely to decay, and rendering your question useless for future research. Also find a better title please. \$\endgroup\$ – πάντα ῥεῖ Dec 15 '15 at 19:44
4
\$\begingroup\$

Redoing tons of work

Consider a number like 100. By the time $n gets to 100, we will have already done the work for $n == 50 (which has a length of 25). So rather than simply seeing that the result for $n was 25, and adding 1 (since we're one step away from that) -- we have to recalculate all 26 steps from scratch.

For that matter, we'd've already done $n as 33, so just by having gotten to 100, we should already know that it's at 26 without doing any work.

Save your state as you go along - this is known as memoization. Given that the resulting longest chain is of length 525, that's a lot of work that we'll end up saving. Just that one chain will end up with 525 operations instead of 138,075...

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.