Re^2: Rotationally Prime Numbers Revisited

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.)

Comment on Re^2: Rotationally Prime Numbers Revisited

Replies are listed 'Best First'.
Re^3: Rotationally Prime Numbers Revisited by ambrus (Abbot) on Mar 25, 2005 at 09:40 UTC
As we all know, (10n-1)/9 is surely not a prime when n is composed, because (10(kl)-1)/9 = ((10(kl)-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.	[reply]
Re^4: Rotationally Prime Numbers Revisited by hv (Prior) on Mar 25, 2005 at 12:54 UTC
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	[reply] [d/l] [select]
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 26972593-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 (10p-1)/9 suggest a similar advantage. Which is significant, but not astoundingly different than the naive approximation.	[reply]