

A066674


Least number m such that phi(m) = A000010(m) is divisible by the nth prime.


10



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

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  q1 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(n1), so p(n1) 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 HeathBrown (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 HeathBrown (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. HeathBrown (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) 6982.
E. Bach and J. Sorenson, Explicit bounds for primes in residue classes, Math. Comp. 65, 1996, pp. 17171735.
D. R. HeathBrown, Almostprimes in arithmetic progressions and short intervals, Math. Proc. Cambridge Phil. Soc., 83:357375, 1978.
D. R. HeathBrown, Siegel zeros and the least prime in an arithmetic progression, Quart. J. Math. Oxford (2) 41, 1990, 405418.
D. R. HeathBrown, Zerofree regions for Dirichlet Lfunctions, and the least prime in an arithmetic progression, Proc. London Math. Soc. 64(3) (1992), pp. 265338.
S. S. Wagstaff, Jr, Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus, Math. Comp., 33 (147) (1979) pp. 10731080.
T. Xylouris, On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet Lfunctions, Acta Arith. 150 (2011), no. 1, 6591.


FORMULA

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


EXAMPLE

All terms seem to be primes of the form a(n) = k*prime(n)+1 for some k.


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

Cf. A000010, A000040, A066675A066678, A035095.
Cf. also A074884 and A117673.
Sequence in context: A211674 A035095 * A125878 A126112 A194373 A156210
Adjacent sequences: A066671 A066672 A066673 * A066675 A066676 A066677


KEYWORD

nonn


AUTHOR

Labos Elemer, Dec 19 2001


EXTENSIONS

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


STATUS

approved



