login
Good primes (version 3): p such that p-1 has a prime factor between (log p)^2 and 2 (log p)^2.
1

%I #15 Mar 18 2017 14:12:59

%S 3,23,47,59,149,173,223,283,367,431,439,569,659,709,733,743,827,853,

%T 877,941,977,997,1061,1063,1069,1163,1181,1279,1423,1553,1607,1609,

%U 1709,1747,1753,1831,1847,1877,1889,1993,2011,2131,2137,2141,2213,2267,2273,2371,2399

%N Good primes (version 3): p such that p-1 has a prime factor between (log p)^2 and 2 (log p)^2.

%C 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.

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

%C 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....

%H Charles R Greathouse IV, <a href="/A187094/b187094.txt">Table of n, a(n) for n = 1..10000</a>

%H Qi Cheng, <a href="http://www.cs.ou.edu/~qcheng/paper/aksimp.pdf">Primality Proving via One Round in ECPP and One Iteration in AKS</a>. Journal of Cryptology 20:3 (2007), pp. 375-387. <a href="http://arxiv.org/abs/math/0301179">arXiv:math/0301179</a>

%F 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.

%e 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.

%t 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 *)

%o (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

%o select(good, primes(1000)) \\ in older versions use select(primes(1000), good)

%K nonn

%O 1,1

%A _Charles R Greathouse IV_, Mar 04 2011