go ahead... be a heretic PerlMonks

Re^3: Rotationally Prime Numbers Revisited

by tilly (Archbishop)
 on Mar 25, 2005 at 01:21 UTC ( #442258=note: print w/replies, xml ) Need Help??

in reply to Re^2: Rotationally Prime Numbers Revisited
in thread Rotationally Prime Numbers Revisited

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

Replies are listed 'Best First'.
Re^4: Rotationally Prime Numbers Revisited
by tlm (Prior) on Mar 25, 2005 at 04:39 UTC

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

Re^4: Rotationally Prime Numbers Revisited
by Limbic~Region (Chancellor) on Mar 25, 2005 at 01:25 UTC
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://442258]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (3)
As of 2019-06-17 00:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Is there a future for codeless software?

Results (76 votes). Check out past polls.

Notices?