P is for Practical PerlMonks

Re: Rotationally Prime Numbers Revisited

by tall_man (Parson)
 on Mar 25, 2005 at 00:20 UTC ( #442231=note: print w/ replies, xml ) Need Help??

in reply to Rotationally Prime Numbers Revisited

I was going to suggest, as usual, that you use Math::Pari and the function isprime(), but your clever adjust method skips so many cases that even the brute-force prime checker you have is good enough. Math::Pari only buys you a fraction of a second.
Comment on Re: Rotationally Prime Numbers Revisited
Replies are listed 'Best First'.
Re^2: Rotationally Prime Numbers Revisited
by Limbic~Region (Chancellor) on Mar 25, 2005 at 00:30 UTC
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.

Cheers - L~R

* 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.
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;
}

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

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!

Cheers - L~R

Create A New User
Node Status?
node history
Node Type: note [id://442231]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (10)
As of 2016-05-31 16:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What font do you use for programming?

Results (384 votes). Check out past polls.