Euler 5

(Wrote this post last week, but accidentally posted it to the wrong blog!)

So, Hacker News brought me this post this morning, and I wanted to see how Perl 6 stacked up to Java / Scala. The answer turned out to be pretty poorly speed-wise, at least in my initial attempts. But that’s a story for another post. Right now I’m just interested in finding a good solution to the problem itself: “What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?”

So far, this is my favorite, I think:

sub divides-by-all-up-to($a, $b) {
    !(2..$b).grep($a !%% *);
}

my $N = [*] 2, 3, 5, 7, 11, 13, 17, 19;
my @attempts := $N, 2 * $N ... { divides-by-all-up-to($_, 20) };
say @attempts[*-1];

You can easily get this down to a two-liner, but only at the cost of a good bit of clarity, IMO.

So, what does it do? divides-by-all-up-to checks to see if $a is divisible by all the numbers from 2 to $b. This is one of those concepts for which there is very definitely more than one way to do it in Perl 6. For instance,

    ?all($a <<%%<< 2..$b)

or

    [&&} $a X%% 2..$b

and so on. I choose my approach because it is pretty straightforward, reasonably efficient, and works on both Rakudo and Niecza.

$N is my secret weapon. It's the product of all the primes less than 20. All of those primes have to be factors of the answer, so we only consider multiples of $N, saving lots of time. To be precise, it means we call divides-by-all-up-to once for every 4,849,845 times the Scala version calls the equivalent function.

The next step is fun with sequences. We want to consider the multiples of $N, stopping when we hit one for which divides-by-all-up-to is true. This is easily expressible using the sequence operator:

    my @attempts := $N, 2 * $N ... { divides-by-all-up-to($_, 20) };

The initial $N, 2 * $N tells the sequence operator that we want the sequence of multiples of $N; the rest tells it when to stop. (We know that it has to stop eventually because 20! has all the correct properties and is a multiple of $N.) The end result is a sequence whose last value is the number we are looking for. And we finally get that last value with standard Perl 6ish @attempts[*-1].

Here's a much more generalized approach. Not sure if it will work with Niecza or not (I've never figured how to use modules with Niecza) but it does work with Rakudo.

use Math::Prime;

sub factors($n is copy) {
    my @primes := primes;
    my $prime = @primes.shift;
    my %factors;
    while $n > 1 {
        if $n %% $prime {
            %factors{$prime}++;
            $n div= $prime;
        } else {
            $prime = @primes.shift;
        }
    }
    return %factors;
}

sub product(%factors) {
    [*] %factors.map({ .key ** .value });
}

sub least-divisble-by-all(@values) {
    my %common-factors;
    for @values -> $i {
        my %factors = factors($i);
        for %factors -> $prime {
            if %common-factors.exists($prime.key) {
                %common-factors{$prime.key} max= $prime.value;
            } else {
                %common-factors{$prime.key} = $prime.value;
            }
        }
    }
    
    product(%common-factors);
}

This version uses the prime factorization of the numbers to smartly figure out the answer. It's much more flexible and and probably faster for big numbrers, but... it's just too long to make me love it.

About these ads

7 Responses to “Euler 5”

  1. sorear Says:

    This is a Perl 6 predefined function (not in Niecza yet, but seems to work fine in Rakudo): “say [lcm] 1..20″

  2. Tim Bollman Says:

    Given the problem, you can actually transform it into a semi-one liner. I’m too rusty at the moment to find the correct function for filtering the list down to the primes less than 20 from the infinite list, but the following works:
    my @primes = (2,3,5,7,11,13,17,19);
    [*] @primes.map({ $^prime ** log(20, $^prime).floor; });

    • colomon Says:

      Woah. Can you explain why that works? I don’t know if it’s over-tiredness or just general denseness on my part, but I can’t think of any obvious reason it ought to work, and it certainly does…

      • Tim Bollman Says:

        I can. Whether or not I explain it well is another story :P.

        The english description of the algorithm is “find and multiply the largest power of every prime that is less than or equal to the maximum of the range”.

        We’re basically saying that we don’t care what the actual numbers are for the lcm, we just care about the largest prime powers that fit in the range. And since multiplying two primes can’t make the number smaller, we know that if 2**5 won’t fit, neither will 2**5 times anything else. And if 2**2*3 fits, so will both 2**2 and 3. So basically if a composite exists in the range the largest prime power it can have is also in the range (since it has to be at least half as big).

        This actually kind of works for ranges that don’t start with 1 too. If the power is in the range, you’re done. Otherwise you have to backtrack down through smaller powers until you find one that has a prime in (min .. max) / power.

      • colomon Says:

        Thanks!

      • Tim Bollman Says:

        Correction on the ranges that don’t start with 1. It should be ceil(min / power) <= floor(max / power). Doesn't have to be a prime; silly me.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: