OFFSET
1,1
COMMENTS
All terms seem to be primes of the form a(n) = k*prime(n)+1 for some k.
Is this a duplicate of A035095? - R. J. Mathar, Dec 13 2008
For the first 5*10^6 terms, a(n) = A035095(n). - Donovan Johnson, Oct 21 2011
Comments on the relationship between A035095, A066674, A125878, added by N. J. A. Sloane, Jan 07 2013: (Start)
It is immediate from the definitions that a(n) <= b(n) and a(n) <= c(n).
Bjorn Poonen (Jan 06 2013) makes the following observations:
1) A prime p divides phi(m) if and only if p^2 | m or p | q-1 for some prime q | m. Thus the smallest m for p is either p^2 or the smallest prime q = 1 (mod p). In other words, a(n) = min(b(n),p(n)^2).
2) In particular, the m in the definition of a(n) is at most p(n)^2, so phi(m)/p(n) < p(n), so p(n) is the largest prime dividing phi(m), and phi(m)/(2 p(n)) < p(n)/2 < p(n-1), so p(n-1) does not divide phi(m)/2.
Thus c(n) = a(n).
Further comments from Eric Bach, Jan 07 2013: (Start)
As others have pointed out, the possible equivalence of a(n) and b(n) is basically the question of how quickly the least prime q == 1 mod p grows, as a function of p. In particular, if q < p^2, the two sequences are the same.
Here are some remarks connected with this.
1. There are probabilistic arguments suggesting that q = O(p (log p)^2). See Heath-Brown (1978), Wagstaff (1979), Bach and Huelsbergen (1993). Using the sieve of Eratosthenes, I found no exceptions to q < p^2 below p = 1254767. So it seems likely that a(n) and b(n) are the same.
2. If ERH holds, then q = O(p log p)^2, see Heath-Brown (1990), (1992). Explicitly, on the same hypothesis, q < 2(p log p)^2, see Bach and Sorenson (1996).
3. By Linnik's theorem, q = O(p^c) for some c > 0. This is unconditional, but the best known value of c, equal to 5.18 -- see Xylouris (2011) -- is nowhere near 2. Heath-Brown (1992) mentions the conjecture (generalized to Linnik's theorem) that q <= p^2. If true, a(n) and b(n) are identical, since p^2 cannot be 1 mod p. (End)
Summary: A066674 and A125878 are the same, and A035095 is probably also the same, but this is an open question.
(End)
REFERENCES
E. Bach and J. Shallit, Algorithmic Number Theory, Vol. 1: Efficient Algorithms, MIT Press, Cambridge, MA, 1996.
LINKS
Robert G. Wilson v, Table of n, a(n) for n = 1..10000
E. Bach and L. Huelsbergen, Statistical evidence for small generating sets, Math. Comp. 61 (1993) 69-82.
E. Bach and J. Sorenson, Explicit bounds for primes in residue classes, Math. Comp. 65, 1996, pp. 1717-1735.
D. R. Heath-Brown, Almost-primes in arithmetic progressions and short intervals, Math. Proc. Cambridge Phil. Soc., 83:357--375, 1978.
D. R. Heath-Brown, Siegel zeros and the least prime in an arithmetic progression, Quart. J. Math. Oxford (2) 41, 1990, 405-418.
D. R. Heath-Brown, Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression, Proc. London Math. Soc. 64(3) (1992), pp. 265-338.
S. S. Wagstaff, Jr, Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus, Math. Comp., 33 (147) (1979) pp. 1073-1080.
T. Xylouris, On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions, Acta Arith. 150 (2011), no. 1, 65-91.
FORMULA
a(n) = min{m : phi(m) = 0 mod prime(n) = 0}.
MATHEMATICA
f[n_] := Block[{m = p = Prime@ n}, While[ Mod[ EulerPhi@ m, p] != 0, m += 2]; m]; f[1] = 3; Array[f, 60] (* Robert G. Wilson v, Dec 27 2014 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Labos Elemer, Dec 19 2001
EXTENSIONS
a(2) corrected by R. J. Mathar, Dec 13 2008
STATUS
approved