A066674 Least number m such that phi(m) = A000010(m) is divisible by the n-th prime.

3, 7, 11, 29, 23, 53, 103, 191, 47, 59, 311, 149, 83, 173, 283, 107, 709, 367, 269, 569, 293, 317, 167, 179, 389, 607, 619, 643, 1091, 227, 509, 263, 823, 557, 1193, 907, 1571, 653, 2339, 347, 359, 1087, 383, 773, 3547, 797, 2111, 2677, 5449, 2749, 467

Offset: 1

Author

Labos Elemer, Dec 19 2001

Keywords

• nonn

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)

Let a(n) = A066674(n), b(n) = A035095(n), c(n) = A125878(n).

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)

Don Reble (Jan 07 2013) observes that A074884 and A117673 are related to these questions.

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.

Crossrefs

Cf. A000010, A000040, A066675-A066678, A035095.

Cf. also A074884 and A117673.

Programs

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

Formula

a(n) = min{m : phi(m) = 0 mod prime(n) = 0}.

Extensions

a(2) corrected by R. J. Mathar, Dec 13 2008