A034693 -id:A034693 - cp's OEIS frontend

A047980 a(n) is smallest difference d of an arithmetic progression dk+1 whose first prime occurs at the n-th position.

1, 3, 24, 7, 38, 17, 184, 71, 368, 19, 668, 59, 634, 167, 512, 757, 1028, 197, 1468, 159, 3382, 799, 4106, 227, 10012, 317, 7628, 415, 11282, 361, 38032, 521, 53630, 3289, 37274, 2633, 63334, 1637, 34108, 1861, 102296, 1691, 119074, 1997, 109474, 2053

Offset: 1

Labos Elemer

nonn

Definition involves two minimal conditions: (1) the first prime (as in A034693) and (2) dk+1 sequences were searched with minimal d. Present terms are the first ones in sequences analogous to A034780, A034782-A034784, A006093 (called there K(n,m)).

Index of the first occurrence of n in A034693. - Amarnath Murthy, May 08 2003

			For n=2, the sequence with d=1 is 2,3,4,5,... with the prime 2 for k=1.  The sequence with d=2 is 3,5,7,9,... with the prime 3 for k=1.  The sequence with d=3 is 4,7,10,13,... with the prime 7 for k=2.  So a(n)=3. - _Michael B. Porter_, Mar 18 2019

Jon E. Schoenfield, Table of n, a(n) for n = 1..150 (terms 1..72 from Robert Israel)
Jon E. Schoenfield, Terms <= 5*10^8: Table of n, a(n) for n = 1..406, with -1 for each term > 5*10^8
Index entries for sequences related to primes in arithmetic progressions

Cf. A034693, A034694, A034780, A034782, A034783, A034784, A006093, A047981, A047982.

function [ A ] = A047980( P, N )
%   Get values a(i) for i <= N with a(i) <= P/i
%   using primes <= P.
%   Returned entries A(n) = 0 correspond to unknown a(n) > P/n
Primes = primes(P);
A = zeros(1,N);
Ds = zeros(1,P);
for p = Primes
   ns = [1:N];
   ns = ns(mod((p-1) * ones(1,N), ns) == 0);
   newds = (p-1) ./ns;
   ns = ns(A(ns) == 0);
   ds = (p-1) ./ ns;
   q = (Ds(ds) == 0);
   A(ns(q)) = ds(q);
   Ds(newds) = 1;
end
end % Robert Israel, Jan 25 2016

N:= 40: # to get a(n) for n <= N
count:= 0:
p:= 0:
Ds:= {1}:
while count < N do
    p:= nextprime(p);
    ds:= select(d -> (p-1)/d <= N, numtheory:-divisors(p-1) minus Ds);
    for d in ds do
      n:= (p-1)/d;
      if not assigned(A[n]) then
        A[n]:= d;
        count:= count+1;
      fi
    od:
    Ds:= Ds union ds;
od:
seq(A[i],i=1..N); # Robert Israel, Jan 25 2016

With[{s = Table[k = 1; While[! PrimeQ[k n + 1], k++]; k, {n, 10^6}]}, TakeWhile[#, # > 0 &] &@ Flatten@ Array[FirstPosition[s, #] /. k_ /; MissingQ@ k -> {0} &, Max@ s]] (* Michael De Vlieger, Aug 01 2017 *)

a(n) = min{k | A034693(k) = n}.

A060940 Triangle in which n-th row gives the phi(n) terms appearing as initial primes in arithmetic progressions with difference n, with initial term equal to the smallest positive residue coprimes to n.

Original entry on oeis.org

2, 3, 7, 5, 5, 7, 11, 7, 13, 19, 7, 11, 29, 23, 17, 11, 19, 13, 17, 11, 13, 23, 19, 11, 13, 23, 43, 17, 11, 13, 17, 19, 23, 13, 47, 37, 71, 17, 29, 19, 31, 43, 13, 17, 19, 23, 53, 41, 29, 17, 31, 19, 59, 47, 61, 23, 37, 103, 29, 17, 19, 23, 53, 41, 31, 17, 19, 37, 23, 41, 43, 29

Offset: 1

Labos Elemer, May 07 2001

			For differences 1, 2, 3, 4, 5, 6, 7, .. the initial primes are 2; 3; 7, 5; 5, 7; 11, 7, 13, 19; 7, 11; 29, 23, 17, 11, 19, 13; ... etc. Suitable initial values (coprimes to difference) are in A038566. Position of end(start) of rows is given by values of A002088.
From _Seiichi Manyama_, Apr 02 2018: (Start)
   n | phi(n)|
  ---+-------+------------------------
   1 |   1   |  2;
   2 |   1   |  3;
   3 |   2   |  7,  5;
   4 |   2   |  5,  7;
   5 |   4   | 11,  7, 13, 19;
   6 |   2   |  7, 11;
   7 |   6   | 29, 23, 17, 11, 19, 13;
   8 |   4   | 17, 11, 13, 23;
   9 |   6   | 19, 11, 13, 23, 43, 17;
  10 |   4   | 11, 13, 17, 19;         (End)

Seiichi Manyama, Rows n = 1..200, flattened
Eric Weisstein's MathWorld, Dirichlet's theorem
Wikipedia, Dirichlet's theorem on arithmetic progressions

Cf. A000010 (phi), A002088, A038566, A034693, A034694, A002144, A007519, A088732, etc..

A072344 a(n) = the least natural number k such that k*phi(n) + 1 is prime.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 3, 1, 1, 1, 3, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 2, 3, 3, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 1, 1, 1, 1, 3, 1, 3, 2, 1, 1, 3, 3, 1, 2, 1, 1, 3, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 2, 2

Offset: 1

Joseph L. Pe, Jul 16 2002

nonn

			phi(35) = 24 and the least natural number k such that 24 k + 1 is prime is k = 3; so a(35) = 3.

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A000010, A034693, A072917.

f[n_] := Module[{i}, i = 0; While[ ! PrimeQ[i*EulerPhi[n] + 1], i++ ]; i]; Table[f[i], {i, 1, 150}]

A034693(n) = { my(k=1); while(!isprime(1+(k*n)), k++); k; };
A072344(n) = A034693(eulerphi(n)); \\ Antti Karttunen, Aug 22 2017

a(n) = A034693(A000010(n)). - Antti Karttunen, Aug 22 2017

A083809 Let f(n) be the smallest prime == 1 mod n (cf. A034694). Sequence gives triangle T(j,k) = f^k(j) for 1 <= k <= j, read by rows.

Original entry on oeis.org

2, 3, 7, 7, 29, 59, 5, 11, 23, 47, 11, 23, 47, 283, 1699, 7, 29, 59, 709, 2837, 22697, 29, 59, 709, 2837, 22697, 590123, 1180247, 17, 103, 619, 2477, 34679, 416149, 7490683, 29962733, 19, 191, 383, 4597, 27583, 330997, 9267917, 74143337, 1038006719

Offset: 1

Amarnath Murthy, May 08 2003

It has been proved in the reference that for every prime p there exists a prime of the form k*p+1. Conjecture: sequence is infinite, i.e., for every n there exists a prime of the form n*k+1 (cf. A034693).

Both follow directly from Dirichlet's theorem. [Charles R Greathouse IV, Feb 28 2012]

			The first few rows of the triangle are
2
3 7
7 29 59
5 11 23 47
11 23 47 283 1699
7 29 59 709 2837 22697

Amarnath Murthy, On the divisors of Smarandache Unary Sequence. Smarandache Notions Journal, Vol. 11, 2000.

Vincenzo Librandi, Table of n, a(n) for n = 1..591

The first column is given by A034694; the sequence of the last terms in the rows (main diagonal) is A083810. Row sums are in A160940.

Cf. A034693.

f:=function(n) m:=1; while not IsPrime(m*n+1) do m+:=1; end while; return m*n+1; end function; &cat[ [ k eq 1 select f(j) else f(Self(k-1)): k in [1..j] ]: j in [1..9] ]; // Klaus Brockhaus, May 30 2009

f[1]=2; f[n_] := f[n] = Block[{p=2}, While[Mod[p, n] != 1, p = NextPrime[p]]; p];
Flatten[Table[Rest @ NestList[f, j, j], {j, 9}]]
(* Jean-François Alcover, May 31 2011, improved by Robert G. Wilson v *)

f(n)=my(k=n+1);while(!isprime(k),k+=n);k
T(j,k)=for(i=1,k,j=f(j));j \\ Charles R Greathouse IV, Feb 28 2012

Edited, corrected and extended by Klaus Brockhaus, May 13 2003

A085053 Number of primes of the form nk+1, where k=1 to n; 0 if no such number exists.

Original entry on oeis.org

1, 2, 1, 3, 1, 5, 2, 2, 3, 6, 3, 6, 4, 6, 5, 6, 3, 10, 2, 7, 6, 9, 4, 10, 5, 10, 7, 11, 4, 17, 3, 10, 9, 12, 9, 16, 4, 9, 11, 14, 5, 21, 7, 11, 10, 16, 8, 19, 6, 18, 13, 17, 5, 24, 10, 19, 9, 16, 8, 27, 7, 15, 13, 16, 13, 30, 9, 18, 13, 27, 9, 26, 10, 20, 18, 17, 11, 29, 11, 23, 18, 22, 11

Offset: 1

Amarnath Murthy and Meenakshi Srikanth (menakan_s(AT)yahoo.com), Jun 26 2003

nonn

Conjecture: no entry is zero; i.e. for every n there exists a prime of the form nk+1, k<=n.

The conjecture is essentially the same as the one in A034693, which has a long history in the study of primes in arithmetic progression. - T. D. Noe, Jun 29 2003

			When formatted as an array of primes of the form nk+1 up to n^2+1:
2
3,5
7
5,13,17
11
7,13,19,31,37
29,43
17,41
19,37,73
11,31,41,61,71,101
23,67,89
13,37,61,73,97,109
53,79,131,157
29,43,71,113,127,197
The sequence contains the number of terms in the n-th row.

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

Cf. A034693 (smallest k such that kn+1 is prime).

Table[cnt=0; Do[If[PrimeQ[k*n+1], cnt++ ], {k, n}]; cnt, {n, 100}]
Table[Count[n*Range[n]+1,?PrimeQ],{n,90}] (* _Harvey P. Dale, Jan 24 2014 *)

a(m)=local(c); for(n=1,m,c=0; for(k=1,n,if(isprime(n*k+1),c++; )); print1(c","))

Edited, corrected and extended by T. D. Noe, Ray Chandler and Jason Earls, Jun 28 2003

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

A231820 Least positive k such that n*k! - 1 is a prime, or 0 if no such k exists.

Original entry on oeis.org

3, 2, 1, 1, 3, 1, 2, 1, 2, 2, 4, 1, 4, 1, 2, 2, 3, 1, 2, 1, 2, 2, 3, 1, 3, 5, 2, 3, 3, 1, 2, 1, 3, 2, 4, 2, 2, 1, 3, 2, 4, 1, 3, 1, 2, 4, 3, 1, 2, 6, 2, 2, 3, 1, 2, 5, 2, 3, 3, 1, 10, 1, 4, 2, 3, 2, 3, 1, 2, 2, 7, 1, 8, 1, 2, 2, 3, 3, 2, 1, 5, 2, 8, 1, 3, 4, 2, 4, 15, 1

Offset: 1

Alex Ratushnyak, Nov 13 2013

nonn

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

Cf. A035092 (least k such that k*(n^2)+1 is a prime).
Cf. A175763 (least k such that k*(n^n)+1 is a prime).
Cf. A035093 (least k such that k*n!+1    is a prime).
Cf. A193807 (least k such that n*(k^2)+1 is a prime).
Cf. A231119 (least k such that n*(k^k)+1 is a prime).
Cf. A057217 (least k such that n*k!+1    is a prime).
Cf. A034693 (least k such that n*k +1    is a prime).
Cf. A231819 (least k such that k*(n^2)-1 is a prime).
Cf. A231818 (least k such that k*(n^n)-1 is a prime).
Cf. A083663 (least k such that k*n!-1    is a prime).
Cf. A231734 (least k such that n*(k^2)-1 is a prime).
Cf. A231735 (least k such that n*(k^k)-1 is a prime).
Cf. A053989 (least k such that n*k -1    is a prime).

f:= proc(n) local k;
for k from 1 do if isprime(n*k!-1) then return k fi od
end proc:
map(f, [$1..100]); # Robert Israel, Oct 29 2019

Table[k = 1; While[! PrimeQ[k!*n - 1], k++]; k, {n, 100}] (* T. D. Noe, Nov 18 2013 *)

a(n) = my(k=1); while (!isprime(n*k! - 1), k++); k; \\ Michel Marcus, Oct 29 2019

A261437 Least positive integer k such that kn+1 = prime(p) and k^2n+1 = prime(q) for some pair of primes p and q.

Original entry on oeis.org

2, 1, 286, 1, 7290, 21, 18, 2472, 12, 1, 20460, 20, 20692, 105, 4392, 1, 96816, 1327, 360, 264, 19850, 2734, 1854, 5293, 930, 29526, 98, 622, 9222, 1, 6816, 924, 61614, 70, 53760, 45, 32190, 9687, 5510, 1, 128070, 148, 8772, 23478, 404, 801, 1830, 5, 9912, 7662, 1100, 8211, 1116, 9997, 630, 4965, 936, 1, 87570, 759

Offset: 1

Zhi-Wei Sun, Aug 18 2015

nonn

Conjecture: (i) If n > 0 and r are relatively prime integers, then there are infinitely many positive integers k such that k*n+r = prime(p) for some prime p.
(ii) Let r be 1 or -1. For any integer n > 0, there is a positive integer k such that k*n+r = prime(p) and k^2*n+1 = prime(q) for some primes p and q.
(iii) For any integer n > 0, there is a positive integer k such that n+k = prime(p) and n+k^2 = prime(q) for some primes p and q.
Note that part (i) is a refinement of Dirichlet's theorem on primes in arithmetic progressions. Also, part (ii) implies that a(n) exists for any n > 0.

			a(3) = 286 since 286*3+1 = 859 = prime(149) with 149 prime, and 286^2*3+1 = 245389 = prime(21661) with 21661 prime.

Zhi-Wei Sun, Problems on combinatorial properties of primes, in: M. Kaneko, S. Kanemitsu and J. Liu (eds.), Number Theory: Plowing and Starring through High Wave Forms, Proc. 7th China-Japan Seminar (Fukuoka, Oct. 28 - Nov. 1, 2013), Ser. Number Theory Appl., Vol. 11, World Sci., Singapore, 2015, pp. 169-187.

Zhi-Wei Sun, Table of n, a(n) for n = 1..200
Zhi-Wei Sun, Problems on combinatorial properties of primes, arXiv:1402.6641 [math.NT], 2014.

Cf. A000040, A000290, A034693, A053989, A185636, A204065.

PQ[p_]:=PrimeQ[p]&&PrimeQ[PrimePi[p]]
Do[k=0;Label[bb];k=k+1;If[PQ[k*n+1]&&PQ[k^2*n+1],Goto[aa],Goto[bb]];Label[aa];Print[n," ", k];Continue,{n,1,60}]

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

A047981 a(n) = A047980(2n).

Original entry on oeis.org

3, 7, 17, 71, 19, 59, 167, 757, 197, 159, 799, 227, 317, 415, 361, 521, 3289, 2633, 1637, 1861, 1691, 1997, 2053, 4097, 6437, 5731, 9199, 11603, 5641, 3833, 26885, 6637, 26815, 32117, 18637, 29933, 31667, 5227, 19891, 47303, 54973, 5207, 59537

Offset: 1

Labos Elemer

nonn

			First example: a(1)=3 since in 3k+1 sequence, the first term is 3, a prime and the d=2 is the smallest such difference. The next such progression is 5k+1 because 5*2+1=11 is prime. 2nd example: here at n=6 a(6)=59. This means that 2n=12 occurs first in A034693 at its position 59, which means that its first prime is 12*59+1=709. arises as 12th term (such progressions are: 59k+1,85k+1,133k+1, etc.)

Index entries for sequences related to primes in arithmetic progressions

Cf. A047980, A047982, A034693, A034782 - A034784.

a(n) = min {k}: A034693(a(n)) is an even number such that in a(n)*k+1 progression the first prime occurs at even 2n=k position.

cp's OEIS Frontend

A047980 a(n) is smallest difference d of an arithmetic progression dk+1 whose first prime occurs at the n-th position.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

Maple

Mathematica

Formula

A060940 Triangle in which n-th row gives the phi(n) terms appearing as initial primes in arithmetic progressions with difference n, with initial term equal to the smallest positive residue coprimes to n.

Views

Author

Keywords

Examples

Links

Crossrefs

A072344 a(n) = the least natural number k such that k*phi(n) + 1 is prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A083809 Let f(n) be the smallest prime == 1 mod n (cf. A034694). Sequence gives triangle T(j,k) = f^k(j) for 1 <= k <= j, read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions

A085053 Number of primes of the form nk+1, where k=1 to n; 0 if no such number exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A231820 Least positive k such that n*k! - 1 is a prime, or 0 if no such k exists.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A261437 Least positive integer k such that k*n+1 = prime(p) and k^2*n+1 = prime(q) for some pair of primes p and q.

Views

Author

Keywords

A261437 Least positive integer k such that kn+1 = prime(p) and k^2n+1 = prime(q) for some pair of primes p and q.