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

Indeed, I'd argue they're more likely to be primes: numbers of the form M(a, p) = (a^p - 1)/(a - 1) form an extended class of Mersenne numbers, and in particular will not share a factor with any M(a, q), q < p, and draw their factors from the restricted set {p, <2kp + 1>}.

I don't know if there's a way to adapt the Lucas-Lehmer test to check directly for divisors in this extended class.

Hugo

Replies are listed 'Best First'.
Re^5: Rotationally Prime Numbers Revisited
by tilly (Archbishop) on Mar 25, 2005 at 19:33 UTC
    While they may be more likely to be primes, I'm not convinced that the effect is that large. True, possible factors are restricted, but numbers in that set of possible factors are far, far more likely to be divisors than mere chance would predict. How do these balance out? It certainly isn't obvious to me.

    Let's do some heuristics. the 38'th Mersenne prime is 2**6972593-1. Naively from the Prime Number theorem you'd expect to find an average of 22.12 primes in that sequence to that point. We actually got 38. So we got about 70% more primes than we were expecting to have. The limited results that we have for (10**p-1)/9 suggest a similar advantage.

    Which is significant, but not astoundingly different than the naive approximation.

[reply]

In Section Seekers of Perl Wisdom