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
Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Qi Cheng, Primality Proving via One Round in ECPP and One Iteration in AKS. Journal of Cryptology 20:3 (2007), pp. 375-387. arXiv:math/0301179
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
Charles R Greathouse IV, Mar 04 2011
STATUS
approved