A035095 - OEIS

%I #85 Aug 06 2024 08:49:56

%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 Smallest prime congruent to 1 (mod prime(n)).

%C This is a version of the "least prime in special arithmetic progressions" problem.

%C Smallest numbers m such that largest prime factor of Phi(m) = prime(n), the n-th prime, also seems to be prime and identical to n-th term of A035095. See A068211, A068212, A065966: Min[x : A068211(x)=prime(n)] = A035095(n); e.g., Phi(a(7)) = Phi(103) = 2*3*17, of which 17 = p(7) is the largest prime factor, arising first here.

%C It appears that A035095, A066674, A125878 are probably all the same, but see the comments in A066674. - _N. J. A. Sloane_, Jan 05 2013

%C Minimum of the smallest prime factors of F(n,i) = (i^prime(n)-1)/(i-1), when i runs through all integers in [2, prime(n)]. Every prime factor of F(n,i) is congruent to 1 modulo prime(n). - _Vladimir Shevelev_, Nov 26 2014

%C Conjecture: a(n) is the smallest prime p such that gpf(p-1) = prime(n). See A023503. - _Thomas Ordowski_, Aug 06 2017

%D E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Bd 1 (reprinted Chelsea 1953).

%D E. C. Titchmarsh, A divisor problem, Renc. Circ. Math. Palermo, 54 (1930) pp. 414-429.

%D P. Turan, Uber Primzahlen der arithmetischen Progression, Acta Sci. Math. (Szeged), 8 (1936/37) pp. 226-235.

%H T. D. Noe, <a href="/A035095/b035095.txt">Table of n, a(n) for n = 1..10000</a>

%H P. Erdős, <a href="http://acta.fyx.hu/acta/showCustomerArticle.action?id=5970&amp;dataObjectType=article&amp;sessionDataSetId=28afa5176abeef7e">On some application of Brun's method</a>, Acta Sci. Math (Szeged), v. 13, 1949, pp. 57-63.

%H A. Granville and C. Pomerance, <a href="https://citeseerx.ist.psu.edu/pdf/1d2c19b5d29b506db045b0389d4c7ec57dbd5fc5">On the least prime in certain arithmetic progressions</a>

%H A. Granville and C. Pomerance, <a href="http://dx.doi.org/10.1112/jlms/s2-41.2.193">On the least prime in certain arithmetic progressions</a> J. Lond Math Soc s2-41 (2) (1990), pp. 193-200.

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

%H D. R. Heath-Brown, <a href="http://dx.doi.org/10.1093/qmath/41.4.405">Siegel zeros and the least prime in arithmetic progression</a>, Quart. J. of Math 41 (49) (1990), pp. 405-418.

%H H.-J. Kanold, <a href="http://dx.doi.org/10.1007/BF01362452">Uber Primzahlen in arithmetischen Folgen</a>, Math. Ann. v 156 (1964) pp. 393-395.

%H U. V. Linnik, On the least prime in an arithmetic progression. I. The basic theorem, Rec. Math (N.S.) v 15 (57) (1944), pp 139-178. <a href="http://www.ams.org/mathscinet-getitem?mr=12111">MR0012111</a>

%H C. Pomerance, <a href="http://dx.doi.org/10.1016/0022-314X(80)90056-6">A note on the least prime in an arithmetic progression</a> J. Number Theory 12 (2) (1980), pp. 218-223.

%H K. Prachar, <a href="http://dx.doi.org/10.1515/crll.1961.206.3">Uber die kleinste Primzahl in einer arithmetischen Reihe</a>, J Reine Angew Math. 206 (1961) pp. 3-4.

%H A. Schinzel, <a href="http://dx.doi.org/10.1515/crll.1962.210.121">Remark on the paper of K. Prachar Uber die kleinste..</a>, J. Reine Angew Math. v 210 (1962) pp. 122-122.

%H S. S. Wagstaff, Jr., <a href="http://dx.doi.org/10.1090/S0025-5718-1978-0491465-4">The irregular primes to 125000</a>, Math. Comp., 32 (1978) pp. 583-591.

%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 <a href="/index/Pri#primes_AP">Index entries for sequences related to primes in arithmetic progressions</a>

%F According to a long-standing conjecture (see the 1979 Wagstaff reference), a(n) <= prime(n)^2 + 1. This would be sufficient to imply that a(n) is the smallest prime such that greatest prime divisor of a(n)-1 is prime(n), the n-th prime: A006530(a(n)-1) = A000040(n). This in turn would be sufficient to imply that no value occurs twice in this sequence. - _Franklin T. Adams-Watters_, Jun 18 2010

%F a(n) = 1 + A035096(n)*A000040(n). - _Zak Seidov_, Dec 27 2013

%e a(8) = 191 because in the prime(8)k+1 = 19k+1 sequence, 191 is the smallest prime.

%t a[n_] := Block[{p = Prime[n]}, r = 1 + p; While[ !PrimeQ[r], r += p]; r]; Array[a, 51] (* _Jean-François Alcover_, Sep 20 2011, after PARI *)

%t a[n_]:=If[n<2,3,Block[{p=Prime[n]},r=1+2*p;While[!PrimeQ[r],r+=2*p]];r];Array[a,51] (* _Zak Seidov_, Dec 14 2013 *)

%o (PARI) a(n)=local(p,r);p=prime(n);r=1;while(!isprime(r),r+=p);r

%o (PARI) {my(N=66); forprime(p=2, , forprime(q=p+1,10^10, if((q-1)%p==0, print1(q,", "); N-=1; break)); if(N==0,break)); } \\ _Joerg Arndt_, May 27 2016

%Y Cf. A034694, A032448, A006530, A006093, A035096, A000040, A019434, A058383.

%Y Cf. A068211, A068212, A065966, A000010, A070844-A070858, A061092.

%Y Cf. A000040.

%K nonn

%O 1,1

%A _Labos Elemer_

%E Edited by _Franklin T. Adams-Watters_, Jun 18 2010

%E Minor edits by _N. J. A. Sloane_, Jun 27 2010

%E Edited by _N. J. A. Sloane_, Jan 05 2013