A117673 -id:A117673 - cp's OEIS frontend

A035096 a(n) is the smallest k such that prime(n)*k+1 is prime.

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

Offset: 1

Labos Elemer

nonn

These arithmetic progressions have prime differences. Note that both the terms of generated by this k values and the differences are primes as well.
This is one possible generalization of "the least prime problem in special arithmetic progressions" when n in the nk+1 form is replaced by n-th prime number.
Note that Dirichlet's theorem on primes in arithmetic progressions implies that a(n) always exists. - Max Alekseyev, Jul 11 2008
If a(n)=2, prime(n) is a Sophie Germain prime (A005384). Among the first 10^6 terms, the largest is a(330408) = 234. - Zak Seidov, Jan 28 2012

			a(15)=6 because the 15th prime is 47, and the smallest k such that 47k+1 is prime is k=6, for which 47k+1=283.

T. D. Noe, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Math, Dirichlet's theorem.
Index entries for sequences related to primes in arithmetic progressions.

Smallest k such that k*n+1 is prime is A034693.
Sophie Germain primes are in A005384.
Cf. A000040, A035095. - Zak Seidov, Dec 27 2013
Cf. A117673.

S:=[];
k:=1;
for n in [1..90] do
  while not IsPrime(k*NthPrime(n)+1) do
       k:=k+1;
  end while;
  Append(~S, k);
  k:=1;
end for;
S; // Bruno Berselli, Apr 18 2013

Reap[Sow[1]; Do[p = Prime[n]; k = 2; While[! PrimeQ[k*p + 1], k = k + 2]; Sow[k], {n, 2, 10^4}]][[2, 1]] (* Zak Seidov, Jan 28 2012 *)
f[n_] := Block[{p = Prime@ n}, q = 1 + 2p; While[ !PrimeQ@ q, q += 2p]; (q - 1)/p]; f[1] = 1; Array[f, 88] (* Robert G. Wilson v, Dec 27 2014 *)

a(n) = if(n == 1, 1, my(t = 2*prime(n), m = t + 1); while(!isprime(m), m += t); 2*(m - 1)/t); \\ Amiram Eldar, Mar 19 2025

a(n) = (A035095(n)-1)/A000040(n). - Zak Seidov, Dec 27 2013

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

A072225 Numbers k such that prime(k) + prime(k+1) + prime(k+2) is prime.

Original entry on oeis.org

3, 4, 5, 7, 8, 9, 10, 11, 13, 16, 18, 19, 20, 22, 23, 26, 29, 34, 35, 37, 38, 45, 47, 50, 58, 60, 61, 62, 64, 68, 69, 70, 75, 77, 79, 80, 83, 87, 88, 90, 91, 94, 95, 97, 101, 113, 116, 119, 120, 121, 126, 128, 132, 133, 134

Offset: 1

Joseph L. Pe, Jul 04 2002

The sequence contains 298884 terms <= 2000000, so nearly 15% of the numbers <= 2000000 are in the sequence. - Dmitry Kamenetsky, Aug 08 2015
Heuristically, we might expect the "probability" of n being in the sequence to be on the order of 1/log(n). - Robert Israel, Aug 09 2015
The first 8 consecutive integers in this sequence start from 8744076. - Dmitry Kamenetsky, Aug 28 2015
The first 9 consecutive integers in this sequence start from 697642916. - Dmitry Kamenetsky, Sep 08 2015
Vladimir Chirkov found that the first 10 and 11 consecutive integers in this sequence start from 23169509240 and 29165083170, respectively (see The Prime Puzzles link and A386275). - Dmitry Kamenetsky, Sep 08 2015

			9 is in the sequence because prime(9) + prime(10) + prime(11) = 23 + 29 + 31 = 83 is a prime.

Robert Israel, Table of n, a(n) for n = 1..10000
Carlos Rivera, Puzzle 798. A nice puzzle by Kamenetski, The Prime Puzzles & Problems Connection.

Cf. A034962, A073681, A117673, A152469, A152470.

Cf. A386275 (first occurrences of runs).

[n: n in [0..600]| IsPrime(NthPrime(n)+NthPrime(n+1)+NthPrime(n+2))]; // Vincenzo Librandi, Apr 06 2011

a:=proc(n) if isprime(ithprime(n)+ithprime(n+1)+ithprime(n+2))=true then n else fi end: seq(a(n),n=1..150); # Emeric Deutsch, Apr 24 2006

Select[Range[10^4], PrimeQ[Prime[ # ] + Prime[ # + 1] + Prime[ # + 2]] &]

isok(n)=isprime(prime(n)+prime(n+1)+prime(n+2)) \\ Anders Hellström, Aug 20 2015

A074884 For a prime p, let k(p) be the least k such that 2kp+1 is prime. Sequence gives primes for which k(p) exceeds k(q) for all primes q < p.

Original entry on oeis.org

2, 7, 17, 19, 59, 167, 197, 227, 317, 457, 521, 1637, 1861, 1997, 2053, 3833, 5227, 19891, 47303, 54973, 58603, 124567, 138163, 170167, 707467, 1637429, 1940777, 3717731, 4722079, 17886697, 27507569, 73342163, 154205101, 160561133, 186668543, 429364379, 458121431, 1459411661, 2140833967, 4028983027, 5189517859, 6184586189, 10352323829, 36673176307

Offset: 1

Mike Oakes, Oct 01 2002

nonn

			a(1)=2 because k(2)=1 (2*1*2+1=5 is prime);
a(2)=7 because k(7)=2 (2*1*7+1=15 is not prime, 2*2*7+1=29 is prime).

Cf. A117673.

a(30)-a(38) from Don Reble, Jan 07 2013

a(39)-a(44) from Marco Frigerio, Mar 25 2019

A367805 a(1) = 0; for n > 1, a(n) is the least positive integer k for which k*prime(n) + 2 is prime.

Original entry on oeis.org

0, 1, 1, 3, 1, 3, 1, 3, 3, 1, 5, 3, 1, 3, 7, 7, 1, 5, 5, 1, 5, 3, 3, 3, 3, 1, 3, 1, 5, 9, 3, 7, 1, 3, 1, 5, 5, 3, 3, 3, 1, 5, 1, 5, 1, 3, 9, 5, 1, 9, 3, 1, 15, 7, 3, 15, 1, 9, 11, 1, 9, 3, 21, 1, 3, 3, 5, 3, 1, 3, 3, 15, 3, 5, 9, 3, 13, 3, 19, 3, 1, 15, 1, 3, 3, 9, 13, 3, 1, 15

Offset: 1

Frank Hollstein, Dec 01 2023

nonn

			For n = 4: a(4) = 3, because prime(4) = 7, 3*7 + 2 = 23 which is prime.

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A000040, A029707, A035096, A117673, A279756, A001359.

a:= proc(n) local p, q, r; p:= ithprime(n); q:= p;
      while irem(q-2, p, 'r')<>0 do q:= nextprime(q) od; r
    end:
seq(a(n), n=1..99);  # Alois P. Heinz, Dec 04 2023

nmax=90; a[1]=0; For[n=2, n<=nmax, n++, For[k=1, k>0, k++, If[PrimeQ[k*Prime[n]+2], a[n]=k; k=-1]]]; Array[a,nmax] (* Stefano Spezia, Dec 04 2023 *)

a(n) = if (n==1, 0, my(k=1, p=prime(n)); while (!isprime(k*p+2), k++); k); \\ Michel Marcus, Dec 02 2023

from itertools import count, dropwhile
from sympy import prime, isprime
def A367805(n):
    if n==1:
        return 0
    else:
        p = prime(n)
        return next(dropwhile(lambda x:not isprime(x*p+2),count(1))) # Chai Wah Wu, Jan 04 2024

a(n) = (A279756(n) - 2)/A000040(n).

a(n) = 1 <=> n in A029707.

More terms from Michel Marcus, Dec 02 2023

cp's OEIS Frontend

A035096 a(n) is the smallest k such that prime(n)*k+1 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

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

A072225 Numbers k such that prime(k) + prime(k+1) + prime(k+2) is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

A074884 For a prime p, let k(p) be the least k such that 2kp+1 is prime. Sequence gives primes for which k(p) exceeds k(q) for all primes q < p.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A367805 a(1) = 0; for n > 1, a(n) is the least positive integer k for which k*prime(n) + 2 is prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions