A057778 -id:A057778 - 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

A204620 Numbers k such that 3*2^k + 1 is a prime factor of a Fermat number 2^(2^m) + 1 for some m.

Original entry on oeis.org

41, 209, 157169, 213321, 303093, 382449, 2145353, 2478785

Offset: 1

Arkadiusz Wesolowski, Jan 17 2012

Terms are odd: by Morehead's theorem, 3*2^(2*n) + 1 can never divide a Fermat number.
No other terms below 7516000.
Is this sequence the same as "Numbers k such that 3*2^k + 1 is a factor of a Fermat number 2^(2^m) + 1 for some m"? - Arkadiusz Wesolowski, Nov 13 2018
The last sentence of Morehead's paper is: "It is easy to show that composite numbers of the forms 2^kappa * 3 + 1, 2^kappa * 5 + 1 can not be factors of Fermat's numbers." [a proof is needed]. - Jeppe Stig Nielsen, Jul 23 2019
Any factor of a Fermat number 2^(2^m) + 1 of the form 3*2^k + 1 is prime if k < 2*m + 6. - Arkadiusz Wesolowski, Jun 12 2021
If, for any m >= 0, F(m) = 2^(2^m) + 1 has a prime factor p of the form 3*2^k + 1, then F(m)/p is congruent to 11 mod 30. - Arkadiusz Wesolowski, Jun 13 2021
A number k belongs to this sequence if and only if the order of 2 modulo p is not divisible by 3, where p is a prime of the form 3*2^k + 1 (see Golomb paper). - Arkadiusz Wesolowski, Jun 14 2021

Solomon W. Golomb, Properties of the sequence 3.2^n+1, Math. Comp., 30 (1976), 657-663.
Wilfrid Keller, Fermat factoring status
J. C. Morehead, Note on the factors of Fermat's numbers, Bull. Amer. Math. Soc., Volume 12, Number 9 (1906), pp. 449-451.
Eric Weisstein's World of Mathematics, Fermat Number

Subsequence of A002253.

Cf. A000215, A039687, A057775, A057778, A201364, A226366.

lst = {}; Do[p = 3*2^n + 1; If[PrimeQ[p] && IntegerQ@Log[2, MultiplicativeOrder[2, p]], AppendTo[lst, n]], {n, 7, 209, 2}]; lst

isok(n) = my(p = 3*2^n + 1, z = znorder(Mod(2, p))); isprime(p) && ((z >> valuation(z, 2)) == 1); \\ Michel Marcus, Nov 10 2018

A226366 Numbers k such that 5*2^k + 1 is a prime factor of a Fermat number 2^(2^m) + 1 for some m.

Original entry on oeis.org

7, 25, 39, 75, 127, 1947, 3313, 23473, 125413

Offset: 1

Arkadiusz Wesolowski, Jun 05 2013

No other terms below 5330000.

The reason all terms are odd is that if k is even, then 5*2^k + 1 == (-1)*(-1)^k + 1 = (-1)*1 + 1 = 0 (mod 3). So if k is even, then 3 divides 5*2^k + 1, and since 3 divides no other Fermat number than F_0=3 itself, we do not have a Fermat factor. - Jeppe Stig Nielsen, Jul 21 2019

Wilfrid Keller, Fermat factoring status
J. C. Morehead, Note on the factors of Fermat's numbers, Bull. Amer. Math. Soc., Volume 12, Number 9 (1906), pp. 449-451.
Eric Weisstein's World of Mathematics, Fermat Number

Subsequence of A002254.

Cf. A000215, A050526, A057775, A057778, A201364, A204620.

lst = {}; Do[p = 5*2^n + 1; If[PrimeQ[p] && IntegerQ@Log[2, MultiplicativeOrder[2, p]], AppendTo[lst, n]], {n, 7, 3313, 2}]; lst

isok(n) = my(p = 5*2^n + 1, z = znorder(Mod(2, p))); isprime(p) && ((z >> valuation(z, 2)) == 1); \\ Michel Marcus, Nov 10 2018

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

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

Original entry on oeis.org

3, 3, 1, 1, 3, 1, 3, 1, 5, 7, 5, 3, 5, 1, 5, 9, 17, 1, 3, 1, 17, 7, 33, 13, 39, 57, 11, 21, 27, 7, 213, 1, 5, 31, 3, 25, 17, 21, 3, 25, 107, 15, 33, 3, 35, 7, 23, 31, 5, 19, 11, 21, 65, 147, 5, 3, 33, 51, 77, 45, 17, 1, 53, 9, 3, 67, 63, 43, 63, 51, 27, 73, 5, 15, 21, 25, 3, 55, 47, 69

Offset: 0

Bernardo Boncompagni, Feb 13 2007

nonn

If a(n)=1 then n is a Mersenne exponent (A000043). - Pierre CAMI, Apr 22 2013
From Pierre CAMI, Apr 03 2017: (Start)
Empirically, as N increases, (Sum_{n=1..N} a(n)) / (Sum_{n=1..N} n) tends to log(2); this is consistent with the prime number theorem as the probability that x*2^n - 1 is prime is ~ 1/(n*log(2)) if n is large enough.
For n=1 to 10000, a(n)/n < 7.5.
a(n)*2^n - 1 and a(n)*2^n + 1 are twin primes for n = 1, 2, 6, 18, 22, 63, 211, 282, 546, 726, 1032, 1156, 1321, 1553, 2821, 4901, 6634, 8335, 8529; corresponding values of a(n) are 3, 1, 3, 3, 33, 9, 9, 165, 297, 213, 177, 1035, 1065, 291, 6075, 2403, 2565, 4737, 3975, 459. (End)

			a(10)=5 because 5*2^10-1 is prime but 1*2^10-1 and 3*2^10-1 are not.

Pierre CAMI, Table of n, a(n) for n = 0..10000 (first 1000 terms from T. D. Noe)
Ray Ballinger, Proth Search Page
Poo-Sung Park, Multiplicative functions with f(p + q - n_0) = f(p) + f(q) - f(n_0), arXiv:2002.09908 [math.NT], 2020.

Cf. A035050, A057778, A085427, A284631.

f[n_] := Block[{k = 1}, While[ !PrimeQ[k*2^n - 1], k += 2]; k]; Table[f@n, {n, 0, 80}] (* Robert G. Wilson v, Feb 20 2007 *)

a(n) = {my(k=1); while(!isprime(k*2^n - 1), k+=2); k}; \\ Indranil Ghosh, Apr 03 2017

from sympy import isprime
def a(n):
    k=1
    while True:
        if isprime(k*2**n - 1): return k
        k+=2
print([a(n) for n in range(101)]) # Indranil Ghosh, Apr 03 2017

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

Conjecture: a(n) = O(n log n). - Thomas Ordowski, Oct 15 2014

More terms from Robert G. Wilson v, Feb 20 2007

A201364 Numbers k such that A057775(k) is the factor of a Fermat number 2^(2^m) + 1 for some m.

Original entry on oeis.org

1, 2, 4, 7, 8, 14, 16, 25, 39, 41, 57, 67, 75, 120, 127, 147, 209, 229, 231, 290, 302, 320, 455, 547, 558, 747, 1553, 1947, 2027, 2458, 3313, 3508, 4262, 4727, 6210, 6393, 6539, 6838, 7312, 8242, 8557, 9431, 9450, 12189, 13252, 14254, 14280, 15164, 17909, 18759

Offset: 1

Arkadiusz Wesolowski, Nov 30 2011

nonn

Indices of Fermat factors in A057775.

Arkadiusz Wesolowski, Table of n, a(n) for n = 1..57
Wilfrid Keller, Fermat factoring status
Eric Weisstein's World of Mathematics, Fermat Number

Cf. A000215, A057775, A057778.

lst = {}; Do[k = 1; While[! PrimeQ[p = (2*k - 1)*2^n + 1], k++]; If[IntegerQ[Log[2, MultiplicativeOrder[2, p]]], AppendTo[lst, n]], {n, 320}]; lst

isok(n)=my(k=-1, p(k)=k*2^n+1, z(k)=znorder(Mod(2, p(k)))); until(isprime(p(k)), k=k+2); z(k)>>valuation(z(k), 2)==1; \\ Arkadiusz Wesolowski, May 26 2023

a(44)-a(50) from Arkadiusz Wesolowski, May 26 2023

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

Original entry on oeis.org

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

A057776 a(n) is the least number k such that prime(k) - 1 is divisible by 2^(n-1) and the quotient is odd.

Original entry on oeis.org

1, 2, 3, 13, 7, 25, 44, 116, 55, 974, 1581, 2111, 1470, 4289, 10847, 15000, 6543, 91466, 62947, 397907, 498178, 1452314, 6025010, 20197904, 38946356, 9385401, 24843812, 98842359, 166808880, 556542914, 154570517, 3132108468, 7417604438, 3217817383, 47999122016

Offset: 1

Labos Elemer, Nov 02 2000

nonn

			For n = 1, a(1) = 1, prime(a(1)) = prime(1) = 2 and prime(1)-1 = 1 is divisible by 2^(n-1) = 2^0 = 1; moreover 2 is the smallest.
For n = 10, a(10) = 974, the 974th prime is 7681, prime(974) - 1 = 7680 = 512*15, is divisible by 2^9 = 512 and the quotient is 15, and there are no other primes such this below 7681.
A057775(30) = 12348030977; a(30) = 556542914. It means that 12348030977 is the 556542914th prime. A057777(30) = 12348030976; when A057777(30) is divided by 2^29, the quotient is 23 = A057778(30).

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

Cf. A000040, A000720, A006093, A057773, A057775, A057776, A057777, A057778.

a(n) = PrimePi(A057775(n-1)). - Amiram Eldar, Mar 16 2025

a(32)-a(35) from Amiram Eldar, Mar 16 2025

A280003 Numbers k such that 7*2^k + 1 is a prime factor of a Fermat number 2^(2^m) + 1 for some m.

Original entry on oeis.org

14, 120, 290, 320, 95330, 2167800

Offset: 1

Arkadiusz Wesolowski, Feb 21 2017

18233956 belongs to this sequence, but its position is currently unknown. - Jeppe Stig Nielsen, Oct 05 2020

Proth Search Page, Prime factors of Fermat numbers
Eric Weisstein's World of Mathematics, Fermat Number

Subsequence of A032353.

Cf. A000215, A050527, A057778, A201364, A204620, A226366, A280004.

IsInteger := func; [n: n in [1..320] | IsPrime(k) and IsInteger(Log(2, Modorder(2, k))) where k is 7*2^n+1];

A295639 Smallest k not divisible by 3 such that k*3^n + 1 is prime.

Original entry on oeis.org

2, 2, 4, 2, 2, 2, 8, 8, 2, 8, 28, 10, 64, 4, 4, 2, 2, 10, 20, 26, 56, 8, 104, 16, 34, 14, 14, 20, 26, 2, 26, 26, 14, 22, 26, 16, 22, 50, 4, 62, 64, 68, 88, 70, 56, 34, 146, 32, 50, 20, 314, 8, 40, 2, 70, 22, 2, 8, 40, 2, 64, 14, 136, 100, 2

Offset: 1

Pierre CAMI, Nov 25 2017

nonn

The ratio (Sum_(n=1..t) a(n)) / (Sum_(n=1..t) n) tends to log(3) as t increases.

Differs from A239676 when A239676(n) is a multiple of 3. - Michel Marcus, Nov 25 2017

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

Cf. A057778, A239676, A295640, A295641.

f:= proc(n) local i,j,k,t;
  t:= 3^n;
  for i from 0 do
    for j in [2,4] do
      if isprime((6*i+j)*t+1) then return 6*i+j fi
  od od
end proc:
map(f, [$1..100]); # Robert Israel, Dec 14 2017

f[n_] := Block[{k = 2}, While[If[Mod[k, 3] == 0, k+=2]; ! PrimeQ[k*3^n + 1], k+=2]; k]; Array[f, 65] (* Robert G. Wilson v, Dec 12 2017 *)

a(n) = {k = 1; while (!isprime(k*3^n+1), k++; if (! (k%3), k++)); k;} \\ Michel Marcus, Nov 25 2017

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

A204620 Numbers k such that 3*2^k + 1 is a prime factor of a Fermat number 2^(2^m) + 1 for some m.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A226366 Numbers k such that 5*2^k + 1 is a prime factor of a Fermat number 2^(2^m) + 1 for some m.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A201364 Numbers k such that A057775(k) is the factor of a Fermat number 2^(2^m) + 1 for some m.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica