Learning math and efficient algorithms using perl

andreas1234567 has asked for the wisdom of the Perl Monks concerning the following question:

Fellow Monks,

I try my best at Project Euler. Both fun and highly challenging.

Problem 12 reads Which is the first triangle number to have over five-hundred divisors? Being a Brute Force Monk, I came up with this highly inefficient algorithm. I want to learn more on math and efficient algorithms using perl, and I humbly seek the Monks advice on how to I acquire such skills.

use strict;
use warnings;

my $tri = 1;
my $i   = 1;

while ($i++) {
  $tri += $i;
  my $nof = 2 * scalar(grep { $tri % $_ == 0 } 1 .. sqrt($tri));
  if ($nof >= 500) {
    print "The " . $i . "th triangle number $tri has $nof divisors";
    last;
  }
}

__END__
$ time perl -wl 12.pl
The 12375th triangle number 76576500 has 576 divisors

real    0m26.947s
user    0m25.013s
sys     0m0.027s
[download]

--
Andreas

Comment on Learning math and efficient algorithms using perl Download Code

Replies are listed 'Best First'.
Re: Learning math and efficient algorithms using perl by rhesa (Vicar) on Sep 06, 2007 at 14:36 UTC
Some helpful links: Mathworld The On-Line Encyclopedia of Integer Sequences PARI/GP computer algebra system Specific to this problem: Divisor function Sloane A000005 Math::Pari Those sites help me solve pretty much all the Project Euler problems. Of course, it does help to have some familiarity with the basics of number theory and combinatorics. Google and Wikipedia can help you with that too. Here's my solution (runs in about 0.6 sec): `use Math::Pari qw(numdiv); while( ++$i ) { $n += $i; $d = numdiv($n); last if $d > 500; } print "$n: $d\n";` [download]	[reply] [d/l]
Re: Learning math and efficient algorithms using perl by swampyankee (Parson) on Sep 06, 2007 at 15:15 UTC
Another site that may be of interest is Dictionary of Algorithms and Data Structures. Also, when you say "500 divisors" do you mean 500 distinct divisors (2⁵⁰⁰ has one divisor, repeated 500 times)? emc Information about American English usage here and here. Any New York City or Connecticut area jobs? I'm currently unemployed.	[reply]
Re^2: Learning math and efficient algorithms using perl by rhesa (Vicar) on Sep 06, 2007 at 15:42 UTC
No, 2⁵⁰⁰ has 501 divisors. It's divisible by 1, 2, 4, ..., 2⁴⁹⁹, 2⁵⁰⁰.	[reply]
Re^3: Learning math and efficient algorithms using perl by swampyankee (Parson) on Sep 07, 2007 at 16:47 UTC
OK; 2 distinct divisors, one of which is repeated 500 times... emc Information about American English usage here and here. Any New York City or Connecticut area jobs? I'm currently unemployed.	[reply]
Re^4: Learning math and efficient algorithms using perl by blokhead (Monsignor) on Sep 07, 2007 at 16:57 UTC
Re^2: Learning math and efficient algorithms using perl by andreas1234567 (Vicar) on Sep 06, 2007 at 18:49 UTC
Also, when you say "500 divisors" do you mean 500 distinct divisors? I believe that's a correct observation. -- Andreas	[reply]
Re: Learning math and efficient algorithms using perl by blazar (Canon) on Sep 09, 2007 at 10:45 UTC
I try my best at Project Euler. Both fun and highly challenging. Problem 12 reads Which is the first triangle number to have over five-hundred divisors? I also play with PE and this is what I had used: `#!/usr/bin/perl -l use strict; use warnings; my $n; my @div=(0); while (++$n) { my ($m,$p)=($n,0); $m /= 2 and $p++ until $m & 1; $div[$n] = $p ? $div[$m]$p : grep !($n%$_), 1..$n; print $n($n-1)/2 and last if $div[$n]*$div[$n-1] > 500; } __END__` [download]	[reply] [d/l]
Re: Learning math and efficient algorithms using perl by artist (Parson) on Sep 06, 2007 at 20:36 UTC
You can improve the speed of your code with: `sub get_nof2 { return scalar @{ divisors(+shift) }; } { my $D; sub divisors { my $n = shift; foreach my $d ( 2 .. sqrt($n) ) { unless ( $n % $d ) { my $div = $n / $d; unless ( defined $D->{$div} ) { $D->{$div} = divisors($div); } return $D->{$n} = [ uniq( @{ $D->{$div} }, map { $d * $_ } @{ $D->{$div} } + ) ]; } } return $D->{$n} = [ 1, $n ]; }` [download] --Artist	[reply] [d/l]