A035096 -id:A035096 - cp's OEIS frontend

A247234 First occurrence of 2*n in A035096.

2, 4, 7, 20, 8, 17, 39, 134, 45, 206, 149, 49, 66, 321, 88, 98, 637, 382, 259, 284, 820, 302, 310, 1102, 1597, 3763, 1140, 3432, 741, 532, 4751, 856, 4855, 3446, 2130, 3256, 3407, 694, 2250, 4878, 5588, 13199, 15211, 9040, 7426, 11126, 5931, 11699, 22463, 26223, 37546, 37602, 42795, 32776

Offset: 1

Robert G. Wilson v, Dec 28 2014

nonn

			a(1) = 2 since the first appearance of 2 occurs at A035096(2);
a(3) = 7 since the first appearance of 6 occurs at A035096(7).

Robert G. Wilson v, Table of n, a(n) for n = 1..276

Cf. A035096.

f[n_] := Block[{p = Prime@ n}, q = 1 + 2p; While[ !PrimeQ@ q, q += 2p]; (q - 1)/p]; f[1] = 1; t = Table[0, {1000}]; k = 2; While[k < 10^5, a = f@ k /2; If[ t[[a]] == 0, t[[a]] = k; Print[{a, k}]]; k++]; t

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

A068211 Largest prime factor of Euler totient function phi(n).

Original entry on oeis.org

2, 2, 2, 2, 3, 2, 3, 2, 5, 2, 3, 3, 2, 2, 2, 3, 3, 2, 3, 5, 11, 2, 5, 3, 3, 3, 7, 2, 5, 2, 5, 2, 3, 3, 3, 3, 3, 2, 5, 3, 7, 5, 3, 11, 23, 2, 7, 5, 2, 3, 13, 3, 5, 3, 3, 7, 29, 2, 5, 5, 3, 2, 3, 5, 11, 2, 11, 3, 7, 3, 3, 3, 5, 3, 5, 3, 13, 2, 3, 5, 41, 3, 2, 7, 7, 5, 11, 3, 3, 11, 5, 23, 3, 2, 3, 7, 5, 5

Offset: 3

Labos Elemer, Feb 21 2002

nonn

Smallest numbers m, such that largest prime factor of phi(m) is prime(n), a(n) is a prime number and identical to the n-th term of A035095: min{x: A068211(x) = prime(n)} = A035095(n). E.g., phi(A035095(7)) = phi(103) = 2*3*17 of which 17 = prime(7) is the largest prime factor.

			For n=46, phi(46) = 2*2*11, hence a(46) = 11.

T. D. Noe, Table of n, a(n) for n = 3..1000

Cf. A000010, A006530.

Cf. A035095, A035096.

[Maximum(PrimeDivisors(EulerPhi(n))): n in [3..90]]; // Vincenzo Librandi, Jan 04 2017

Table[FactorInteger[EulerPhi[n]][[-1, 1]], {n, 3, 100}] (* Vincenzo Librandi, Jan 04 2017 *)

a(n) = vecmax(factor(eulerphi(n))[,1]); \\ Michel Marcus, Jan 04 2017

a(n) = A006530(A000010(n)).

A066675 a(n) = A066674(n)-1 divided by the n-th prime.

Original entry on oeis.org

1, 2, 2, 4, 2, 4, 6, 10, 2, 2, 10, 4, 2, 4, 6, 2, 12, 6, 4, 8, 4, 4, 2, 2, 4, 6, 6, 6, 10, 2, 4, 2, 6, 4, 8, 6, 10, 4, 14, 2, 2, 6, 2, 4, 18, 4, 10, 12, 24, 12, 2, 2, 6, 2, 6, 6, 8, 6, 4, 2, 6, 2, 4, 6, 6, 26, 6, 10, 6, 10, 14, 2, 6, 4, 12, 12, 24, 6, 8, 4, 2, 10, 2, 4, 10, 2, 8, 30, 6, 12, 6, 8, 4

Offset: 1

Labos Elemer, Dec 19 2001

nonn

Is this a duplicate of A035096? - R. J. Mathar, Dec 15 2008

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A000040, A035096, A066674, A066675, A066676, A066677, A066678.

a(n) = min{m : phi(m) == 0 (mod p(n))} = min{m : A000010(m) == 0 (mod A000040(n))}.

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

A117673 a(n) is the least k such that k2prime(n) + 1 is prime.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 3, 5, 1, 1, 5, 2, 1, 2, 3, 1, 6, 3, 2, 4, 2, 2, 1, 1, 2, 3, 3, 3, 5, 1, 2, 1, 3, 2, 4, 3, 5, 2, 7, 1, 1, 3, 1, 2, 9, 2, 5, 6, 12, 6, 1, 1, 3, 1, 3, 3, 4, 3, 2, 1, 3, 1, 2, 3, 3, 13, 3, 5, 3, 5, 7, 1, 3, 2, 6, 6, 12, 3, 4, 2, 1, 5, 1, 2, 5, 1, 4, 15, 3, 6, 3, 4, 2, 1, 2, 3, 1, 16, 5, 9

Offset: 1

Don Reble, Apr 25 2006

nonn

Iff a(n) = 1, prime(n) is a Sophie Germain prime, i.e., in A005384. - A.H.M. Smeets, Feb 01 2018

			a(8)=5 because 2*prime(8)=38 and 5*38 + 1 is prime.

Zak Seidov, Table of n, a(n) for n = 1..10000

Cf. A016014, A035096, A074884.

Table[k := 1; While[ ! PrimeQ[2*k*Prime[n] + 1], k++ ]; k, {n, 1, 120}] (* Stefan Steinerberger, May 01 2006 *)

a(n) = {my(p=prime(n), k=1); while (!isprime(2*k*p+1), k++); k;} \\ Michel Marcus, Feb 12 2018

A216568 Smallest k such that prime(n)*k-1 is prime.

Original entry on oeis.org

2, 1, 4, 2, 4, 8, 4, 2, 6, 6, 2, 2, 4, 6, 6, 4, 6, 8, 6, 4, 14, 2, 4, 16, 2, 10, 6, 6, 6, 6, 6, 4, 4, 2, 10, 12, 2, 6, 10, 4, 10, 8, 22, 8, 4, 2, 2, 8, 4, 2, 16, 6, 14, 12, 12, 4, 6, 2, 12, 4, 6, 4, 2, 10, 6, 6, 2, 2, 6, 8, 10, 6, 2, 6, 2, 4, 6, 6, 22

Offset: 1

Alex Ratushnyak, Sep 19 2012

nonn

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

Cf. A035096, A034693, A053989.

Table[k = 1; While[! PrimeQ[Prime[n]*k - 1], k++]; k, {n, 100}] (* T. D. Noe, Sep 19 2012 *)

A266909 Table read by rows: for each k < n and coprime to n, the least x>=0 such that x*n+k is prime.

Original entry on oeis.org

1, 2, 0, 1, 0, 2, 0, 0, 3, 1, 0, 4, 0, 0, 1, 0, 1, 2, 0, 0, 0, 2, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 0, 0, 3, 0, 1, 0, 1, 2, 3, 1, 0, 0, 0, 4, 0, 0, 1, 0, 1, 0, 3, 4, 1, 0, 7, 2, 0, 0, 1, 0, 0, 2, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 0, 0, 1, 6, 0, 0, 5, 0, 1, 0, 3, 2, 3, 0, 1, 0, 1, 4, 3, 1, 0, 0, 0, 0, 0, 10, 0

Offset: 1

Robert Israel, Jan 05 2016

By Dirichlet's theorem, such x exists whenever k is coprime to n.
By Linnik's theorem, there exist constants b and c such that T(n,k) <= b n^c for all n and all k < n coprime to n.
T(n,1) = A034693(n).
T(n,n-1) = A053989(n)-1.
T(prime(n),1) = A035096(n).
T(2^n,1) = A035050(n).
A085427(n) = T(2^n,2^n-1) + 1.
A126717(n) = 2*T(2^(n+1),2^n-1) + 1.
A257378(n) = 2*T(n*2^(n+1),n*2^n+1) + 1.
A257379(n) = 2*T(n*2^(n+1),n*2^n-1) + 1.

			The first few rows are
n=2: 1
n=3: 2, 0
n=4: 1, 0
n=5: 2, 0, 0, 3
n=6: 1, 0

Robert Israel, Table of n, a(n) for n = 1..10975 (rows 2 to 190, flattened)
Wikipedia, Dirichlet's theorem on arithmetic progressions.
Wikipedia, Linnik's theorem
Index entries for sequences related to primes in arithmetic progressions

Cf. A034693, A035050, A035096, A053989, A085427, A126717, A257378, A257379.

T:= proc(n,k) local x;
    if igcd(n,k) <> 1 then return NULL fi;
    for x from 0 do if isprime(x*n+k) then return x fi
    od
end proc:
seq(seq(T(n,k),k=1..n-1),n=2..30);

Table[Map[Catch@ Do[x = 0; While[! PrimeQ[x n + #], x++]; Throw@ x, {10^3}] &, Range@ n /. k_ /; GCD[k, n] > 1 -> Nothing], {n, 2, 19}] // Flatten (* Michael De Vlieger, Jan 06 2016 *)

A266236 Least m > 0 such that m*n^3 + 1 is a cube.

Original entry on oeis.org

1, 7, 91, 37, 4291, 16003, 1801, 17, 263683, 19927, 1003003, 1775557, 111169, 506115, 17145, 423001, 16789507, 24152311, 1261657, 3266062, 64024003, 5080, 113411851, 148072393, 7082497, 244187503, 1922636, 14355469, 3132736, 594896491, 27009001, 8341522, 1073840131

Offset: 0

Alex Ratushnyak, Dec 25 2015

nonn

Least m>0 for which x^3 - m*y^3 = 1 has a solution with y = n.

			17*7^3+1 = 18^3, and 17 is the smallest positive m such that m*7^3+1 is a cube, so a(7)=17.

Robert G. Wilson v, Table of n, a(n) for n = 0..1000

Cf. A000578, A035096, A067872.

f[n_] := Block[{x = 2, n3 = n^3}, While[ Mod[x^3 - 1, n3] != 0, x++]; (x^3 - 1)/n3]; f[0] = 1; Array[f, 34, 0] (* Robert G. Wilson v, Mar 24 2016 *)

a(n) = {my(m = 1, cn = n^3); while (!ispower(m*cn + 1, 3), m++); m;} \\ Michel Marcus, Feb 09 2016

a(n) = A076947(n^3). - Robert Israel, Dec 25 2015

A267077 Least m>0 for which mn^2 + 1 is a square and mtriangular(n) + 1 is a triangular number (A000217). Or -1 if no such m exists.

Original entry on oeis.org

1, 35, 30, 18135, 189, 27, 321300, 23760, 1188585957, 1656083, 26, 244894427400, 82093908624206325, 1858717755529547, 86478, 21491811639746039592, 26135932603458945934958445, 353382195058506640426335, 26780050, 7859354769338288038121982384, 274554988002

Offset: 0

Alex Ratushnyak, Jan 10 2016

nonn

			26*10^2+1 = 2601 is a square, and 26*10*11/2+1 = 1431 = triangular(53), and 26 is the smallest such multiplier, therefore a(10) = 26.

Don Reble, Table of n, a(n) for n = 0..300

Cf. A000217, A000290, A035096, A061782, A067872, A188621.

from math import sqrt
def A267077(n):
    if n == 0:
        return 1
    u,v,t,w = max(8,2*n),max(4,n)**2-9,4*n*(n+1),n**2
    while True:
        m,r = divmod(v,t)
        if not r and int(sqrt(m*w+1))**2 == m*w+1:
            return m
        v += u+1
        u += 2 # Chai Wah Wu, Jan 15 2016

#!/usr/bin/python3
# This sequence is easy if you use a Pell-equation solver such as labmath.py
# Solve the A267077 Pell equation:
# nx^2 - (4n+4)y^2 = 5n-4; but also y^2 == 1 mod n^2
# Let u = nx, then # u^2 - n*(4n+4)y^2 = n*(5n-4)
#   and (y > n) and (u == 0 mod n) and (y^2 == 1 mod n^2)
# (y > n makes m > 0)
# Report m = (y^2 - 1) / n^2
import labmath
print(0, 1)
print(1, 35) # When n<2, the Pell equation is elliptical.
for nn in range(2,1001):
    nsq = nn * nn
    ps = labmath.pell(nn*(4*nn+4), nn*(5*nn-4))
    uu,yy = next(ps[0])
    while (yy <= nn) or ((uu % nn) != 0) or ((yy*yy) % nsq != 1):
        uu,yy = next(ps[0])
    print(nn, (yy*yy - 1) // nsq)
# From Don Reble, Apr 15 2022, added by N. J. A. Sloane, Apr 15 2022.

a(12)-a(15) from Chai Wah Wu, Jan 16 2016

a(16) and beyond from Don Reble, Apr 15 2022

A082650 Number of primes < n of form 1+k*spf(n), where spf(n) is the smallest prime factor of n (A020639).

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 0, 3, 1, 3, 0, 4, 0, 5, 2, 5, 0, 6, 0, 7, 3, 7, 0, 8, 1, 8, 3, 8, 0, 9, 0, 10, 4, 10, 2, 10, 0, 11, 5, 11, 0, 12, 0, 13, 6, 13, 0, 14, 2, 14, 6, 14, 0, 15, 3, 15, 6, 15, 0, 16, 0, 17, 7, 17, 4, 17, 0, 18, 8, 18, 0, 19, 0, 20, 9, 20, 3, 20, 0, 21, 10, 21, 0, 22, 5, 22, 10, 22, 0

Offset: 1

Reinhard Zumkeller, May 16 2003

nonn

			For n=20, spf(20) = 2, and there are 8 primes of form 1+k*2: 1+1*2=3, 1+2*2=5,
1+3*2=7, 1+5*2=11, 1+6*2=13, 1+8*2=17, 1+9*2=19, therefore a(20) = 8.
For n=21, spf(21) = 3, and there are 3 primes of form 1+k*3: 1+2*3=7, 1+4*3=13, 1+6*3=19, therefore a(21) = 3.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Index entries for sequences related to primes in arithmetic progressions

Cf. A000720, A008578 (positions of 0's), A020639, A035096.

a[n_] := With[{spfn = FactorInteger[n][[1, 1]]}, Select[Range[n-1], PrimeQ[#] && IntegerQ[(#-1)/spfn]&] // Length];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Jan 13 2023 *)

A020639(n) = if(1==n,n,vecmin(factor(n)[, 1]));
A082650(n) = { my(spf=A020639(n), s=0); forprime(p=(1+spf),n-1,if(!((p-1)%spf),s++)); (s); }; \\ Antti Karttunen, Apr 03 2022

a(2*n) = A000720(2*n)-1; a(n)=0 iff n=1 or n prime, i.e., a(A008578(n)) = 0. - Reinhard Zumkeller, Sep 11 2003, typo corrected by Antti Karttunen, Apr 03 2022

cp's OEIS Frontend

A247234 First occurrence of 2*n in A035096.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A068211 Largest prime factor of Euler totient function phi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A066675 a(n) = A066674(n)-1 divided by the n-th prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A117673 a(n) is the least k such that k*2*prime(n) + 1 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A216568 Smallest k such that prime(n)*k-1 is prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A266909 Table read by rows: for each k < n and coprime to n, the least x>=0 such that x*n+k is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A266236 Least m > 0 such that m*n^3 + 1 is a cube.

Views

A117673 a(n) is the least k such that k2prime(n) + 1 is prime.

A267077 Least m>0 for which mn^2 + 1 is a square and mtriangular(n) + 1 is a triangular number (A000217). Or -1 if no such m exists.