The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(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


%S 3,7,11,29,23,53,103,191,47,59,311,149,83,173,283,107,709,367,269,569,

%T 293,317,167,179,389,607,619,643,1091,227,509,263,823,557,1193,907,

%U 1571,653,2339,347,359,1087,383,773,3547,797,2111,2677,5449,2749,467

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

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

%C Is this a duplicate of A035095? - _R. J. Mathar_, Dec 13 2008

%C For the first 5*10^6 terms, a(n) = A035095(n). - _Donovan Johnson_, Oct 21 2011

%C Comments on the relationship between A035095, A066674, A125878, added by _N. J. A. Sloane_, Jan 07 2013: (Start)

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

%C It is immediate from the definitions that a(n) <= b(n) and a(n) <= c(n).

%C Bjorn Poonen (Jan 06 2013) makes the following observations:

%C 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).

%C 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.

%C Thus c(n) = a(n).

%C Further comments from Eric Bach, Jan 07 2013: (Start)

%C 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.

%C Here are some remarks connected with this.

%C 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.

%C 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).

%C 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)

%C _Don Reble_ (Jan 07 2013) observes that A074884 and A117673 are related to these questions.

%C Summary: A066674 and A125878 are the same, and A035095 is probably also the same, but this is an open question.

%C (End)

%D E. Bach and J. Shallit, Algorithmic Number Theory, Vol. 1: Efficient Algorithms, MIT Press, Cambridge, MA, 1996.

%H Robert G. Wilson v, <a href="/A066674/b066674.txt">Table of n, a(n) for n = 1..10000</a>

%H E. Bach and L. Huelsbergen, <a href="http://dx.doi.org/10.1090/S0025-5718-1993-1195432-5 ">Statistical evidence for small generating sets</a>, Math. Comp. 61 (1993) 69-82.

%H E. Bach and J. Sorenson, <a href="http://dx.doi.org/10.1090/S0025-5718-96-00763-6">Explicit bounds for primes in residue classes</a>, Math. Comp. 65, 1996, pp. 1717-1735.

%H D. R. Heath-Brown, <a href="http://dx.doi.org/10.1017/S0305004100054657">Almost-primes in arithmetic progressions and short intervals</a>, Math. Proc. Cambridge Phil. Soc., 83:357--375, 1978.

%H D. R. Heath-Brown, <a href="http://qjmath.oxfordjournals.org/content/41/4/405.extract">Siegel zeros and the least prime in an arithmetic progression</a>, Quart. J. Math. Oxford (2) 41, 1990, 405-418.

%H D. R. Heath-Brown, <a href="http://eprints.maths.ox.ac.uk/166/">Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression</a>, Proc. London Math. Soc. 64(3) (1992), pp. 265-338.

%H S. S. Wagstaff, Jr, <a href="http://dx.doi.org/10.1090/S0025-5718-1979-0528061-7">Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus</a>, Math. Comp., 33 (147) (1979) pp. 1073-1080.

%H T. Xylouris, <a href="http://dx.doi.org/10.4064/aa150-1-4">On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions</a>, Acta Arith. 150 (2011), no. 1, 65-91.

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

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

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

%Y Cf. also A074884 and A117673.

%K nonn

%O 1,1

%A _Labos Elemer_, Dec 19 2001

%E a(2) corrected by _R. J. Mathar_, Dec 13 2008

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 10 02:39 EDT 2020. Contains 333392 sequences. (Running on oeis4.)