*Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:*

All,

YuckFoo has posted on a lot of interesting problems. I was looking at Rotationally Prime Numbers and doubted any mathematical shortcuts could be employed to determine if a candidate number passed since prime numbers are involved. I pulled out my bag of tricks to make the brute force method faster and found~~60~~ 55 rotational primes in less than 1 second:
The problem is that I can't find any after 999331 even though I tested numbers in the hundreds of millions. It is possible that my code is flawed or perhaps it is the last one.

YuckFoo has posted on a lot of interesting problems. I was looking at Rotationally Prime Numbers and doubted any mathematical shortcuts could be employed to determine if a candidate number passed since prime numbers are involved. I pulled out my bag of tricks to make the brute force method faster and found

#!/usr/bin/perl use strict; use warnings; my $impossible = qr/([245680])/; my $n = 5; print "$_\n" for (2, 3, 5); for ( 1 .. 3_157 ) { $n += 2; my $skip; if ( $n =~ $impossible ) { $skip = adjust( $1, $n ); next if $skip && $n =~ $impossible; } print $n, "\n" if rot_prime( $n ); next if $skip; $n += 4; if ( $n =~ $impossible ) { adjust( $1, $n ); next if $n =~ $impossible; } print $n, "\n" if rot_prime( $n ); } print "Last number checked : $n\n"; sub rot_prime { my $n = shift; return 0 if ! is_prime( $n ); my @dig = split //, $n; for ( 1 .. $#dig ) { push @dig, shift @dig; return 0 if ! is_prime( join '', @dig ); } return 1; } sub adjust { my $dig = shift; return 0 if $dig == 5 && $_[0] =~ /5$/; my $new = $dig; $new += $dig == 5 ? 2 : 1; $_[0] =~ s/$dig(\d+)$/$new . '1' x length( $1 )/e; $_[0] = $_[0] - $_[0] % 3; $_[0] += not ($_[0] % 2) ? -1 : 2; return $_[0]; } sub is_prime { my $num = shift; my ($div, $sqrt) = (5, int sqrt $num); while ( $div <= $sqrt ) { return 0 if not $num % $div; $div += 2; return 0 if not $num % $div; $div += 4; } return 1; }

Can you find any more or prove that there aren't any? Note: This code does not supress rotations.

Cheers - L~R

**Update:** Minor bugfix to avoid multiples of 3

Back to
Seekers of Perl Wisdom

Comment onRotationally Prime Numbers RevisitedDownloadCode