My take on Euler #52 in Perl 6

colomon on 2009-07-29T17:26:24

Loved PerlJam's Euler #52 post, but instantly wanted to try to optimize it. I think this version is about five times faster than his (not sure because I'm too lazy to run his full program on my system) while being more careful about what it checks.

use v6;

my $pass_start = 5;     # start at the first number divisible by three after this one
my $pass_end = 17;      # skip ahead when we get here
my $n;
loop ($n = 6; ; $n += 3)
{
    if $n > $pass_end 
    {
        $pass_start *= 10;
        $pass_end *= 10;
        $n = $pass_start;
        $n -= $n % 3;
        next;
    }

    my $digits = (2*$n).comb.sort;
    next unless ($digits ~~ /0|5/);
    # say "$n ==> $digits";
    
    last if
        $digits eq (3*$n).comb.sort &&
        $digits eq (4*$n).comb.sort &&
        $digits eq (5*$n).comb.sort &&
        $digits eq (6*$n).comb.sort;
}
say $n;

---

Second try

colomon on 2009-07-29T19:30:36

I like this version better: http://paste.lisp.org/display/84391

Re:Second try

colomon on 2009-07-29T19:30:54

But it's a bit slower for some reason.

care to contribute to the euler_bench program?

notbenh on 2009-07-29T20:06:06

{after some poking from Eric Wilhelm I'll post this here as well}

I'm part of PDX.pm and we've started a project to collect solutions to euler problems as a way to benchmark rakudo. We would love to have you join in the fun. Currently everything is up on github (http://github.com/notbenh/euler_bench/tree/master).

Re:care to contribute to the euler_bench program?

colomon on 2009-07-30T00:05:54

I will add what I've got in as soon as I can puzzle out git. (A good exercise for me anyway!)

The answer has to be divisible by 9

btilly on 2009-07-30T09:03:53

The sum of the digits of a number mod 9 is always the number mod 9. The sum of the digits of 2*$n and 3*$n is the same, which means that mod 9, 2*$n and 3*$n are the same, which means that $n is 0 mod 9, so $n is divisible by 9.

This should improve your speed by a factor of 3. :-)

Re:The answer has to be divisible by 9

colomon on 2009-08-08T20:47:49

Huh. I don't follow your logic -- I don't know anything about sum of the digits being the same means the numbers are the same mod 9. BUT a web search trying to turn up more on it found a proof that "The difference of any two numbers composed of the same digits is always a multiple of nine." In which case 3*$n - 2*$n = $n is a multiple of nine, so your conclusion is dead on correct. Thanks!