Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation

Rotationally Prime Numbers

by YuckFoo (Abbot)
on Jan 29, 2002 at 02:11 UTC ( #142199=CUFP: print w/replies, xml ) Need Help??

1193 is 'rotationally prime' because 1193 and all of it's rotations (1931, 9311, and 3119) are prime. There is another set of 4-digit, and two sets of 5-digit rot-prime numbers. I think that's cool, but I'm not sure why...

Update: changed stop criteria in sub primelist from test/2 to sqrt(test). Thanks to larsen.

Also, there are two sets of 6 digit rot-prime numbers.


#!/usr/bin/perl use strict; my ($DIGITS) = (5); my ($list, $item); $list = primelist(10**$DIGITS); $list = rotatelist($list); for $item (@{$list}) { print "$item\n"; } #----------------------------------------------------------- sub rotatelist { my ($primes) = @_; my (@list, %phash, $prime, $sum); my ($rotations, $rotation); @phash{@{$primes}} = (1) x @{$primes}; for $prime (@{$primes}) { $rotations = rotations($prime); if ($prime == $rotations->[0]) { $sum = 0; for $rotation (@{$rotations}) { $sum += $phash{$rotation}; } if ($sum == @{$rotations}) { push (@list, $prime); } } } return \@list; } #----------------------------------------------------------- sub rotations { my ($num) = @_; my (@list, @digs, $i); @digs = split('', $num); for ($i = 0; $i < length($num); $i++) { push (@digs, shift(@digs)); push (@list, join ('', @digs) + 0); } @list = sort(@list); return \@list; } #----------------------------------------------------------- sub primelist { my ($max) = @_; my ($test, $stop, $isprime, $prime); my (@primes) = qw(2); for ($test = 3; $test < $max; $test++) { $stop = sqrt($test); $isprime = 1; for $prime (@primes) { if ($prime > $stop) { last; } if ($test % $prime == 0) { $isprime = 0; last; } } if ($isprime) { push (@primes, $test); } } return \@primes; }

Replies are listed 'Best First'.
Re: Rotationally Prime Numbers
by particle (Vicar) on Jan 29, 2002 at 04:32 UTC
    i wrote an algorithm to save you many, many cycles.

    createPrimeVec() creates a bit vector of length $max. the value is 0 if prime, 1 otherwise. it uses the sieve of erathosthenes method to create the list. merlyn wrote a column on this some time ago (suprise!)

    isprime() is a simple bit vector lookup, very fast.

    rotPrime() cleverly appends the return value of chop to the beginning of the string.

    here it is:

    #!/usr/local/bin/perl -w use strict; $|=1; my $vecPrime; my %rotPrime; # allows specification of a range, such as (1000, 9999) my ($min, $max) = (2, 999_999); print "---creating prime vector (length: $max)\n"; $vecPrime = createPrimeVec($max); print "---created\n\n"; print "---trying rotations $min..$max\n"; for($min..$max) { next unless isprime($_); my $x = rotPrime($_); $x && $rotPrime{$x}++; } print "---tried $min..$max\n\n"; print "$_\n" for(sort {$a <=> $b} keys %rotPrime); #---------- # return list of prime numbers up to and including value passed (defau +lt:1000) sub createPrimeVec { my $UPPER = shift || 1000; my $sieve = ""; GUESS: for (my $guess = 2; $guess <= $UPPER; $guess++) { next GUESS if vec($sieve,$guess,1); for(my $mults = $guess * $guess; $mults <= $UPPER; $mults += $ +guess) { vec($sieve,$mults,1) = 1; } } return $sieve; }; # returns true if found in prime number bit vector sub isprime { return 1 if( vec($vecPrime,shift,1) == 0 ); }; # return smallest 'rotationally prime' number in set # for instance, 1931, 9311, 3119, or 1193 yeilds return value 1193 sub rotPrime { my ($num, $lchr, @list) = (shift); for(1..length $num) { $lchr = chop $num; $num = $lchr . $num; push @list, $num; return unless isprime($num); } return (sort @list)[0]; };
    i had used the prime number code for a program using fermat's factoring algorithm. perhaps i'll post it, assuming there's not a module to do that already.


      Thanks particle,

      Great improvement. I purposefully didn't use the sieve method for memory considerations, but I see this is an ideal situation for vec. Something I've been aware of, but never really found a use for.


      i had used the prime number code for a program using fermat's factoring algorithm. perhaps i'll post it, assuming there's not a module to do that already.

      Surely there was space in the margin to post it :-)

Re: Rotationally Prime Numbers
by dragonchild (Archbishop) on Jan 29, 2002 at 03:14 UTC
    Neat algorithm. I'll arrogantly rewrite your code to make it what I consider to be more Perlish. :-)

    This takes advantage of a number of things some C/C++ programmers may or may not know/be comfortable with.

    #!/usr/local/bin/perl use strict; use warnings; use constant DIGITS => (5); my $list = primelist(10 ** DIGITS); $list = rotatelist($list); print $_, $/ for @$list; #----------------------------------------------------------- sub rotatelist { my ($primes) = @_; my %phash; @phash{@{$primes}} = (1) x @{$primes}; my @list; for my $prime (@{$primes}) { my $rotations = rotations($prime); if ($prime == $rotations->[0]) { my $sum = 0; $sum += $phash{$_} || 0 for @$rotations; push @list, $prime if $sum == @{$rotations}; } } return \@list; } #----------------------------------------------------------- sub rotations { my ($num) = @_; my @digs = split '', $num; my @list; for (1 .. length($num)) { push @digs, shift @digs; push @list, join ('', @digs) + 0; } @list = sort(@list); return \@list; } #----------------------------------------------------------- sub primelist { my ($max) = @_; my @primes = (2); for (my $test = 3; $test < $max; $test += 2) { my $stop = sqrt($test); my $isprime = 1; for my $prime (@primes) { last if $prime >= $stop; if ($test % $prime == 0) { $isprime = 0; last; } } push @primes, $test if $isprime; } return \@primes; }

    We are the carpenters and bricklayers of the Information Age.

    Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

Re (tilly) 1: Rotationally Prime Numbers
by tilly (Archbishop) on Feb 01, 2002 at 04:00 UTC
    A minor number theory note.

    Based on some back of the envelope estimates, there should be only a finite number of rotational primes in base 10. (I haven't double-checked my estimates closely, but I find it suggestive that you have 4 of size 1, and none of size 7.)

    However my estimates suggesting this were based on the standard, "Treat is_prime(n) as a random number with probability 1/log(n) of being true." This is a simple rule of thumb which leads to a lot of estimates in number theory, most of which are strongly supported by the numerical evidence. (For instance the prime number theorem is true, the Riemann Hypothesis should be, the twin prime conjecture should be, Mertens Conjecture should be false but the numerical evidence will make it look true for an absurdly long time, etc.)

    Unfortunately it is a rule of thumb that is absolutely and horribly wrong, with the result that number theory is full of gloriously precise conjectures on primes which have very strong affirmative evidence, but which are not readily amenable to proof.

    UPDATE: As I point out at Re^2: Rotationally Prime Numbers Revisited, I think this post is wrong. (I forgot about numbers that are just strings of 1s.)

Re: Rotationally Prime Numbers
by Anonymous Monk on Jan 31, 2002 at 19:36 UTC

    You should be able to get a fairly decent speed improvement by automatically throwing out any numbers containing a 0, 2, 4, 5, 6 or 8 as obviously these can't be rotationally prime.


Re: Rotationally Prime Numbers
by trammell (Priest) on Feb 01, 2002 at 00:11 UTC
    There was a great thread on CLPM where Abigail posted some super sieve code.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: CUFP [id://142199]
Approved by root
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (7)
As of 2017-02-21 21:32 GMT
Find Nodes?
    Voting Booth?
    Before electricity was invented, what was the Electric Eel called?

    Results (320 votes). Check out past polls.