A Project Euler Puzzler (specifically in PHP)

Question

There is another recent Project Euler question but I think this is a bit more specific (I'm only really interested in PHP based solutions) so I'm asking anyway.

Question #5 tasks you with: "What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?"

Now, I have solved it twice. Once very inefficiently and once much more efficiently but I am still far away from an especially sophisticated answer (and I am not especially solid in math hence my brute force solution). I can see a couple of areas where I could improve this but I am wondering if any of you could demonstrate a more efficient solution to this problem.

*spoiler: Here is my less than optimal (7 seconds to run) but still tolerable solution (not sure what to do about the double $... just pretend you only see 1...

    function euler5(){
        $x = 20;

        for ($y = 1; $y < 20; $y++) {

            if (!($x%$y)) {

            } else {  
                $x+=20;
                $y = 1;  
            }   

        }echo $x;
     };

Answer 1

Collect prime factors for all numbers between 1 and 20. Counting the maximal exponents of each prime factor, we have 16 = 2**4, 9 = 3**2, as well as 5, 7, 11, 13, 17, 19 (each appearing only once). Multiply the lot, and you have your answer.

Answer 2

Chris Jester-Young is right.

In general if you wanted the smallest number that is evenly divisible by all of the numbers from 1 to N, you would want to find all the prime numbers from 2 to N, and for each one, find the greatest number of times it divides any number in the range. This can be calculated by finding the greatest power of the prime that's not greater than N.

In the case of 20, as Chris pointed out, 2^4 is the greatest power of 2 not greater than 20, and 3^2 is the greatest power of 3 not greater than 20, and for all other primes, only the first power is not greater than 20.

Answer 3

in php it will look like this:

<?php
function gcd($a,$b) {
    while($a>0 && $b>0) {
        if($a>$b) $a=$a-$b; else $b=$b-$a;        
    }
    if($a==0) return $b;
    return $a;
}
function euler5($i=20) {
    $euler=$x=1;
    while($x++<$i) {
        $euler*=$x/gcd($euler,$x);
    }
    return $euler;
}

?>

Its at least twice as fast than what you posted.

Answer 4

You can remove some numbers that are divided with, for example 1 is unnecessary, all natural numbers are divisible by 1.you don’t need 2 either, and therefore, all numbers are divisible by multiples of 2 (4, 8, 16, etc) are divisible by 2, also. So the relevant numbers will be 11, 12, 13, 14, 15, 16, 17, 18, and 19.

So:

<?
function eulerPuzzle()
{
  $integers = array( 11,12,13,14,15,16,17,18,19 );

  for ($n = 20; 1; $n += 20 ) {
    foreach ($integers as $int) { 
      if ( $n % $int ) { 
    break; 
      }
      if ( $int == 19 ) { 
    die ("Result:" . $n); 
      }
    }
  }
}

eulerPuzzle();
?>

Answer 5

I know you said PHP, but here's my rough draft in Python.

#!/usr/bin/env python

from operator import mul

def factor(n):
    factors = {}
    i = 2
    while i < n and n != 1:
        while n % i == 0:
            try:
                factors[i] += 1
            except KeyError:
                factors[i] = 1
            n = n / i
        i += 1
    if n != 1:
        factors[n] = 1
    return factors

base = {}
for i in range(2, 2000):
    for f, n in factor(i).items():
        try:
            base[f] = max(base[f], n)
        except KeyError:
            base[f] = n

print reduce(mul, [f**n for f, n in base.items()], 1)

It's not as elegant as I could have made it, but it calculates the least common multiple of the numbers from 2 to 2000 in .15s. If your iterative solution could process a billion candidates per second, it would take 10^849 years to finish.

In other words, don't bother optimizing the wrong algorithm.

Answer 6

<?php
$i=20;
while ($i+=20) {
    for ($j=19;$j!==10;--$j){
     if ($i%$j) continue 2;
    }
    die ("result: $i\n");
}

Is the fastest and shortest php solution so far. About 1.4x faster than Czimi's on my comp. But check out the python solution, thats a nice algo.

Answer 7

Some people really over-think this...

In Ruby:

puts 5*7*9*11*13*16*17*19