Re^2: Rotationally Prime Numbers Revisited

[Limbic~Region]

tall_man,
While Anonymous Monk suggested skipping all numbers containing (0, 2, 4, 5, 6, 8) in the original thread by YuckFoo, I independently thought of the idea on my own. I did borrow the 2/4 trick to avoid multiples of 3. The problem space reduction is amazing. In the first 1_000_000 numbers, only 4_220 candidates are tested. Out of those, 621^* are eliminated as not being prime on the very first try.

I was going to use the C version of is_prime() from Re^3: a close prime number but as you saw yourself, it isn't needed.

* Numbers ending in 5 (15 for instance) in the +2 portion of the code are included as candidates. It is possible to eliminate them but the work involved is more than allowing is_prime() to abort on the first try.

[tilly]

Here is a much faster approach. (I searched up to 10 billion in 10 minutes on my PC.) It looks at far fewer than yours does since it knows that it only looks at numbers whose digits are 1, 3, 7 and 9, and which furthermore have the largest digit first.

#! /usr/bin/perl -w
use strict;

print "$_\n" for 2, 3, 5, 7;
my @d = (1, 3, 7, 9);
my %seen;
for my $length (2..(shift || 6)) {
  # print "Length: $length\n";
  LIMIT: for my $limit (0..3) {
    my @indexes = $limit - 1;
    NUMBER: while (1) {
      $indexes[-1]++;
      while ($indexes[-1] > $limit) {
        pop @indexes;
        next LIMIT unless @indexes;
        $indexes[-1]++;
      }
      while (@indexes < $length) {
        push @indexes, 0;
      }
      my $num = join '', @d[@indexes];
      for (1..$length) {
        next NUMBER unless is_prime_for_odds_over_3($num);
        $num =~ s/(\d)(\d*)/$2$1/;
      }
      for (1..$length) {
        print "$num\n" unless $seen{$num}++;
        $num =~ s/(\d)(\d*)/$2$1/;
      }
    }
  }
}


sub is_prime_for_odds_over_3 {
  my $n = shift;
  my $max = sqrt($n);
  return 0 unless $n % 3;
  my $div = 5;
  while ($div <= $max) {
    return 0 unless $n % $div;
    $div += 2;
    return 0 unless $n % $div;
    $div += 4;
  }
  return 1;
}

[tlm]

It's already very fast, but you can improve it somewhat by doing your rotations with

$num = chop($num) . $num;



      Rate    s chop
s    258/s   -- -14%
chop 299/s  16%   --

the lowliest monk

[Limbic~Region]

tilly,
I certainly considered this approach in theory. I just couldn't see an easy way to jump and that's the real trick. Without the jump, then you end up incrementing/testing far too much. I love looking at a problem in a new light - Thanks!