A126717 -id:A126717 - cp's OEIS frontend

A035050 a(n) is the smallest k such that k*2^n + 1 is prime.

1, 1, 1, 2, 1, 3, 3, 2, 1, 15, 12, 6, 3, 5, 4, 2, 1, 6, 3, 11, 7, 11, 25, 20, 10, 5, 7, 15, 12, 6, 3, 35, 18, 9, 12, 6, 3, 15, 10, 5, 6, 3, 9, 9, 15, 35, 19, 27, 15, 14, 7, 14, 7, 20, 10, 5, 27, 29, 54, 27, 31, 36, 18, 9, 12, 6, 3, 9, 31, 23, 39, 39, 40, 20, 10, 5, 58, 29, 15, 36, 18, 9, 13

Offset: 0

Labos Elemer

nonn

From Ulrich Krug (leuchtfeuer37(AT)gmx.de), Jun 05 2010: (Start)
If a(i) = 2 * m then a(i+1) = m.
Proof: (I) a(i) = 2*m, 2*m * 2^i + 1 = m*2^(i+1) + 1 prime, so a(i+1) <= m;
(II) if a(i+1) = m-d for an integer d > 0, (m-d) * 2^(i+1) + 1 = (2*m-2*d) * 2^i + 1 prime;
(2m-2d) < 2m contradiction to a(i) = 2 * m, d = 0.
(End)
Conjecture: for n > 0, a(n) = k < 2^n, so k*2^n + 1 is a Proth prime A080076. - Thomas Ordowski, Apr 13 2019

			a(3)=2 because 1*2^3 + 1 = 9 is composite, 2*2^3 + 1 = 17 is prime.
a(99)=219 because 2^99k + 1 is not prime for k=1,2,...,218. The first term which is not a composite number of this arithmetic progression is 2^99*219 + 1.

T. D. Noe, Table of n, a(n) for n = 0..1000
Gareth A. Jones and Alexander K. Zvonkin, Groups of prime degree and the Bateman-Horn conjecture, 2021.
Index entries for sequences related to primes in arithmetic progressions

Analogous case is A034693. Special subscripts (n's for a(n)=1) are the exponents of known Fermat primes: A000215. See also Fermat numbers A000051.

Cf. A007522, A057778, A080076, A085427, A087522, A126717, A127575, A127576, A127577, A127578, A127580, A127581, A127586.

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

a = {}; Do[k = 0; While[ ! PrimeQ[k 2^n + 1], k++ ]; AppendTo[a, k], {n, 0, 100}]; a (* Artur Jasinski *)
Table[Module[{k=1,n2=2^n},While[!PrimeQ[k*n2+1],k++];k],{n,0,90}] (* Harvey P. Dale, May 25 2024 *)

a(n) = {my(k = 1); while (! isprime(2^n*k+1), k++); k;}

a(n) << 19^n by Xylouris' improvement to Linnik's theorem. - Charles R Greathouse IV, Dec 10 2013

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

Original entry on oeis.org

1, 1, 1, 5, 1, 3, 3, 5, 1, 15, 13, 9, 3, 5, 7, 5, 1, 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, 39, 39, 127, 23, 67, 5, 93, 29, 15, 249

Offset: 0

Labos Elemer, Nov 02 2000

nonn

There are no Sierpiński numbers in the sequence. See A076336. - Thomas Ordowski, Aug 13 2017

Conjecture: for n > 0, a(n) = k < 2^n, so k*2^n + 1 is a Proth prime A080076. - Thomas Ordowski, Apr 13 2019

			For n = 10, the first primes in the 1024k + 1 arithmetic progression occur at k = 12, 13, 15, 18, 19, ...; 13 is the first odd number, so a(10)=13, while A035050(10)=12. The corresponding primes are 12289 and 13313.
For n = 79, the first primes in the (2^79)k + 1 = 604462909807314587353088k + 1 progression occur at k = 36, 44, 104, 249, 296, 299, so a(79)=249, the first odd number, while A035050(79)=36. The two primes arising are 21760664753063325144711169 and 150511264542021332250918913, respectively.

T. D. Noe, Table of n, a(n) for n = 0..1000
Poo-Sung Park, Multiplicative functions with f(p + q - n_0) = f(p) + f(q) - f(n_0), arXiv:2002.09908 [math.NT], 2020.
Index entries for sequences related to primes in arithmetic progressions

Terms are not necessarily in A035050.

Cf. A006093, A035050, A076336, A080076 A085427, A126717.

Table[k = 1; While[! PrimeQ[k 2^n + 1], k += 2]; k, {n, 0, 80}] (* Michael De Vlieger, Jul 04 2016 *)

a(n) = k=1; while(!isprime(k*2^n+1), k+=2); k; \\ Michel Marcus, Dec 10 2013

a(n) = Min{k: 1+2^n*k is prime and k is odd}.
a(n) << 19^n by Xylouris's improvement to Linnik's theorem. - Charles R Greathouse IV, Dec 10 2013
Conjecture: a(n) = O(n*log(n)). - Thomas Ordowski, Oct 16 2014

A085427 Least k such that k*2^n - 1 is prime.

Original entry on oeis.org

3, 2, 1, 1, 2, 1, 2, 1, 5, 7, 5, 3, 2, 1, 5, 4, 2, 1, 2, 1, 14, 7, 26, 13, 39, 22, 11, 16, 8, 4, 2, 1, 5, 6, 3, 24, 12, 6, 3, 25, 24, 12, 6, 3, 14, 7, 20, 10, 5, 19, 11, 21, 20, 10, 5, 3, 32, 16, 8, 4, 2, 1, 12, 6, 3, 67, 63, 43, 63, 40, 20, 10, 5, 15, 12, 6, 3, 55, 47, 30, 15, 30, 15, 64, 32, 16, 8

Offset: 0

Jason Earls, Aug 13 2003

nonn

First few pairs (n,k) such that k > n are (1,2), (22,26), (24,39), (65,67), (110,150), (112,140), (135,150), (137,169), ... Also, for n=398 there is an interesting anomaly since k=893 which is > 2n.
Conjecture: for every n there exists a number k < 3n such that k*2^n - 1 is prime. Comment from T. D. Noe: this fails at n=624, where a(n)=2163.
Define sumk = Sum_{n=1..N} k(n), and define sumn = Sum_{n=1..N} n, then as N increases the ratio sumk/sumn tends to log(2)/2 = 0.3465735.... so on average k(n) is about 0.35*n and seems to be always < 3.82*n or 11*log(2)/2. - Pierre CAMI, Feb 27 2009
a(n) = 1 if and only if n is in A000043. - Felix Fröhlich, Sep 14 2014

Pierre CAMI, Table of n, a(n) for n = 0..3000

Cf. A035050, A057778, A126717.

k2np[n_]:=Module[{k=1,x=2^n},While[!PrimeQ[k x-1],k++];k]; Array[ k2np,90,0] (* Harvey P. Dale, Nov 19 2011 *)

lim=10^9; for(n=0, 200, k=1; i=0; while(k < lim, if(ispseudoprime(k*2^n-1), print1(k, ", "); i++; break({1})); if(i==0 && k >= lim-1, print1(">", lim, ", "); i=0); k++)) \\ Felix Fröhlich, Sep 20 2014

a(n) << 19^n by Xylouris's improvement to Linnik's theorem. - Charles R Greathouse IV, Dec 10 2013

A057775 a(n) is the least prime p such that p-1 is divisible by 2^n and not by 2^(n+1).

Original entry on oeis.org

2, 3, 5, 41, 17, 97, 193, 641, 257, 7681, 13313, 18433, 12289, 40961, 114689, 163841, 65537, 1179649, 786433, 5767169, 7340033, 23068673, 104857601, 377487361, 754974721, 167772161, 469762049, 2013265921, 3489660929, 12348030977, 3221225473, 75161927681

Offset: 0

Labos Elemer, Nov 02 2000

nonn

If we drop the requirement that p-1 must not be divisible by 2^(n+1), we get instead A035089, which is a nondecreasing sequence. - Jeppe Stig Nielsen, Aug 09 2015

			a(13) = 40961 = 1 + 8192*5 where the last term is divisible by the 13th power of 2 and 40961 is the smallest prime with that property.

Donovan Johnson, Table of n, a(n) for n = 0..1000

Cf. A000040, A006093, A035050, A035089, A057776, A126717, A201914.

f:= proc(n) local p;
  for p from 2^n+1 by 2^(n+1) do
    if isprime(p) then return p fi
  od
end proc:
map(f, [$0..100]); # Robert Israel, Aug 10 2015

Table[k = 1; While[p = k*2^n + 1; ! PrimeQ[p], k = k + 2]; p, {n, 0, 40}] (* T. D. Noe, Dec 27 2011 *)

a(n)=forstep(k=1,9e99,2,isprime((k<Jeppe Stig Nielsen, Aug 09 2015

a(n) = prime(A057776(n+1)). - Amiram Eldar, Mar 16 2025

More terms from Larry Reeves (larryr(AT)acm.org), Nov 03 2000

A210651 a(n)=least odd number k such that 3k2^n-1 is a prime number.

Original entry on oeis.org

1, 1, 1, 1, 5, 1, 1, 9, 15, 5, 1, 29, 3, 5, 3, 15, 5, 1, 17, 19, 3, 11, 23, 13, 19, 19, 7, 9, 15, 71, 5, 19, 49, 1, 11, 15, 7, 1, 21, 39, 5, 11, 1, 19, 55, 11, 71, 39, 23, 29, 7, 61, 49, 15, 1, 11, 17, 37, 15, 31, 23, 19, 3, 1, 33, 21, 37, 21, 17, 9, 41, 43, 5, 7, 25, 1, 19, 37, 23, 5, 27, 5, 37, 31, 15, 85, 67, 43, 79, 77

Offset: 1

Pierre CAMI, Mar 27 2012

nonn

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

Cf. A126717.

A210651 := proc(n)
        for k from 1 by 2 do
                if isprime(3*k*2^n-1) then
                        return k;
                end if;
        end do:
end proc: # R. J. Mathar, Mar 29 2012

A285808 a(n) = smallest k such that (6k-3)2^n-1 is prime.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 5, 8, 3, 1, 15, 2, 3, 2, 8, 3, 1, 9, 10, 2, 6, 12, 7, 10, 10, 4, 5, 8, 36, 3, 10, 25, 1, 6, 8, 4, 1, 11, 20, 3, 6, 1, 10, 28, 6, 36, 20, 12, 15, 4, 31, 25, 8, 1, 6, 9, 19, 8, 16, 12, 10, 2, 1, 17, 11, 19, 11, 9, 5, 21, 22, 3, 4, 13, 1

Offset: 1

Pierre CAMI, Apr 27 2017

nonn

As N increases, (Sum_{n=1..N} a(n)) / (Sum_{n=1..N} n) tends to log(2)/3 as seen by plotting data; this is consistent with the prime number theorem as the probability that (6*x-3)*2^n - 1 is prime is ~ 3/(n*log(2)) if n is great enough, so after n*log(2)/3 try n*log(2)/3*(3/n*log(2))=1.

For n=1 to 14000, a(n)/n is always < 3.

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

Cf. A126717, A284325.

Table[k = 1; While[! PrimeQ[(6 k - 3)*2^n - 1], k++]; k, {n, 76}] (* Michael De Vlieger, Apr 27 2017 *)

A201914 Least prime p such that p+1 is divisible by 2^n and not by 2^(n+1).

Original entry on oeis.org

2, 5, 3, 7, 47, 31, 191, 127, 1279, 3583, 5119, 6143, 20479, 8191, 81919, 294911, 1114111, 131071, 786431, 524287, 17825791, 14680063, 138412031, 109051903, 654311423, 1912602623, 738197503, 2818572287, 7247757311, 3758096383, 228707008511, 2147483647

Offset: 0

T. D. Noe, Dec 27 2011

nonn

See A126717 for the least k such that k*2^n-1 is prime.

For every n >= 1 there are infinitely many prime numbers p such that p + 1 is divisible by 2^n and not by 2^(n + 1). - Marius A. Burtea, Mar 10 2020

Laurențiu Panaitopol, Alexandru Gica, Arithmetic problems and number theory, Ed. Gil, Zalău, (2006), ch. 13, p. 78, pr. 5 (in Romanian).

Donovan Johnson, Table of n, a(n) for n = 0..1000

Cf. A008864 (primes + 1), A057775 (p-1 case), A126717.

For n>0, sequence is first term of A002144, A007520, A141194, A142041, A142939, ...

a:=[]; for n in [0..31] do k:=1; while not IsPrime(k*2^n-1) do k:=k+2; end while; Append(~a,k*2^n-1); end for; a; // Marius A. Burtea, Mar 10 2020

Table[k = 1; While[p = k*2^n - 1; ! PrimeQ[p], k = k + 2]; p, {n, 0, 40}]

A264097 Smallest odd number k divisible by 3 such that k*2^n-1 is a prime.

Original entry on oeis.org

3, 3, 3, 3, 3, 15, 3, 3, 27, 45, 15, 3, 87, 9, 15, 9, 45, 15, 3, 51, 57, 9, 33, 69, 39, 57, 57, 21, 27, 45, 213, 15, 57, 147, 3, 33, 45, 21, 3, 63, 117, 15, 33, 3, 57, 165, 33, 213, 117, 69, 87, 21, 183, 147, 45, 3, 33, 51, 111, 45, 93, 69, 57, 9, 3, 99, 63

Offset: 0

Pierre CAMI, Nov 03 2015

nonn

As N increases, (Sum_{n=1..N} a(n))/(Sum_{n=1..N} n) appears to tend to 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 where k is a multiple of 3 is 1/(2*(n*log(2)+log(k))) ~ 1/(2*n*log(2)).

			3*2^0-1=2 prime so a(0)=3.
3*2^1-1=5 prime so a(1)=3.
3*2^2-1=11 prime so a(2)=3.
3*2^3-1=23 prime so a(3)=3.

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

Cf. A256787, A085427, A126717.

Table[k = 3; While[! PrimeQ[k 2^n - 1], k += 6]; k, {n, 0, 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

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

A276121 Smallest odd integer k such that k*2^prime(n)-1 is a prime number.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 1, 13, 7, 1, 21, 15, 3, 31, 147, 45, 1, 43, 73, 15, 69, 91, 1, 51, 81, 3, 1, 9, 85, 1, 55, 169, 225, 109, 145, 15, 103, 615, 69, 259, 69, 63, 45, 285, 471, 9, 255, 169, 489, 69, 273, 427, 43, 391, 169, 201, 21, 159, 181, 103, 15, 339

Offset: 1

Pierre CAMI, Aug 21 2016

nonn

When k=1 the prime k*2^prime(n)-1 is a Mersenne prime.

			1*2^7-1 = 127 prime so a(4) = 1 as prime(4)=7.
1*2^11-1 = 2047 composite, 3*2^11-1 = 6143 prime so a(5) = 3 as prime(5)=11.

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

Cf. A000043, A126717.

Table[k = 1; While[! PrimeQ[k 2^Prime@ n - 1], k += 2]; k, {n, 63}] (* Michael De Vlieger, Aug 21 2016 *)

a(n) = {my(k=1); while (!isprime(k*2^prime(n)-1), k+=2); k;} \\ Michel Marcus, Aug 21 2016

a(n) = A126717(prime(n)). - Michel Marcus, Sep 07 2016

cp's OEIS Frontend

A035050 a(n) is the smallest k such that k*2^n + 1 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A085427 Least k such that k*2^n - 1 is prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A057775 a(n) is the least prime p such that p-1 is divisible by 2^n and not by 2^(n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A210651 a(n)=least odd number k such that 3*k*2^n-1 is a prime number.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A285808 a(n) = smallest k such that (6*k-3)*2^n-1 is prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A201914 Least prime p such that p+1 is divisible by 2^n and not by 2^(n+1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

A264097 Smallest odd number k divisible by 3 such that k*2^n-1 is a prime.

A210651 a(n)=least odd number k such that 3k2^n-1 is a prime number.

A285808 a(n) = smallest k such that (6k-3)2^n-1 is prime.