A061092 -id:A061092 - cp's OEIS frontend

A121799 Values of k from A061092.

1, 1, 2, 4, 2, 12, 4, 8, 26, 2, 8, 18, 16, 2, 6, 12, 4, 32, 30, 6, 40, 60, 22, 12, 208, 18, 48, 168, 18, 76, 6, 232, 48, 4, 50, 78, 28, 236, 68, 1026, 10, 162, 6, 138, 162, 48, 120, 330, 82, 414, 130, 188, 164, 6, 6, 100, 126, 10, 36, 40, 48, 94, 14, 218, 954

Offset: 1

Zak Seidov, Oct 26 2005, Dec 14 2006

nonn

A061092 is: a(0) = 1; for n>0 a(n) is the smallest prime, larger than a(n-1), of the form k*a(n-1) + 1. - Corrected by Zak Seidov, Oct 03 2015

Ken Takusagawa, Table of n, a(n) for n = 1..3000 (terms 1..200 from T. D. Noe)

Cf. A061092, A072532, A113334.

a = {2}; b = {1}; Do[k = 1; p = a[[n - 1]]; While[! PrimeQ[k p + 1], k++]; AppendTo[a, k p + 1]; AppendTo[b, k], {n, 2, 60}]; b (* Michael De Vlieger, Oct 03 2015, after Robert G. Wilson v at A061092 *)

a(n) = (A061092(n)-1)/A061092(n-1). - Zak Seidov, Oct 03 2015

Definition corrected by Ken Takusagawa, Jan 17 2006
Corrected and extended by T. D. Noe, Mar 10 2007
Edited by N. J. A. Sloane, Aug 08 2008 at the suggestion of R. J. Mathar

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

Original entry on oeis.org

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

Offset: 1

Labos Elemer

nonn

This is a version of the "least prime in special arithmetic progressions" problem.
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.
It appears that A035095, A066674, A125878 are probably all the same, but see the comments in A066674. - N. J. A. Sloane, Jan 05 2013
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
Conjecture: a(n) is the smallest prime p such that gpf(p-1) = prime(n). See A023503. - Thomas Ordowski, Aug 06 2017
For n>1, a(n) is the smallest prime congruent to 1 mod (2*prime(n)). - Chai Wah Wu, Apr 28 2025

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

E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Bd 1 (reprinted Chelsea 1953).
E. C. Titchmarsh, A divisor problem, Renc. Circ. Math. Palermo, 54 (1930) pp. 414-429.
P. Turan, Über Primzahlen der arithmetischen Progression, Acta Sci. Math. (Szeged), 8 (1936/37) pp. 226-235.

T. D. Noe, Table of n, a(n) for n = 1..10000
P. Erdős, On some application of Brun's method, Acta Sci. Math (Szeged), v. 13, 1949, pp. 57-63.
A. Granville and C. Pomerance, On the least prime in certain arithmetic progressions
A. Granville and C. Pomerance, On the least prime in certain arithmetic progressions J. Lond Math Soc s2-41 (2) (1990), pp. 193-200.
D. R. Heath-Brown, almost-primes in arithmetic progressions in short intervals, Math Proc Cambr. Phil Soc v 83 (1978), pp. 357-375.
D. R. Heath-Brown, Siegel zeros and the least prime in arithmetic progression, Quart. J. of Math 41 (49) (1990), pp. 405-418.
H.-J. Kanold, Uber Primzahlen in arithmetischen Folgen, Math. Ann. v 156 (1964) pp. 393-395.
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. MR0012111
C. Pomerance, A note on the least prime in an arithmetic progression J. Number Theory 12 (2) (1980), pp. 218-223.
K. Prachar, Uber die kleinste Primzahl in einer arithmetischen Reihe, J Reine Angew Math. 206 (1961) pp. 3-4.
A. Schinzel, Remark on the paper of K. Prachar Uber die kleinste.., J. Reine Angew Math. v 210 (1962) pp. 122-122.
S. S. Wagstaff, Jr., The irregular primes to 125000, Math. Comp., 32 (1978) pp. 583-591.
S. S. Wagstaff, Jr, Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus, Math. Comp., 33 (147) (1979) pp. 1073-1080.
Index entries for sequences related to primes in arithmetic progressions

Cf. A034694, A032448, A006530, A006093, A035096, A000040, A019434, A058383.
Cf. A068211, A068212, A065966, A000010, A070844-A070858, A061092.
Cf. A000040.

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

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

{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

from itertools import count
from sympy import prime, isprime
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

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

a(n) = 1 + A035096(n)*A000040(n). - Zak Seidov, Dec 27 2013

Edited by Franklin T. Adams-Watters, Jun 18 2010
Minor edits by N. J. A. Sloane, Jun 27 2010
Edited by N. J. A. Sloane, Jan 05 2013

A059411 a(1) = 2, a(n) = ka(n-1) + 1, where a(n) is the smallest prime of the form ka(n-1) + 1 and k > 1.

Original entry on oeis.org

2, 5, 11, 23, 47, 283, 1699, 20389, 244669, 7340071, 205521989, 411043979, 4932527749, 295951664941, 4735226639057, 227290878674737, 12273707448435799, 883706936287377529, 24743794216046570813

Offset: 1

Labos Elemer, Jan 30 2001

nonn

A sequence of primes generated recursively as follows: a(n+1) = q(n)*a(n)+1, where q=q(n) is the smallest (even) number such that a(n+1) = q*a(n)+1 is prime and the initial value a(1)=2. q(n) = (a(n+1) - 1)/a(n) is the satellite "almost-quotient-sequence".
It has been established in the Murthy reference that for every prime p there exists at least one prime of the form k*p +1. Hence the sequence is infinite. - Amarnath Murthy, Mar 02 2002
The existence of a prime of the form k*p+1 follows from Dirichlet's theorem (1837). - T. D. Noe, Mar 14 2009

			a(5) = 47 and a(6) = 283 = 6*47 +1 is the smallest such prime.
The initial values are safe primes: (2), 5, 11, 23, 47, ... To obtain qa(i)+1 primes q > 2 multiplier arises and such a q always exists in arithmetic progression of difference a(i). E.g., {1699*2k+1} gives the first prime when 2k=12. So a(7)=1699 is followed by 1699*12+1 = 20389 = a(8). The emergent "quotient-sequence" is {2, 2, 2, 2, 6, 6, 12, 12, 30, 28, 2, 12, 60, 16, 48, 54, 72, 28, 180, 102, 4, 12, 106, 50, 18}. A059411 is an infinite sequence of primes increasing at least with exponential speed.

Amarnath Murthy, On the divisors of Smarandache Unary Sequence. Smarandache Notions Journal, Vol. 11, No. 1-2-3, Spring 2000.

T. D. Noe, Table of n, a(n) for n = 1..100

Cf. A061092.

i := 0:a[0] := 2:while(i<40) do k := 2:while(not isprime(k*a[i]+1)) do k := k+1; end do; i := i+1; a[i] := k*a[i-1]+1; end do:q := seq(a[i],i=0..39);

nxt[n_]:=Module[{k=2},While[!PrimeQ[k*n+1],k++];k*n+1]; NestList[nxt,2,20] (* Harvey P. Dale, Dec 26 2014 *)

a(n+1) = a(n)*q(n) + 1, q(n) = Min{q|qa(n)+1 is prime}.

A071580 Smallest prime of the form ka(n-1)a(n-2)...a(1)+1.

Original entry on oeis.org

2, 3, 7, 43, 3613, 65250781, 5109197227031017, 21753246920584523633819544186061, 993727878334632126576336773629979379563850938567846991629270287

Offset: 1

Rick L. Shepherd, May 31 2002

nonn

The former definition was "Smallest prime == 1 mod (a(n-1)*a(n-2)*...*a(1)) for n>=2 with a(1)=2."
a(6) through a(13), with digit lengths 8, 16, 32, 63, 127, 253, 507 and 1012, respectively, have been certified prime with Primo.
There is no need to use Elliptic curve primality proving (ECPP) to certify the primes. The primality of each term can be proved recursively with the "N-1 method" since the full factorization of a(n)-1 is known. - Jeppe Stig Nielsen, May 14 2023

Joerg Arndt, Table of n, a(n) for n = 1..13
Mersenne Forum, A071580

Cf. A061092, A258081.

P:= 1:
for n from 1 to 13 do
  for k from 1 do
     if isprime(k*P+1) then
       A[n]:= k*P+1;
       P:= P * A[n];
       break
     fi
  od
od:
seq(A[i],i=1..13); # Robert Israel, May 19 2015

sp[{p_,a_}]:=Module[{k=1},While[!PrimeQ[k*p+1],k++];{p(p*k+1),p*k+1}]; NestList[sp,{2,2},10][[All,2]] (* Harvey P. Dale, Mar 04 2019 *)

terms=13; v=vector(terms); p=2; v[1]=p; for(n=2,terms, q=p+1; while(!isprime(q), q=q+p); v[n]=q; p=p*q); v

Definition reworded by Andrew R. Booker, May 19 2015

A072532 a(0)=1; for n>0, a(n) = smallest prime of the form k*a(n-1)-1 with k>1.

Original entry on oeis.org

1, 2, 3, 5, 19, 37, 73, 1021, 8167, 16333, 326659, 3919907, 47038883, 188155531, 2257866371, 76767456613, 1535349132259, 12282793058071, 147393516696851, 4127018467511827, 107302480155307501, 1502234722174305013

Offset: 0

Amarnath Murthy, Aug 02 2002

Conjecture: If a(n) = k*a(n-1)-1 then k < a(n-1).

A theorem of Dirichlet shows the sequence to be infinite. - Don Reble, Aug 03 2002

T. D. Noe, Table of n, a(n) for n=0..100

Cf. A061092.

f[n_]:=Module[{k=2},While[!PrimeQ[k*n-1],k++];k*n-1]; Join[{1}, NestList[ f,2,35]] (* Harvey P. Dale, Jun 27 2011 *)

More terms from Don Reble, Aug 03 2002

A214523 a(1) = 13, a(n) is smallest prime of the form k*a(n-1) + 1.

Original entry on oeis.org

13, 53, 107, 643, 7717, 30869, 432167, 6050339, 12100679, 169409507, 9148113379, 439109442193, 5269313306317, 84309012901073, 7587811161096571, 303512446443862841, 69807862682088453431, 2652698781919361230379, 143245734223645506440467

Offset: 1

Robin Garcia, Jul 23 2012

nonn

Sequence does not begin with a(1) = 2 or 3 (13 = 6*2+1 = 4*3*1; but 2*2+1 =5 or 2*3 +1 = 7 are smaller) , because this would be A061092 or A059411.

			53 = 4*13 + 1 ; 107 = 2*53 + 1.

Harvey P. Dale, Table of n, a(n) for n = 1..300

Cf. A061092, A059411.

t = {13}; Do[k = 1; While[p = k*t[[-1]] + 1; ! PrimeQ[p], k++]; AppendTo[t, p], {20}]; t (* T. D. Noe, Jul 24 2012 *)
nxt[n_]:=Module[{k=1},While[!PrimeQ[k*n+1],k++];n*k+1]; NestList[nxt,13,20] (* Harvey P. Dale, Apr 28 2014 *)

a=13;for(n=1,200,b=a*n+1;if(isprime(b),a=b;print1(a,", ");next(n=1)))

A061303 Given a prime p, let s(p,0)=p and let s(p,n+1) be the smallest prime == 1 (mod s(p,n)). Let S(p) be the sequence {s(p,n): n=0,1,...}. Let a(0)=2 and let a(n+1) be the smallest prime not in any of the sequences S(a(0)), ..., S(a(n)).

Original entry on oeis.org

2, 5, 13, 17, 19, 31, 37, 41, 43, 61, 67, 71, 73, 79, 89, 97, 101, 109, 113, 127, 131, 137, 139, 151, 157, 163, 181, 193, 197, 199, 211, 223, 229, 233, 239, 241, 251, 257, 271, 277, 281, 307, 313, 331, 337, 349, 353, 373, 379, 397, 401, 409, 419, 421, 431, 433

Offset: 0

Amarnath Murthy, Apr 26 2001

nonn

It is conjectured for primes p and q the sequences S(p) and S(q) are disjoint, unless one is contained in the other.
Also values of n such that gcd(n! , phi(n!)) equals gcd((n-1)! , phi((n-1)!)), see proof by Don Reble. - Wouter Meeussen, Mar 18 2014
Primes p such that phi(p) divides phi(Product_{primes q <= p} phi(q)), where phi is A000010. - Richard R. Forberg, Sep 11 2024

			a(0)=2 so S(a(0))={2,3,7,29,...}, which is A061092. Hence a(1)=5 so S(a(1))={5,11,23,47,...}. Hence a(2)=13 so S(a(2))={13,53,107,643,...}, ...

Amarnath Murthy, On the divisors of Smarandache Unary Sequence. Smarandache Notions Journal, Vol. 11, No. 1-2-3, Spring 2000.
Amarnath Murthy, Smarandache Prime Generator Sequence (to be published in Smarandache Notions Journal).

Wouter Meeussen, Don Reble's equivalence proof

Cf. A061092. A000010

(* start *) s[p_, 0] := s[p, 0]=p; s[p_, n_] := s[p, n]=Module[{q}, For[q=s[p, n-1]+1, !PrimeQ[q], q+=s[p, n-1], Null]; q]; ins[q_, p_] := Module[{k}, For[k=0, s[p, k]<=q, k++, If[s[p, k]==q, Return[True]]]; False]; a[0]=2; a[n_] := a[n]=Module[{i, j, q}, For[i=1, True, i++, q=Prime[i]; For[j=0, jWouter Meeussen, Mar 18 2014 *)
result = {}; prodEPP = 1; Do[prodEPP *= EulerPhi[Prime[i]];
 If[Divisible[EulerPhi[prodEPP], EulerPhi[Prime[i]]],
AppendTo[result, Prime[i]]], {i, 1, 1000}]; result  (* Richard R. Forberg, Sep 16 2024 *)

Edited by Dean Hickerson, Jun 09 2002

A214632 a(1) = 17, a(n) is smallest prime of the form k*a(n - 1) + 1.

Original entry on oeis.org

17, 103, 619, 2477, 34679, 416149, 7490683, 29962733, 419478263, 5872695683, 82217739563, 986612874757, 27625160493197, 994505777755093, 5967034666530559, 71604415998366709, 6444397439853003811, 180443128315884106709, 9743928929057741762287

Offset: 1

Robin Garcia, Jul 23 2012

nonn

Sequence does not begin with 2 (17 = 8*2 + 1; all primes are k*2+1) because 3 = 1*2 + 1 or 5 = 2*2 + 1 are smaller; and they would lead to A061092, or A059411. Also: 7 belongs to A061092; 11 to A059411 and 13 is a(1) in A214523.

			a(2) = 103 = 6*17 + 1.

Harvey P. Dale, Table of n, a(n) for n = 1..300

Cf. A061092, A059411, A214523.

t = {17}; Do[k = 1; While[p = k*t[[-1]] + 1; ! PrimeQ[p], k++]; AppendTo[t, p], {20}]; t (* T. D. Noe, Jul 24 2012 *)
nxt[n_]:=Module[{k=1},While[!PrimeQ[k*n+1],k++];k*n+1]; NestList[nxt,17,20] (* Harvey P. Dale, Apr 18 2014 *)

A258081 Values of k in A071580.

Original entry on oeis.org

1, 1, 1, 1, 2, 10, 12, 10, 21, 25, 70, 670, 239, 2115, 586, 1619, 26800, 2505, 99019, 40903, 285641, 67166, 1852765

Offset: 1

Andrew R. Booker, May 19 2015

The first 23 terms were found using gwnum, and the first 22 have been independently checked using gmp.

Mersenne Forum, A071580

Cf. A061092, A072532, A113334.

terms=12; p=2; for(n=2, terms, q=p+1; while(!ispseudoprime(q), q=q+p); print1(q\p,", "); p=p*q) \\ Serge Batalov, May 19 2015

A035091 Smallest prime == 1 mod (n^2).

Original entry on oeis.org

2, 5, 19, 17, 101, 37, 197, 193, 163, 101, 727, 433, 677, 197, 1801, 257, 3469, 1297, 10831, 401, 883, 1453, 12697, 577, 11251, 677, 1459, 3137, 10093, 1801, 15377, 12289, 2179, 3469, 7351, 1297, 5477, 18773, 9127, 1601, 16811, 3529, 22189, 11617

Offset: 1

Labos Elemer

nonn

Smallest prime of form (n^2)*k+1, i.e., an arithmetic progression with n^2 differences; k is the subscript of the progressions.

			a(5) = 101 because in 5^2k + 1 = 25k + 1 progression k=4 generates the smallest prime (this is 101) and 26, 51, and 76 are composite.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..500 from Robert Price)
Index entries for sequences related to primes in arithmetic progressions.

Analogous case is A034694. Special case is A002496.

Cf. A070844 to A070858, A061092, A035095.

With[{prs=Prime[Range[2500]]},Flatten[Table[Select[prs,Mod[#-1,n^2]==0&,1],{n,50}]]] (* Harvey P. Dale, Sep 22 2021 *)

a(n) = if(n == 1, 2, my(s = n^2); forprime(p = 1, , if(p % s == 1, return(p)))); \\ Amiram Eldar, Mar 16 2025

cp's OEIS Frontend

A121799 Values of k from A061092.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A059411 a(1) = 2, a(n) = k*a(n-1) + 1, where a(n) is the smallest prime of the form k*a(n-1) + 1 and k > 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A071580 Smallest prime of the form k*a(n-1)*a(n-2)*...*a(1)+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A072532 a(0)=1; for n>0, a(n) = smallest prime of the form k*a(n-1)-1 with k>1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A214523 a(1) = 13, a(n) is smallest prime of the form k*a(n-1) + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A061303 Given a prime p, let s(p,0)=p and let s(p,n+1) be the smallest prime == 1 (mod s(p,n)). Let S(p) be the sequence {s(p,n): n=0,1,...}. Let a(0)=2 and let a(n+1) be the smallest prime not in any of the sequences S(a(0)), ..., S(a(n)).

Views

Author

Keywords

Comments

Examples

A059411 a(1) = 2, a(n) = ka(n-1) + 1, where a(n) is the smallest prime of the form ka(n-1) + 1 and k > 1.

A071580 Smallest prime of the form ka(n-1)a(n-2)...a(1)+1.