Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?

Re^2: Rotationally Prime Numbers Revisited

by Limbic~Region (Chancellor)
on Mar 25, 2005 at 00:30 UTC ( #442233=note: print w/replies, xml ) Need Help??

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

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.
  • Comment on Re^2: Rotationally Prime Numbers Revisited

Replies are listed 'Best First'.
Re^3: Rotationally Prime Numbers Revisited
by tilly (Archbishop) on Mar 25, 2005 at 01:21 UTC
    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

      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

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://442233]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (3)
As of 2019-06-19 05:20 GMT
Find Nodes?
    Voting Booth?
    Is there a future for codeless software?

    Results (84 votes). Check out past polls.

    • (Sep 10, 2018 at 22:53 UTC) Welcome new users!