Fibonacci and Primes

The middle challenge was to find the first prime Fibonacci number greater than 227000, add one to it, and then sum the prime numbers which were its factors. Here’s my first implementation:

sub is-prime($a) {
    return Bool::True if $a == 2;
    ! [||] $a <<%%<< (2, 3, *+2 ... * > $a.sqrt);
}

my @fib := (1, 1, *+* ... *);

my $cutoff = 227000;
my $least-prime = 0;
for @fib -> $f {
    next if $f <= $cutoff;
    next unless is-prime($f);
    $least-prime = $f;
    last;
}

my $x = $least-prime + 1;
say [+] (2, 3, *+2 ... * > $x.sqrt).grep({ $x %% $^a && is-prime($a) });

Despite what seems like an obvious inefficiency (approximating the prime numbers with the odd numbers), this is pretty snappy, executing in 12.5 seconds.

I was planning to go on and talk about my new Math::Prime module here, but looking at this code, I think it can be expressed rather more nicely with a tweak or two here. Let's see.


sub is-prime($a) {
    return Bool::True if $a == 2;
    ! [||] $a <<%%<< (2, 3, *+2 ... * > $a.sqrt);
}

my @fib := (1, 1, *+* ... *);
my $cutoff = 227000;
my $least-prime = @fib.first({ $_ > $cutoff && is-prime($_) });
my $x = $least-prime + 1;
say [+] (2, 3, *+2 ... * > $x.sqrt).grep({ $x %% $^a && is-prime($a) });

So that's what the first method is good for!

I did indeed write Math::Prime just so I could use it here. It's not a huge change from the previous version, really:

use Math::Prime;

my @fib := (1, 1, *+* ... *);
my $cutoff = 227000;
my $least-prime = @fib.first({ $_ > $cutoff && is-prime($_) });
my $x = $least-prime + 1;
say [+] (primes() ... * > $x.sqrt).grep({ $x %% $^a });

Unfortunately, Math::Prime isn't optimized yet, and so this version, while a bit nicer, is actually slower than the previous version.

Update: With Moritz's help I did some optimizations to Math::Prime, and the script using it is now very significantly faster than the others.

About these ads

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: