This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A066674 Least number m such that phi(m) = A000010(m) is divisible by the n-th 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 | 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. 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 = 3; Array[f, 60] (* Robert G. Wilson v, Dec 27 2014 *) CROSSREFS Cf. A000010, A000040, A066675-A066678, A035095. Cf. also A074884 and A117673. Sequence in context: A051202 A211674 A035095 * A125878 A126112 A194373 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 16 20:33 EDT 2019. Contains 327118 sequences. (Running on oeis4.)