Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid

Rotationally Prime Numbers Revisited

by Limbic~Region (Chancellor)
on Mar 24, 2005 at 19:57 UTC ( #442179=perlquestion: print w/replies, xml ) Need Help??
Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:

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:
#!/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; }
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.

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

Replies are listed 'Best First'.
Re: Rotationally Prime Numbers Revisited
by ambrus (Abbot) on Mar 24, 2005 at 20:49 UTC
    A068652 is the sequence of rotational primes. It references A003459, the sequence of absolute primes, the numbers of which all the permutations are primes. That sequence contains the numbers 1111111111111111111, and 11111111111111111111111. There's also a link to this page: MATHEWS: Circular, Permutable, Truncatable and Deletable Primes, which lists all known rotational primes. According to that list, you probably won't find any more rotational primes.
      Fascinating. Contrary to what I said at Re: Re (tilly) 1: Rotationally Prime Numbers, when I consider numbers that are strings of 1's, the prime number theorem naively suggests that there should be an infinite number of rotational primes of that form. (This differs from most numbers in that there is only 1 number in the rotation - the odds of 1 number being prime is far different than the odds of n of them being prime.)

      Of course there are a lot of special factorization properties of long strings of 1's. So it may not be so simple as all that. But the number of rotational factors between length 23 and 1031 matches the naive prediction surprisingly well. (The naive prediction is that the number of primes out to length n should be roughly log(n)/log(10), and the number in any interval should be the difference of those two. From 23 to 1031 we'd predict 1.65 and actually had 2.)

        As we all know, (10**n-1)/9 is surely not a prime when n is composed, because (10**(k*l)-1)/9 = ((10**(k*l)-1)/(10**k-1)) * ((10**k - 1)/9). Thus, they do have special factoring properties, but this doesn't mean that they are either more often or less often primes then other numbers.

      According to the Mathews page, all repunit primes (primes consisting of the digit "1" only) are rotational primes -- and that there are conjectured to be an infinite number of them.

      If so, there are an infinite number of (trivial) repunit rotational primes, but there may not be any more nontrivial ones.

Re: Rotationally Prime Numbers Revisited
by 5mi11er (Deacon) on Mar 24, 2005 at 22:22 UTC
    I was going to say that proving a "negative statement", is logically impossible...

    However, this is mathematics, so perhaps the "I can't prove I don't have something, you have to prove I do" isn't quite as solid in the world of mathematics? I'm pretty sure reading through some of the recent mathematical threads I've seen some "proofs" that showed that certain things are not possible.

    But, I could simply be remembering "conjectures" and the like as "proofs", and thus, the original line above might still be correct?


      It is perfectly valid in math to prove that something does not exist. For example, there are no positive integers {a,b,c} such that a^3 + b^3 = c^3

      This is a direct result of Wiles (1994) proof of Fermats Last Theorem.

      Now there are also a different class of assertions that cannot be proved either way. (Godels Incompleteness Theorem)
      I am digressing a lot here, but if you find this sort of thing interesting, i suggest reading 'Godel, Escher, Bach' by Hofsteadter (spelling?)
      ...prepare to hurt your brain :)

        For example, there are no positive integers {a,b,c} such that a^3 + b^3 = c^3

        This is a direct result of Wiles (1994) proof of Fermats Last Theorem.

        No, this case is much easier to prove than the general case, and was proven in the 18th century by Euler and Legendre.

        In fact, for all sufficently small n exponents the impossibility of a^n + b^n = c^n was proven long ago, in fact, Szalay[1] which was published in 1991 reports all n < 125000.

        [1] Dr. Szalay Mihály, Számelmélet. Tankönyvkiadó, Budapest, 1991

Re: Rotationally Prime Numbers Revisited
by shemp (Deacon) on Mar 25, 2005 at 00:53 UTC
    Well, i just wrote my own prime checker that is really a growing sieve that goes as far as it needs to for the prime to check. It caches a hash of all the primes known so far, so that primeness only needs to be calculated once, and is quite fast. I didnt even bother explicitly eliminating even numbers in advance, but that would be no biggie. The general sieve'ing can be improved some too. So here it is:
    { my %prime_cache; my $max_checked; BEGIN { $prime_cache{2} = undef; $max_checked = 2; } sub is_prime { my ($to_check) = @_; sieve_up_to($to_check); return exists $prime_cache{$to_check}; } sub sieve_up_to { my ($to_check) = @_; while ( $max_checked < $to_check ) { sieve_part($to_check); } } sub sieve_part { my ($to_check) = @_; $to_check++ if !($to_check % 2); my $max_this_part = $to_check; if ( ($max_checked * $max_checked) < $to_check ) { $max_this_part = $max_checked * $max_checked; } my %to_sieve = map { $_ => undef } ($max_checked + 1 .. $max_t +his_part); for my $prime (keys %prime_cache) { my $base = $max_checked - ($max_checked % $prime) + $prime +; while ( $base <= $max_this_part ) { delete $to_sieve{$base}; $base += $prime; } } while ( my $new_prime = each %to_sieve ) { $prime_cache{$new_prime} = undef; } $max_checked = $max_this_part; } }
      As tall_man and I have discussed, is_prime() isn't really a factor. I had considered both the sieve method as well as C. Given that my candidate numbers reach 100 million in about 40 seconds on my mediocre machine, I prefer keeping it simple (and pure Perl).

      Cheers - L~R

Re: Rotationally Prime Numbers Revisited
by tall_man (Parson) on Mar 25, 2005 at 00:20 UTC
    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.
      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; }
Re: Rotationally Prime Numbers Revisited
by dHarry (Abbot) on Aug 07, 2008 at 08:41 UTC

    This is a fairly old threat but being a number geek myself I would like to add something anyway. First of all I use the term "Circular Primes" instead of "Rotationally Primes" because that seems to be the official name in literature.

    There might be an additional "trick" to filter out numbers that cannot be circular prime instead of doing some prime test on each cyclic permutation (worst case).

    I recently read paper on absolute primes (sometimes also called permutable primes) by A. Slinko. The rules for absolute primes are even more restrictive, i.e. every possible permutation (instead of only every cyclic permutation) should also result in a prime number. In this paper a survey is given of all known facts referring to absolute primes different from repunits.

    Some facts
    1. A multidigit absolute prime contains in its decimal representations only the four digits 1, 3, 7, 9. The same applies to cyclic primes and your program already takes this into account (0, 2, 4, 5, 6, 8 are impossible for obvious reasons).

    A second theorem is less trivial:
    2. An absolute prime does not contain in its decimal representation all of the digits 1, 3, 7, 9 simultaneously. In short the proof takes a certain permutation of the digits constructing a number that has a divisor. Now the proof no longer holds for cyclic primes (e.g. 71993 is a counter example) but it would apply to a subset of numbers (Maybe the proof could be modified to cater for a certain subset of cyclic prime canidates).

    Then this could be implemented for cyclic primes as well, i.e. short-circuit if some pattern of digits 1,3,7 and 9 occurs in the number.

    Now to get back to your original question: If you really want to find the next one your program needs modifications:

    • The standard Perl numbers are nowhere near big enough (I was looking for palindromes in different bases and Math::BigInt seems mandatory).
    • A different prime test, when the numbers get bigger you run into problems.

    With a little bad luck R19 is the first candidate. The first really interesting candidate is R49081. For this giant number it is still unknown if it is prime or not. Although the real challenge would be to find a circular prime that’s not a repunit.

    Sorry for the long post

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://442179]
Approved by kvale
Front-paged by ww
[choroba]: the maintainer of the upstream repo than "merges" the pull request, i.e. they pull from your fork into the upstream
[Discipulus]: ' i.e. you asked them to pull from your repo' =~ I (subj) want to push
[Discipulus]: chorobayour words are reasonable
[choroba]: I'm just repeating some else's words as I remembered them after having asked the same question
[choroba]: s/some/someone/
Discipulus what a pity all people do not speak only in eatalian..
[choroba]: we'd need video calls more often :)
[Discipulus]: i still suspect english has some logical 'curvature/ crookedness' that has and will have a big impact over programming

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (6)
As of 2017-05-27 20:17 GMT
Find Nodes?
    Voting Booth?