A125878 -id:A125878 - cp's OEIS frontend

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

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

A125866 Odd numbers k such that cos(2*Pi/k) is an algebraic number of a 3-smooth degree, but not 2-smooth.

Original entry on oeis.org

7, 9, 13, 19, 21, 27, 35, 37, 39, 45, 57, 63, 65, 73, 81, 91, 95, 97, 105, 109, 111, 117, 119, 133, 135, 153, 163, 171, 185, 189, 193, 195, 219, 221, 243, 247, 259, 273, 285, 291, 315, 323, 327, 333, 351, 357, 365, 399, 405, 433, 455, 459, 481, 485, 487, 489

Offset: 1

Artur Jasinski, Dec 13 2006

nonn

Odd terms of A051913.
This sequence is infinite (unlike A004729), because it contains any A058383(n) times any power of 3.
A regular polygon of a(n) sides can be constructed if one also has an angle trisector.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A004729, A051913, A058383, A125867-A125878.

filter:= proc(n) local r,a,b;
  r:= numtheory:-phi(n);
  a:= padic:-ordp(r,2);
  b:= padic:-ordp(r,3);
  if b = 0 then return false fi;
  r = 2^a*3^b;
end proc:
select(filter, [seq(i,i=3..1000,2)]); # Robert Israel, May 11 2020

Do[If[Take[FactorInteger[EulerPhi[2n+1]][[ -1]], 1]=={3},Print[2n+1]],{n,1,10000}]

Edited by Don Reble, Apr 24 2007

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

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, Dec 19 2001

nonn

All terms seem to be primes of the form a(n) = k*prime(n)+1 for some k.
Is this a duplicate of A035095? - R. J. Mathar, Dec 13 2008
For the first 5*10^6 terms, a(n) = A035095(n). - Donovan Johnson, Oct 21 2011
Comments on the relationship between A035095, A066674, A125878, added by N. J. A. Sloane, Jan 07 2013: (Start)
Let a(n) = A066674(n), b(n) = A035095(n), c(n) = A125878(n).
It is immediate from the definitions that a(n) <= b(n) and a(n) <= c(n).
Bjorn Poonen (Jan 06 2013) makes the following observations:
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).
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.
Thus c(n) = a(n).
Further comments from Eric Bach, Jan 07 2013: (Start)
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.
Here are some remarks connected with this.
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.
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).
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)
Don Reble (Jan 07 2013) observes that A074884 and A117673 are related to these questions.
Summary: A066674 and A125878 are the same, and A035095 is probably also the same, but this is an open question.
(End)

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

Robert G. Wilson v, Table of n, a(n) for n = 1..10000
E. Bach and L. Huelsbergen, Statistical evidence for small generating sets, Math. Comp. 61 (1993) 69-82.
E. Bach and J. Sorenson, Explicit bounds for primes in residue classes, Math. Comp. 65, 1996, pp. 1717-1735.
D. R. Heath-Brown, Almost-primes in arithmetic progressions and short intervals, Math. Proc. Cambridge Phil. Soc., 83:357--375, 1978.
D. R. Heath-Brown, Siegel zeros and the least prime in an arithmetic progression, Quart. J. Math. Oxford (2) 41, 1990, 405-418.
D. R. Heath-Brown, Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression, Proc. London Math. Soc. 64(3) (1992), pp. 265-338.
S. S. Wagstaff, Jr, Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus, Math. Comp., 33 (147) (1979) pp. 1073-1080.
T. Xylouris, On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions, Acta Arith. 150 (2011), no. 1, 65-91.

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

Cf. also A074884 and A117673.

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

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

a(2) corrected by R. J. Mathar, Dec 13 2008

A125867 Numbers k such that p=6k+1 is prime and cos(2*Pi/p) is an algebraic number of a 3-smooth degree, but not 2-smooth.

Original entry on oeis.org

1, 2, 3, 6, 12, 16, 18, 27, 32, 72, 81, 96, 128, 192, 216, 243, 432, 486, 576, 648, 1728, 2048, 2916, 3072, 6561, 8748, 23328, 24576, 34992, 55296, 78732, 104976, 124416, 131072, 139968, 165888, 196608, 248832, 294912, 331776, 442368, 839808

Offset: 1

Artur Jasinski, Dec 13 2006

nonn

Numbers k such that p=6k+1 is prime and the greatest prime divisor of p-1 is 3.

Cf. A024899, A058383, A125866-A125878.

Do[If[Take[FactorInteger[EulerPhi[6n+1]][[ -1]], 1]=={3} && PrimeQ[6n+1],Print[n]],{n,1,100000}]

Edited by Don Reble, Apr 24 2007

A125875 Odd numbers k such that cos(2*Pi/k) is an algebraic number of a 13-smooth degree, but not 11-smooth.

Original entry on oeis.org

53, 79, 131, 157, 159, 169, 237, 265, 313, 371, 393, 395, 471, 477, 507, 521, 547, 553, 583, 655, 677, 689, 711, 785, 795, 845, 859, 869, 901, 911, 917, 937, 939, 1007, 1027, 1093, 1099, 1113, 1171, 1179, 1183, 1185, 1219, 1249, 1301, 1325, 1343

Offset: 1

Artur Jasinski, Dec 13 2006

nonn

A regular polygon of a(n) sides can be constructed if one also has an angle trisector, 5-, 7-, 11- and 13-sector.

Cf. A125866-A125878.

Do[If[Take[FactorInteger[EulerPhi[2n+1]][[ -1]],1]=={13},Print[2n+1]],{n,1,10000}]

Edited by Don Reble, Apr 24 2007

A125877 Numbers k such that p=26k+1 is prime and cos(2Pi/p) is an algebraic number of a 13-smooth degree, but not 11-smooth.

Original entry on oeis.org

2, 3, 5, 6, 12, 20, 21, 26, 33, 35, 36, 42, 45, 48, 50, 72, 75, 77, 78, 80, 90, 98, 105, 110, 120, 125, 128, 132, 135, 143, 147, 156, 182, 192, 225, 231, 252, 260, 275, 288, 297, 308, 315, 330, 336, 351, 363, 378, 390, 392, 405, 441, 450, 455, 486, 500, 507, 512

Offset: 1

Artur Jasinski, Dec 13 2006

nonn

Numbers k such that p=26*k+1 is prime and the greatest prime divisor of p-1 is 13.

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

Cf. A125866-A125878.

Do[If[Take[FactorInteger[EulerPhi[26n+1]][[ -1]],1]=={13} && PrimeQ[26n+1],Print[n]],{n,1,10000}]
(* or *)
Select[Range[600],PrimeQ[26#+1]&&FactorInteger[26#][[-1,1]]==13&] (* Harvey P. Dale, Jun 01 2019 *)

Edited by Don Reble, Apr 24 2007

A125874 Numbers k such that p=22k+1 is prime and cos(2Pi/p) is an algebraic number of an 11-smooth degree, but not 7-smooth.

Original entry on oeis.org

1, 3, 4, 9, 15, 16, 18, 21, 28, 30, 33, 40, 45, 60, 64, 66, 81, 96, 99, 105, 108, 121, 135, 144, 150, 154, 165, 168, 175, 189, 198, 210, 225, 240, 243, 250, 288, 294, 324, 336, 343, 378, 396, 420, 448, 450, 490, 495, 525, 528, 550, 616, 625, 640, 675, 700, 726

Offset: 1

Artur Jasinski, Dec 13 2006

nonn

Numbers k such that p=22*k+1 is prime and the greatest prime divisor of p-1 is 11.

Cf. A125866-A125878.

Do[If[Take[FactorInteger[EulerPhi[22n+1]][[ -1]],1]=={11} && PrimeQ[22n+1],Print[n]],{n,1,10000}]

Edited by Don Reble, Apr 24 2007

A125868 Odd numbers k such that cos(2*Pi/k) is an algebraic number of a 5-smooth degree, but not 3-smooth.

Original entry on oeis.org

11, 25, 31, 33, 41, 55, 61, 75, 77, 93, 99, 101, 123, 125, 143, 151, 155, 165, 175, 181, 183, 187, 205, 209, 217, 225, 231, 241, 251, 271, 275, 279, 287, 297, 303, 305, 325, 341, 369, 375, 385, 401, 403, 407, 425, 427, 429, 451, 453, 465, 475, 495, 505, 525

Offset: 1

Artur Jasinski, Dec 13 2006

nonn

A regular polygon of a(n) sides can be constructed if one also has an angle trisector and 5-sector.

Cf. A058383, A061599, A125866-A125878.

Do[If[Take[FactorInteger[EulerPhi[2n+1]][[ -1]],1]=={5},Print[2n+1]],{n,1,1000}]

Edited by Don Reble, Apr 24 2007

A125869 Numbers k such that p=10k+1 is prime and cos(2Pi/p) is an algebraic number of a 5-smooth degree, but not 3-smooth.

Original entry on oeis.org

1, 3, 4, 6, 10, 15, 18, 24, 25, 27, 40, 54, 60, 64, 75, 81, 120, 160, 162, 180, 216, 225, 300, 400, 405, 480, 486, 648, 768, 810, 864, 900, 960, 972, 1125, 1440, 1536, 1600, 1944, 2160, 2187, 2250, 2304, 2400, 2560, 3240, 3375, 3645, 3750, 4096, 4320

Offset: 1

Artur Jasinski, Dec 13 2006

nonn

Numbers k such that p=10*k+1 is prime and the greatest prime divisor of p-1 is 5.

Cf. A024912, A125866-A125878.

Do[If[Take[FactorInteger[EulerPhi[10n+1]][[ -1]],1]=={5} && PrimeQ[10n+1],Print[n]],{n,1,10000}]

Edited by Don Reble, Apr 24 2007

A125870 Odd numbers k such that cos(2*Pi/k) is an algebraic number of a 7-smooth degree, but not 5-smooth.

Original entry on oeis.org

29, 43, 49, 71, 87, 113, 127, 129, 145, 147, 197, 203, 211, 213, 215, 245, 261, 281, 301, 319, 337, 339, 343, 355, 377, 379, 381, 387, 421, 435, 441, 449, 473, 491, 493, 497, 539, 551, 559, 565, 591, 609, 631, 633, 635, 637, 639, 645, 673, 701, 725, 731

Offset: 1

Artur Jasinski, Dec 13 2006

nonn

A regular polygon of a(n) sides can be constructed if one also has an angle trisector, 5-sector and 7-sector.

Cf. A125866-A125878.

Do[If[Take[FactorInteger[EulerPhi[2n+1]][[ -1]],1]=={7},Print[2n+1]],{n,1,1000}]

Edited by Don Reble, Apr 24 2007

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A125866 Odd numbers k such that cos(2*Pi/k) is an algebraic number of a 3-smooth degree, but not 2-smooth.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A125867 Numbers k such that p=6k+1 is prime and cos(2*Pi/p) is an algebraic number of a 3-smooth degree, but not 2-smooth.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A125875 Odd numbers k such that cos(2*Pi/k) is an algebraic number of a 13-smooth degree, but not 11-smooth.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A125877 Numbers k such that p=26*k+1 is prime and cos(2*Pi/p) is an algebraic number of a 13-smooth degree, but not 11-smooth.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A125874 Numbers k such that p=22*k+1 is prime and cos(2*Pi/p) is an algebraic number of an 11-smooth degree, but not 7-smooth.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A125868 Odd numbers k such that cos(2*Pi/k) is an algebraic number of a 5-smooth degree, but not 3-smooth.

Views

Author

A125877 Numbers k such that p=26k+1 is prime and cos(2Pi/p) is an algebraic number of a 13-smooth degree, but not 11-smooth.

A125874 Numbers k such that p=22k+1 is prime and cos(2Pi/p) is an algebraic number of an 11-smooth degree, but not 7-smooth.

A125869 Numbers k such that p=10k+1 is prime and cos(2Pi/p) is an algebraic number of a 5-smooth degree, but not 3-smooth.