|
%I #67 May 20 2023 12:48:03
%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="https://web.archive.org/web/20160317102203/http://eprints.maths.ox.ac.uk/166/1/linnik.pdf">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
|
