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 <[email protected]> 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 [email protected] http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits
