A035050 -id:A035050 - cp's OEIS frontend

A247479 Smallest odd k > 1 such that k*2^n+1 is a prime number.

3, 3, 5, 7, 3, 3, 5, 3, 15, 13, 9, 3, 5, 7, 5, 21, 9, 3, 11, 7, 11, 25, 45, 45, 5, 7, 15, 13, 23, 3, 35, 43, 9, 75, 59, 3, 15, 15, 5, 27, 3, 9, 9, 15, 35, 19, 27, 15, 23, 7, 17, 7, 51, 49, 5, 27, 29, 99, 27, 31, 53, 105, 9, 25, 9, 3, 9, 31, 23

Offset: 1

Pierre CAMI, Dec 01 2014

nonn

Differs from A057778 only where n is related to a Fermat prime (A019434). - R. J. Mathar, Dec 02 2014

Records: 3, 5, 7, 15, 21, 25, 45, 75, 99, 105, 127, 249, 321, 363, 411, 421, 535, 823, 1383, 1875, 2375, 2443, 2865, 4063, 4141, 4239, 4623, 5175, 5469, 14319, 15979, 17817, 25925, 30487, 39741, 48055, 49709, 50721, 55367, ... . - Robert G. Wilson v, Feb 02 2015

Robert G. Wilson v, Table of n, a(n) for n = 1..10111 (first 5150 terms from Pierre CAMI)

Cf. A035050, A057778, A247202, A253398.

A247479:= proc(n) local k;
      for k from 3 by 2 do if isprime(k*2^n+1) then return k fi od
   end proc:
seq(A247479(n),n=1..100); # Robert Israel, Dec 01 2014

f[n_] := Block[{k = 3, p = 2^n}, While[ !PrimeQ[k*p + 1], k += 2]; k]; Array[f, 70] (* Robert G. Wilson v, Jan 29 2015 *)

a(n) = {k = 3; while (! isprime(k*2^n+1), k += 2); k;} \\ Michel Marcus, Dec 01 2014

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

A085245 Least k such that k*2^n + 1 is a semiprime.

Original entry on oeis.org

4, 2, 1, 2, 1, 1, 1, 6, 3, 2, 1, 1, 1, 6, 3, 2, 1, 2, 1, 1, 3, 2, 1, 3, 8, 4, 2, 1, 3, 2, 1, 1, 3, 7, 5, 5, 8, 4, 2, 1, 4, 2, 1, 3, 3, 7, 6, 3, 15, 9, 29, 28, 14, 7, 6, 3, 3, 8, 4, 2, 1, 4, 2, 1, 14, 7, 12, 6, 3, 3, 9, 5, 12, 6, 3, 8, 4, 2, 1, 3, 29, 18, 9, 18, 9, 10, 5, 13, 8, 4, 2, 1, 15, 12, 6, 3, 9, 6

Offset: 1

Jason Earls, Aug 11 2003

nonn

The first few values of n such that 78557*2^n + 1 is a semiprime, where k = 78557 (the conjectured smallest Sierpinski number), are: 2, 3, 7, 15, 17, 18, 24, 60, 71, 89, 92, 107, 140, 143, 163,... Conjecture: there are infinitely many semiprimes of this form.

			a(51)=29 because k*2^51 + 1 is not a semiprime for k=1,2,...28, but 29*2^51 + 1 = 63839 * 1022920073887 is.

Sean A. Irvine, Table of n, a(n) for n = 1..500

Cf. A001358, A035050, A076336.

a(n) = my(k=1); while (bigomega(k*2^n + 1) != 2, k++); k; \\ Michel Marcus, Jul 02 2020

A127597 Least number k such that k 4^n + (4^n-1)/3 is prime.

Original entry on oeis.org

2, 1, 0, 2, 3, 2, 4, 4, 3, 10, 3, 3, 2, 7, 2, 25, 6, 17, 4, 13, 3, 20, 36, 20, 11, 27, 66, 23, 39, 24, 19, 13, 3, 10, 6, 122, 71, 58, 24, 13, 3, 2, 41, 10, 6, 32, 58, 17, 4, 79, 26, 55, 36, 48, 31, 28, 9, 2, 76, 24, 32, 28, 63, 20, 37, 9, 2, 7, 39, 10, 91, 47

Offset: 0

Artur Jasinski, Jan 19 2007

nonn

Michael S. Branicky, Table of n, a(n) for n = 0..2391

Cf. A035050, A007522, A127575, A127576, A127577, A127578, A127580, A127581, A087522, A127586, A127587, A127589, A127590, A127591, A127592, A127593, A127594, A127598.

a = {}; Do[k = 0; While[ !PrimeQ[k 4^n + (4^n - 1)/3], k++ ]; AppendTo[a, k], {n, 0, 50}]; a (*Artur Jasinski*)
lnk[n_]:=Module[{k=0,n4=4^n},While[!PrimeQ[k*n4+(n4-1)/3],k++];k]; Array[ lnk,60,0] (* Harvey P. Dale, May 28 2018 *)

from sympy import isprime
def a(n):
    k, fourn = 0, 4**n
    while not isprime(k*fourn + (fourn-1)//3): k += 1
    return k
print([a(n) for n in range(72)]) # Michael S. Branicky, May 18 2022

Offset corrected and a(51) and beyond from Michael S. Branicky, May 18 2022

A225911 Smallest k such that k*6^n+1 is prime.

Original entry on oeis.org

1, 1, 2, 1, 10, 3, 3, 3, 12, 2, 2, 15, 17, 11, 3, 8, 2, 10, 12, 2, 73, 35, 21, 11, 18, 3, 12, 2, 3, 28, 48, 8, 11, 31, 17, 102, 17, 7, 17, 8, 2, 35, 13, 135, 33, 72, 12, 2, 18, 3, 26, 17, 38, 16, 51, 12, 2, 2, 2, 40, 103, 45, 26, 40, 16, 3, 10, 26, 10, 8, 2, 11

Offset: 1

Pierre CAMI, May 20 2013

nonn

In average k~0.6*n and 0 < k < 8*n until a proof that k may be > 8*n.

Dirichlet's theorem proves that a(n) exists for each n. Linnik's theorem gives bounds; in particular the version due to Xylouris gives a(n) << 1855^n. - Charles R Greathouse IV, May 20 2013

			6^1+1=7 is prime, so  a(1)=1;
6^2+1=37 is prime, so a(2)=1;
6^3+1=217 is composite, 2*6^3+1=433 is prime, so a(3)=2.

Cf. A225941, A035050.

S:=[]; for n in [1..100] do k:=1; while not IsPrime(k*6^n+1) do k:=k+1; end while; Append(~S, k); end for; S; // Bruno Berselli, May 20 2013

skp[n_]:=Module[{k=1,c=6^n},While[!PrimeQ[k*c+1],k++];k]; Array[skp,80] (* Harvey P. Dale, Jun 17 2025 *)

a(n)=my(k);while(!ispseudoprime(k++*6^n+1),);k \\ Charles R Greathouse IV, May 20 2013

A239676 Least k such that k*3^n+1 is prime.

Original entry on oeis.org

1, 2, 2, 4, 2, 2, 2, 8, 6, 2, 8, 28, 10, 12, 4, 4, 2, 2, 10, 20, 26, 24, 8, 48, 16, 34, 14, 14, 18, 6, 2, 26, 26, 14, 22, 26, 16, 22, 12, 4, 62, 64, 68, 88, 70, 56, 34, 96, 32, 50, 20, 24, 8, 6, 2, 18, 6, 2, 8, 6, 2, 42, 14, 18, 6, 2, 98, 66, 22, 70, 74, 80, 68, 52

Offset: 0

Derek Orr, Mar 23 2014

nonn

All numbers in this sequence, except for a(0), are even.

			1*3^1+1 = 4 is not prime. 2*3^1+1 = 7 is prime. Thus, a(1) = 2.
1*3^3+1 = 28 is not prime. 2*3^3+1 = 57 is not prime. 3*3^3+1 = 82 is not prime. 4*3^3+1 = 109 is prime. Thus, a(3) = 4.

Marius A. Burtea, Table of n, a(n) for n = 0..1000

Cf. A003306 (where k=2), A035050 (k*2^n+1 is prime).

sol:=[];m:=1; for n in [0..73] do k:=0; while not IsPrime(k*3^n+1) do k:=k+1; end while; sol[m]:=k; m:=m+1; end for; sol; // Marius A. Burtea, Jun 05 2019

lk[n_]:=Module[{k=1,t=3^n},While[!PrimeQ[k*t+1],k++];k]; Array[lk,80,0] (* Harvey P. Dale, May 11 2025 *)

for(n=0, 100, k=0; while(!isprime(k*3^n+1), k++); print1(k, ", ")) \\ Colin Barker, Mar 24 2014

import sympy
from sympy import isprime
def Pow3(n):
  for k in range(10**4):
    if isprime(k*(3**n)+1):
      return n
n = 1
while n < 100:
  print(Pow3(n))
  n += 1

A264098 Smallest odd number k divisible by 3 such that k*2^n + 1 is prime.

Original entry on oeis.org

3, 3, 9, 15, 3, 3, 9, 3, 15, 15, 9, 3, 33, 9, 81, 21, 9, 3, 27, 27, 33, 27, 45, 45, 33, 27, 15, 33, 45, 3, 39, 81, 9, 75, 81, 3, 15, 15, 81, 27, 3, 9, 9, 15, 189, 27, 27, 15, 105, 27, 75, 93, 51, 177, 57, 27, 75, 99, 27, 45, 105, 105, 9, 27, 9, 3, 9, 237

Offset: 1

Pierre CAMI, Nov 03 2015

nonn

As N increases, (Sum_{n=1..N} a(n))/(Sum_{n=1..N} n) appears to approach 2*log(2), as can be seen by plotting the first 31000 terms.

This observation is consistent with the prime number theorem as the probability that k*2^n+1 is prime is 1/(n*log(2)+log(k))/2 for k multiple of 3 so ~ 1/(2*n*log(2)) as n increases, if k ~ 2*n*log(2) then k/(2*n*log(2)) ~ 1.

			3*2^1 + 1 = 7 is prime so a(1) = 3.
3*2^2 + 1 = 13 is prime so a(2) = 3.
3*2^3 + 1 = 25 is composite; 9*2^3 + 1 = 73 is prime so a(3) = 9.

Pierre CAMI, Table of n, a(n) for n = 1..31000

Cf. A035050, A057778, A264097.

for n from 1 to 100 do
  for k from 3 by 6 do
    if isprime(k*2^n+1) then
      A[n]:= k; break
   fi
 od
od:
seq(A[n],n=1..100); # Robert Israel, Jan 22 2016

Table[k = 3; While[! PrimeQ[k 2^n + 1], k += 6]; k, {n, 68}] (* Michael De Vlieger, Nov 03 2015 *)

a(n) = {k = 3; while (!isprime(k*2^n+1), k += 6); k;} \\ Michel Marcus, Nov 03 2015

A074717 Least k such that floor(2^n/k) is prime.

Original entry on oeis.org

1, 2, 3, 3, 6, 9, 11, 11, 7, 9, 5, 10, 19, 11, 5, 10, 9, 11, 22, 35, 39, 9, 5, 10, 20, 27, 11, 19, 9, 18, 36, 25, 29, 27, 5, 10, 20, 40, 61, 13, 21, 42, 29, 27, 39, 9, 17, 29, 58, 49, 27, 25, 50, 11, 22, 44, 39, 11, 22, 44, 29, 58, 116, 53, 19, 38, 76, 152, 237, 139, 5, 10, 20

Offset: 1

Benoit Cloitre, Sep 04 2002

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

Cf. A013597, A013603, A035050, A085427.

a[n_] := Module[{k = 1}, While[! PrimeQ @ Floor[2^n/k], k++]; k]; Array[a, 100] (* Amiram Eldar, Aug 31 2020 *)

a(n)=if(n<0,0,k=1; while(isprime(floor(2^n/k)) == 0,k++); k)

There is probably a constant c such that Sum_{i=1..n} a(i) is asymptotic to c*n^2 (0 < c < 1/2).

A127598 Least primes of the form k 4^n + (4^n-1)/3.

Original entry on oeis.org

2, 5, 5, 149, 853, 2389, 17749, 70997, 218453, 2708821, 3495253, 13981013, 39146837, 492131669, 626349397, 27201459541, 27201459541, 297784399189, 297784399189, 3665038759253, 3665038759253, 89426945725781

Offset: 1

Artur Jasinski, Jan 19 2007

nonn

Cf. A035050, A007522, A127575, A127576, A127577, A127578, A127580, A127581, A087522, A127586, A127587, A127589, A127590, A127591, A127592, A127593, A127594, A127597.

a = {}; Do[k = 0; While[ !PrimeQ[k 4^n + (4^n - 1)/3], k++ ]; AppendTo[a, k 4^n + (4^n - 1)/3], {n, 0, 50}]; a (*Artur Jasinski*)

A334296 Smallest k such that (2k+1)*2^n+1 is prime.

Original entry on oeis.org

0, 0, 0, 2, 0, 1, 1, 2, 0, 7, 6, 4, 1, 2, 3, 2, 0, 4, 1, 5, 3, 5, 12, 22, 22, 2, 3, 7, 6, 11, 1, 17, 21, 4, 37, 29, 1, 7, 7, 2, 13, 1, 4, 4, 7, 17, 9, 13, 7, 11, 3, 8, 3, 25, 24, 2, 13, 14, 49, 13, 15, 26, 52, 4, 12, 4, 1, 4, 15, 11, 19, 19, 63, 11, 33, 2, 46

Offset: 0

Mike Speciner, Apr 21 2020

nonn

A057775 is the corresponding sequence of primes.

			a(0)=a(1)=a(2)=0 because 2^0+1=2, 2^1+1=3, 2^2+1=5 are prime.
a(3)=2 because 2^8+1=9 and 3*2^8+1=25 are not prime, but 5*2^8+1=41 is.

Robert Israel, Table of n, a(n) for n = 0..2000

Cf. A057778, A057775, A035050, A035089.

f:= proc(n) local t, v, k;
   t:= 2^n; v:= -t+1;
   for k from 0 do
      v:= v+2*t;
      if isprime(v) then return k fi
   od
end proc:
map(f, [$0..100]); # Robert Israel, Jul 14 2020

a[n_] := Block[{k = 0}, While[! PrimeQ[(2 k + 1) 2^n + 1], k++]; k]; Array[a, 77, 0] (* Giovanni Resta, May 08 2020 *)

a(n) = my(k=0); while (!isprime((2*k+1)*2^n+1), k++); k; \\ Michel Marcus, Apr 30 2020

from itertools import count
from sympy import isprime
def pow2p1() : # generates the sequence
  for n in count() :
    for k in count() :
      if isprime(((2*k+1)<

a(n) = (A057778(n)-1)/2.

a(n) = ((A057775(n)-1)/2^n-1)/2.

cp's OEIS Frontend

A247479 Smallest odd k > 1 such that k*2^n+1 is a prime number.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

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

A085245 Least k such that k*2^n + 1 is a semiprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A127597 Least number k such that k 4^n + (4^n-1)/3 is prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A225911 Smallest k such that k*6^n+1 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

A239676 Least k such that k*3^n+1 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

A264098 Smallest odd number k divisible by 3 such that k*2^n + 1 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI