This is an automated email from the git hooks/post-receive script.

ppm-guest pushed a commit to annotated tag v0.38
in repository libmath-prime-util-perl.

commit 381a71f6593f47e7904dc620d32b95bf6daa6fdb
Author: Dana Jacobsen <d...@acm.org>
Date:   Tue Jan 28 19:43:19 2014 -0800

    Add some Project Euler examples
---
 MANIFEST                      |  9 +++++++++
 examples/project_euler_010.pl |  8 ++++++++
 examples/project_euler_021.pl | 11 +++++++++++
 examples/project_euler_037.pl | 20 +++++++++++++++++++
 examples/project_euler_047.pl |  9 +++++++++
 examples/project_euler_049.pl | 21 ++++++++++++++++++++
 examples/project_euler_069.pl | 17 ++++++++++++++++
 examples/project_euler_070.pl | 18 +++++++++++++++++
 examples/project_euler_095.pl | 45 +++++++++++++++++++++++++++++++++++++++++++
 examples/project_euler_357.pl | 14 ++++++++++++++
 10 files changed, 172 insertions(+)

diff --git a/MANIFEST b/MANIFEST
index bedbeb0..a745742 100644
--- a/MANIFEST
+++ b/MANIFEST
@@ -67,6 +67,15 @@ examples/porter.pl
 examples/verify-gmp-ecpp-cert.pl
 examples/verify-sage-ecpp-cert.pl
 examples/verify-cert.pl
+examples/project_euler_010.pl
+examples/project_euler_021.pl
+examples/project_euler_037.pl
+examples/project_euler_047.pl
+examples/project_euler_049.pl
+examples/project_euler_069.pl
+examples/project_euler_070.pl
+examples/project_euler_095.pl
+examples/project_euler_357.pl
 bin/primes.pl
 bin/factor.pl
 t/01-load.t
diff --git a/examples/project_euler_010.pl b/examples/project_euler_010.pl
new file mode 100644
index 0000000..06ddedb
--- /dev/null
+++ b/examples/project_euler_010.pl
@@ -0,0 +1,8 @@
+#!/usr/bin/env perl
+use warnings;
+use strict;
+use Math::Prime::Util qw/:all/;
+
+my $sum = 0;
+forprimes { $sum += $_ } 2_000_000;
+print "$sum\n";
diff --git a/examples/project_euler_021.pl b/examples/project_euler_021.pl
new file mode 100644
index 0000000..799000b
--- /dev/null
+++ b/examples/project_euler_021.pl
@@ -0,0 +1,11 @@
+#!/usr/bin/env perl
+use warnings;
+use strict;
+use Math::Prime::Util qw/:all/;
+
+my $sum = 0;
+foreach my $a (1..10000) {
+  my $b = divisor_sum($a)-$a;
+  $sum += $a + $b if $b > $a && $a == divisor_sum($b)-$b;
+}
+print "$sum\n";
diff --git a/examples/project_euler_037.pl b/examples/project_euler_037.pl
new file mode 100644
index 0000000..034c569
--- /dev/null
+++ b/examples/project_euler_037.pl
@@ -0,0 +1,20 @@
+#!/usr/bin/env perl
+use warnings;
+use strict;
+use Math::Prime::Util qw/:all/;
+use List::Util qw/sum/;
+
+my @tp;
+my $p = 7;
+while (1) {
+  $p = next_prime($p);
+  next unless $p =~ /^[2357]/ && $p =~ /[2357]$/;   # p ends are prime
+  my $len = 1;
+  while (++$len < length($p)) {
+    last unless is_prime(substr($p, 0, $len)) && is_prime(substr($p, -$len));
+  }
+  next unless $len == length($p);
+  push @tp, $p;
+  last if scalar @tp >= 11;
+}
+print sum(@tp), "\n";
diff --git a/examples/project_euler_047.pl b/examples/project_euler_047.pl
new file mode 100644
index 0000000..f56425e
--- /dev/null
+++ b/examples/project_euler_047.pl
@@ -0,0 +1,9 @@
+#!/usr/bin/env perl
+use warnings;
+use strict;
+use Math::Prime::Util qw/:all/;
+
+my $n = pn_primorial(4);  # Start with the first 4-factor number
+# factor_exp in scalar context returns the number of distinct prime factors
+$n++ while (factor_exp($n) != 4 || factor_exp($n+1) != 4 || factor_exp($n+2) 
!= 4 || factor_exp($n+3) != 4);
+print "$n\n";
diff --git a/examples/project_euler_049.pl b/examples/project_euler_049.pl
new file mode 100644
index 0000000..f65e64d
--- /dev/null
+++ b/examples/project_euler_049.pl
@@ -0,0 +1,21 @@
+#!/usr/bin/env perl
+use warnings;
+use strict;
+use Math::Prime::Util qw/is_prime primes/;
+
+sub is_perm {
+  my($a,$b) = @_;
+  return length($a) == length($b) &&
+         join("",sort split(//,$a)) eq join("",sort split(//,$b));
+}
+
+foreach my $inc2 (1 .. 1700) {
+  my $inc = $inc2 * 2;
+  foreach my $p (@{primes(1000,9999)}) {
+    my($p2, $p3) = ($p+$inc, $p+$inc+$inc);
+    last if $p3 > 9999;
+    next unless is_prime($p2) && is_prime($p3);
+    next unless is_perm($p, $p2) && is_perm($p, $p3);
+    print "$p/$inc: $p $p2 $p3\n";
+  }
+}
diff --git a/examples/project_euler_069.pl b/examples/project_euler_069.pl
new file mode 100644
index 0000000..855897d
--- /dev/null
+++ b/examples/project_euler_069.pl
@@ -0,0 +1,17 @@
+#!/usr/bin/env perl
+use warnings;
+use strict;
+use Math::Prime::Util qw/euler_phi pn_primorial/;
+
+# Better way
+my $n = 0;
+$n++ while pn_primorial($n+1) < 1000000;
+print pn_primorial($n), "\n";
+
+# Brute force
+my ($maxn, $maxratio) = (0, 0);
+foreach my $n (1 .. 1000000) {
+  my $ratio = $n / euler_phi($n);
+  ($maxn, $maxratio) = ($n, $ratio) if $ratio > $maxratio;
+}
+print "$maxn  $maxratio\n";
diff --git a/examples/project_euler_070.pl b/examples/project_euler_070.pl
new file mode 100644
index 0000000..f4a2636
--- /dev/null
+++ b/examples/project_euler_070.pl
@@ -0,0 +1,18 @@
+#!/usr/bin/env perl
+use warnings;
+use strict;
+use Math::Prime::Util qw/:all/;
+
+sub is_perm {
+  my($a,$b) = @_;
+  return length($a) == length($b) &&
+         join("",sort split(//,$a)) eq join("",sort split(//,$b));
+}
+
+my ($maxn, $minratio) = (0, 1000000);
+foreach my $n (2 .. 10_000_000) {
+  my $totient = euler_phi($n);
+  my $ratio = $n / $totient;
+  ($maxn, $minratio) = ($n, $ratio) if $ratio < $minratio && is_perm($totient, 
$n);
+}
+print "$maxn  $minratio\n";
diff --git a/examples/project_euler_095.pl b/examples/project_euler_095.pl
new file mode 100644
index 0000000..1d16105
--- /dev/null
+++ b/examples/project_euler_095.pl
@@ -0,0 +1,45 @@
+#!/usr/bin/env perl
+use warnings;
+use strict;
+use Math::Prime::Util qw/:all/;
+
+# Fill in the chains
+my @achain = ( [0] );
+foreach my $n (0 .. 50_000) {
+  next if defined $achain[$n];
+  my @seq = aliquot_sequence($n, 1_000_000);
+  #print "chain for $n = ", join(",", @seq), "\n";
+  while (@seq) {
+    my $s = shift @seq;
+    $achain[$s] = [$s, @seq] if !defined $achain[$s];
+  }
+}
+
+# Find max chain length
+my ($maxlen, $maxn) = (0, 0);
+foreach my $n (0 .. 1_000_000) {
+  next unless defined $achain[$n];
+  next unless $achain[$n]->[0] == $achain[$n]->[-1];
+  my $len = scalar @{$achain[$n]} - 1;
+  ($maxlen, $maxn) = ($len, $n) if $len > $maxlen;
+}
+print "Max length: $maxlen.  n = $maxn\n";
+print "Chain for $maxn: ", join(",", @{$achain[$maxn]}), "\n";
+
+sub aliquot_sequence {
+  my ($n, $max) = @_;
+  my %hash;
+  undef $hash{$n};
+  my @seq = ($n);
+  foreach my $len (1 .. 1000) {
+    $n = divisor_sum($n)-$n;
+    # Stop if we have exceeded the threshold
+    last if $n > $max;
+    # If we know how this chain ends, return it now
+    return @seq, @{$achain[$n]} if defined $achain[$n];
+    push @seq, $n;
+    return @seq if exists $hash{$n} || $n == 0;
+    undef $hash{$n};
+  }
+  return ();
+}
diff --git a/examples/project_euler_357.pl b/examples/project_euler_357.pl
new file mode 100644
index 0000000..5b69fe0
--- /dev/null
+++ b/examples/project_euler_357.pl
@@ -0,0 +1,14 @@
+#!/usr/bin/env perl
+use warnings;
+use strict;
+use Math::Prime::Util qw/:all/;
+
+# Takes ~ 10 seconds
+my $sum = 0;
+forprimes {
+  my $n = $_-1;                  # 1+$n/1 is prime  (hence n=1 or even)
+  if (is_prime(2+($n>>1))) {     # 2+$n/2 is prime  (noting n is even or 1)
+    $sum += $n unless scalar grep { !is_prime($_+$n/$_) } divisors($n);
+  }
+} 100_000_000;
+print "$sum\n";

-- 
Alioth's /usr/local/bin/git-commit-notice on 
/srv/git.debian.org/git/pkg-perl/packages/libmath-prime-util-perl.git

_______________________________________________
Pkg-perl-cvs-commits mailing list
Pkg-perl-cvs-commits@lists.alioth.debian.org
http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits

Reply via email to