login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

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[1] = 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: 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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified November 23 09:54 EST 2017. Contains 295116 sequences.