|
| |
|
|
A187094
|
|
Good primes (version 3): p such that p-1 has a prime factor between (log p)^2 and 2 (log p)^2.
|
|
1
|
|
|
|
3, 23, 47, 59, 149, 173, 223, 283, 367, 431, 439, 569, 659, 709, 733, 743, 827, 853, 877, 941, 977, 997, 1061, 1063, 1069, 1163, 1181, 1279, 1423, 1553, 1607, 1609, 1709, 1747, 1753, 1831, 1847, 1877, 1889, 1993, 2011, 2131, 2137, 2141, 2213, 2267, 2273, 2371, 2399
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
The notation can be generalized: call n an (a,b)-good number if n-1 has a prime factor in [a * log(p)^2, b * log(p)^2]. In that case these are (1,2)-good primes.
Related to AKS-class primality proving: in particular, these primes can be directly (that is, without an ECPP reduction) proved prime by Cheng's version of AKS in time O((log n)^(4+eps)).
Cheng conjectures that there is a positive constant lambda such that the fraction of primes in (n - 2 sqrt(n) + 1, n + 2 sqrt(n) + 1) that are members of this sequence is greater than lambda/log log n for all sufficiently large n. If it exists, lambda <= (log 2)/2 = 0.346....
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) ~ n log n log log n / log 2. More generally, Cheng proves that there are pi(x) log(b/a)/(2 log log x) * (1 + O(1/log log x)) (a,b)-good primes up to x.
|
|
|
EXAMPLE
|
log(23)^2 is about 9.8, so 23 is good if 22 has a prime factor between 10 and 19 inclusive. 11 | (23 - 1) so 23 is a member of this sequence.
|
|
|
MATHEMATICA
|
pflpQ[n_]:=Module[{c=Log[n]^2}, AnyTrue[FactorInteger[n-1][[All, 1]], IntervalMemberQ[ Interval[{c, 2c}], #]&]]; Select[Prime[Range[ 400]], pflpQ] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Mar 18 2017 *)
|
|
|
PROG
|
(PARI) good(p)=my(f=factor(p-1)[, 1], l2=log(p)^2); for(i=1, #f, if(f[i]>l2&f[i]<l2*2, return(1))); 0
select(good, primes(1000)) \\ in older versions use select(primes(1000), good)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
