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

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

commit b725603e66f81be2f9f80ceda53df3b6cb7cb444
Author: Dana Jacobsen <d...@acm.org>
Date:   Wed Oct 17 01:38:52 2012 -0600

    Add Lucas, Fibonacci, and Palindromic primes, plus speedups
---
 bin/primes.pl | 152 +++++++++++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 134 insertions(+), 18 deletions(-)

diff --git a/bin/primes.pl b/bin/primes.pl
index 9e73a8d..3cdb6fe 100755
--- a/bin/primes.pl
+++ b/bin/primes.pl
@@ -6,22 +6,35 @@ use Getopt::Long;
 use Math::Prime::Util qw/primes next_prime is_prime/;
 $| = 1;
 
+# For many more types, see:
+#   http://en.wikipedia.org/wiki/List_of_prime_numbers
+#   http://mathworld.wolfram.com/IntegerSequencePrimes.html
+
 my $show_safe = 0;
 my $show_sophie = 0;
 my $show_twin = 0;
+my $show_lucas = 0;
+my $show_fibonacci = 0;
+my $show_palindromic = 0;
 my $show_usage = 0;
 my $segment_size = 30 * 128_000;   # 128kB
 
-GetOptions( "safe"   => \$show_safe,
-            "sophie" => \$show_sophie,
-            "twin"   => \$show_twin,
-            "help"   => \$show_usage,
+GetOptions( "safe"      => \$show_safe,
+            "sophie|sg" => \$show_sophie,
+            "twin"      => \$show_twin,
+            "lucas"     => \$show_lucas,
+            "fibonacci" => \$show_fibonacci,
+            "palindromic|palindrome|palendrome" => \$show_palindromic,
+            "help"      => \$show_usage,
           ) || die_usage();
 die_usage() if $show_usage;
 
 # Get the start and end values.  Verify they're positive integers.
 die_usage() unless @ARGV == 2;
 my ($start, $end) = @ARGV;
+# Allow "10**100" as arguments
+$start =~ s/^(\d+)\*\*(\d+)$/Math::BigInt->new($1)->bpow($2)/e;
+$end   =~ s/^(\d+)\*\*(\d+)$/Math::BigInt->new($1)->bpow($2)/e;
 die "$start isn't a positive integer" if $start =~ tr/0123456789//c;
 die "$end isn't a positive integer" if $end =~ tr/0123456789//c;
 
@@ -31,19 +44,105 @@ if ( ($start >= ~0 && $start ne ~0) || ($end >= ~0 && $end 
ne ~0) ) {
   $end = Math::BigInt->new($end);
 }
 
+# Fibonacci numbers
+{
+  my @fibs = (Math::BigInt->new(0), Math::BigInt->new(1));
+  sub fib {
+    my $n = shift;
+    return $n if $n < 2;
+    if (!defined $fibs[$n]) {
+      my ($nm2, $nm1) = ($fibs[-2],$fibs[-1]);
+      for (scalar @fibs .. $n) {
+        ($nm2, $nm1) = ($nm1, $nm2 + $nm1);
+        push @fibs, $nm1;
+      }
+    }
+    return $fibs[$n];
+  }
+}
+
+# Return all Lucas primes between start and end, using identity:
+#     L_n = F_n-1 + F_n+1
+sub lucas_primes {
+  my ($start, $end) = @_;
+  my @lprimes;
+  my $prime = 2;
+  my $k = 0;
+  while ($prime < $start) {
+    $k++;
+    $prime = fib($k) + fib($k+2);
+  }
+  while ($prime <= $end) {
+    push @lprimes, $prime if is_prime($prime);
+    $k++;
+    $prime = fib($k) + fib($k+2);
+  }
+  @lprimes;
+}
+
+sub fibonacci_primes {
+  my ($start, $end) = @_;
+  my @fprimes;
+  my $prime = 2;
+  my $k = 3;
+  while ($prime < $start) {
+    $k++;
+    $prime = fib($k);
+  }
+  while ($prime <= $end) {
+    push @fprimes, $prime if is_prime($prime);
+    # For all but k=4, F_k is prime only when k is prime.
+    $k = ($k <= 4)  ?  $k+1  :  next_prime($k);
+    $prime = fib($k);
+  }
+  @fprimes;
+}
+
+
+my @p;
 while ($start <= $end) {
 
-    # small segment size if we're doing bigints
-    $segment_size = 10000 if $start > ~0;
+    # This will need to be made more generic if we add more options like this.
+    # FIXME: It also doesn't work for our twin prime selection.
+    if ($show_lucas && $show_fibonacci) {
+      my %l;
+      undef @l{ lucas_primes($start, $end) };
+      @p = grep { exists $l{$_} } fibonacci_primes($start, $end);
+      $start = $end+1;
+
+    } elsif ($show_lucas) {
+      @p = lucas_primes($start, $end);
+      $start = $end+1;
+
+    } elsif ($show_fibonacci) {
+      @p = fibonacci_primes($start, $end);
+      $start = $end+1;
+
+    } else {
+      # small segment size if we're doing bigints
+      $segment_size = 10000 if $start > ~0;
+
+      if ( $show_palindromic && $start >= 100 && (length($start) % 2) == 0 ) {
+        # anything with an even number of digits is divisible by 11
+        $start = 10 ** (length($start)) + 1;
+      }
 
-    my $seg_start = $start;
-    my $seg_end = $start + $segment_size;
-    $seg_end = $end if $end < $seg_end;
-    $start = $seg_end+1;
+      my $seg_start = $start;
+      my $seg_end = $start + $segment_size;
+      $seg_end = $end if $end < $seg_end;
+      $start = $seg_end+1;
+      # Skip ranges where there are no palindromic primes.
+      # - anything starting with 24568 won't be a prime when reversed
+      if ( $show_palindromic && $seg_start >= 100 &&
+           length($seg_start) == length($seg_end)) {
+        next if $seg_start =~ /^2/ && $seg_end =~ /^2/;
+        next if $seg_start =~ /^8/ && $seg_end =~ /^8/;
+        next if $seg_start =~ /^[456]/ && $seg_end =~ /^[456]/;
+      }
+      @p = @{primes($seg_start, $seg_end)};
+      #warn "-- ", scalar @p, " primes between $start and $seg_end\n";
+    }
 
-    # Get a list of all primes in the segment.
-    my @p = @{primes($seg_start, $seg_end)};
-    #warn "-- ", scalar @p, " primes between $start and $segment_end\n";
     next unless scalar @p > 0;
 
 
@@ -64,35 +163,52 @@ while ($start <= $end) {
       #warn "   reduced to ", scalar @p, " twin primes\n";
     }
 
-
     # Restrict to safe primes if requested.
     if ($show_safe) {
-      @p = grep { is_prime( ($_-1) >> 1 ); } @p;
+      @p = grep { is_prime( ($_-1) >> 1 ); }
+           grep { ($_ <= 7) || ($_ % 12) == 11; }      # Optimization
+           @p;
       #warn "   reduced to ", scalar @p, " safe primes\n";
     }
 
-
     # Restrict to Sophie Germain primes if requested.
     if ($show_sophie) {
-      @p = grep { is_prime( 2*$_+1 ); } @p;
+      @p = grep { is_prime( 2*$_+1 ); }
+           grep { my $m30 = $_ % 30;
+                  $_ <= 5 || $m30 == 11 || $m30 == 23 || $m30 == 29 ; }
+           @p;
       #warn "   reduced to ", scalar @p, " SG primes\n";
     }
 
+    # Restrict to Palendromic primes if requested.
+    if ($show_palindromic) {
+      @p = grep { $_ eq reverse $_; } @p;
+      #warn "   reduced to ", scalar @p, " Palindromic primes\n";
+    }
+
     # print this segment
     print join("\n", @p), "\n"  if scalar @p > 0;
 }
 
+
+
+
 sub die_usage {
   die <<EOU;
 Usage: $0 [options]  START  END
 
 Displays all primes between the positive integers START and END, inclusive.
+The START and END values must be integers, however the shortcut "x**y" may
+be used, which allows very large values (e.g. '10**500' or '2**64')
 
 Options:
   --help      displays this help message
-  --safe      displays only safe primes, where (p-1)/2 is also prime
   --twin      displays only twin primes, where p+2 is also prime
+  --safe      displays only safe primes, where (p-1)/2 is also prime
   --sophie    displays only Sophie Germain primes, where 2p+1 is also prime
+  --lucas     displays only Lucas primes, where L_n is prime
+  --fibonacci displays only Fibonacci primes, where F_n is prime
+  --palindr   displays only Palindromic primes, where p eq reverse p
 
 Note that options can be combined, e.g. display all safe twin primes.
 EOU

-- 
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