cp's OEIS Frontend

A035095 Smallest prime congruent to 1 (mod prime(n)).

%I A035095 #90 Apr 29 2025 04:53:37
%S A035095 3,7,11,29,23,53,103,191,47,59,311,149,83,173,283,107,709,367,269,569,
%T A035095 293,317,167,179,389,607,619,643,1091,227,509,263,823,557,1193,907,
%U A035095 1571,653,2339,347,359,1087,383,773,3547,797,2111,2677,5449,2749,467
%N A035095 Smallest prime congruent to 1 (mod prime(n)).
%C A035095 This is a version of the "least prime in special arithmetic progressions" problem.
%C A035095 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 A035095 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 A035095 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 A035095 Conjecture: a(n) is the smallest prime p such that gpf(p-1) = prime(n). See A023503. - _Thomas Ordowski_, Aug 06 2017
%C A035095 For n>1, a(n) is the smallest prime congruent to 1 mod (2*prime(n)). - _Chai Wah Wu_, Apr 28 2025
%D A035095 E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Bd 1 (reprinted Chelsea 1953).
%D A035095 E. C. Titchmarsh, A divisor problem, Renc. Circ. Math. Palermo, 54 (1930) pp. 414-429.
%D A035095 P. Turan, Über Primzahlen der arithmetischen Progression, Acta Sci. Math. (Szeged), 8 (1936/37) pp. 226-235.
%H A035095 T. D. Noe, <a href="/A035095/b035095.txt">Table of n, a(n) for n = 1..10000</a>
%H A035095 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 A035095 A. Granville and C. Pomerance, <a href="https://citeseerx.ist.psu.edu/pdf/1d2c19b5d29b506db045b0389d4c7ec57dbd5fc5">On the least prime in certain arithmetic progressions</a>
%H A035095 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 A035095 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 A035095 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 A035095 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 A035095 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 A035095 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 A035095 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 A035095 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 A035095 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 A035095 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 A035095 <a href="/index/Pri#primes_AP">Index entries for sequences related to primes in arithmetic progressions</a>
%F A035095 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 A035095 a(n) = 1 + A035096(n)*A000040(n). - _Zak Seidov_, Dec 27 2013
%e A035095 a(8) = 191 because in the prime(8)k+1 = 19k+1 sequence, 191 is the smallest prime.
%t A035095 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 A035095 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 A035095 (PARI) a(n)=local(p,r);p=prime(n);r=1;while(!isprime(r),r+=p);r
%o A035095 (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
%o A035095 (Python)
%o A035095 from itertools import count
%o A035095 from sympy import prime, isprime
%o A035095 def A035095(n): return 3 if n==1 else next(filter(isprime,count((p:=prime(n)<<1)+1,p))) # _Chai Wah Wu_, Apr 28 2025
%Y A035095 Cf. A034694, A032448, A006530, A006093, A035096, A000040, A019434, A058383.
%Y A035095 Cf. A068211, A068212, A065966, A000010, A070844-A070858, A061092.
%Y A035095 Cf. A000040.
%K A035095 nonn
%O A035095 1,1
%A A035095 _Labos Elemer_
%E A035095 Edited by _Franklin T. Adams-Watters_, Jun 18 2010
%E A035095 Minor edits by _N. J. A. Sloane_, Jun 27 2010
%E A035095 Edited by _N. J. A. Sloane_, Jan 05 2013