A080076 -id:A080076 - cp's OEIS frontend

A046808 a(n) is the least integer greater than a(n-1) such that a(n-1)*2^a(n) + 1 is prime, a(1) = 1.

1, 2, 3, 5, 7, 14, 19, 46, 48, 62, 67, 74, 81, 89, 589, 2090, 2299, 7742, 1925975, 1989191, 2008551, 4371904, 6487918

Offset: 1

Chad Davis (cad16(AT)po.cwru.edu)

Previous name was: Recursive sequence of indices of Proth primes a*2^b + 1.

Chris K. Caldwell, The Prime Pages, 3871*2^1925976+1 (7742*2^1925975+1)
Chris K. Caldwell, The Prime Pages, 1925975*2^1989191+1
Chris K. Caldwell, The Prime Pages, 1989191*2^2008551+1
Chris K. Caldwell, The Prime Pages, 2008551*2^4371904+1
Chris K. Caldwell, The Prime Pages, 68311*2^6487924+1 (4371904*2^6487918+1)
Y. Gallot, Proth.exe: Windows Program for Finding Large Primes

t = {a = 1}; Do[If[PrimeQ[a*2^n + 1], AppendTo[t, a = n]], {n, 2, 2300}]; t (* Jayanta Basu, Jun 29 2013 *)

a=1; until(, print1(a, ", "); for(b=a+1, +oo, if(ispseudoprime(a*2^b+1), a=b; break())))

from gmpy2 import is_prime
from itertools import count, islice
def agen(): # generator of terms
    an = 1
    while True:
        yield an
        an = next(k for k in count(an+1) if is_prime(an*(1<Michael S. Branicky, Aug 12 2025

a(19) from Kellen Shenton, May 08 2022
a(20) from Kellen Shenton, May 14 2022
a(21)-a(22) from Kellen Shenton, Feb 21 2025
New name, new offset and a(23) from Kellen Shenton, Aug 10 2025

A083391 n-th Payam number E_{-}(n), defined as the smallest positive odd integer k such that for every positive integer n, the number k*2^n-1 is not divisible by any primes p such that the multiplicative order of 2 mod p is less than or equal to e.

Original entry on oeis.org

3, 3, 45, 45, 45, 45, 45, 45, 2145, 2805, 92235, 92235, 92235, 92235, 92235, 92235, 529815, 529815, 529815, 529815, 529815, 529815, 529815, 529815, 1426425, 1426425, 247016055, 247016055, 247016055, 247016055

Offset: 2

David Terr, Jun 11 2003

nonn

Payam numbers yield many primes of the form k*2^n+1 (Proth primes) and k*2^n-1.

			E_{-}(4) = 45 because 45 is the smallest odd integer k such that for every nonnegative integer n, k*2^n-1 is not divisible by 3, 5, or 7, the only primes p for which the multiplicative order of 2 mod p is less than or equal to 4.

Robert Smith, A coordinated search for primes in the Payam number series.
Eric Weisstein's World of Mathematics, Payam Number

Cf. A083556.

Cf. A080076.

A083556 n-th Payam number E_{+}(n), defined as the smallest positive odd integer k such that for every positive integer n, the number k*2^n+1 is not divisible by any primes p such that the multiplicative order of 2 mod p is less than or equal to e.

Original entry on oeis.org

3, 9, 15, 105, 105, 105, 105, 105, 165, 165, 75075, 75075, 75075, 75075, 75075, 75075, 855855, 855855, 5583435, 5583435, 5583435, 18625035, 18625035, 18625035, 18625035, 18625035, 27183585, 27183585, 27183585, 27183585, 27183585

Offset: 2

David Terr, Jun 10 2003

Payam numbers are good candidates for looking for Proth primes, i.e. primes of the form k*2^n+1

			E_{+}(3) = 9 because 9 is the smallest odd integer k such that for every nonnegative integer n, k*2^n+1 is not divisible by 3 or 7, the only primes p for which the multiplicative order of 2 mod p is less than or equal to 3.

Author?, Title?
Eric Weisstein's World of Mathematics, Payam Number

Cf. A080076.

Cf. A083391.

A214120 Number of Proth primes < 2^n.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 7, 9, 12, 17, 21, 27, 33, 50, 62, 84, 110, 148, 182, 253, 327, 467, 610, 855, 1097, 1548, 1999, 2849, 3648, 5231, 6761, 9781, 12631, 18293, 23770, 34407, 44704, 64911, 84734, 122742, 160055, 233124, 303882, 442949, 578588, 843890, 1103500

Offset: 1

Arkadiusz Wesolowski, Jul 04 2012

nonn

			a(5) = 4 since first 4 Proth primes are 3, 5, 13, 17 all < 2^5.

Chris Caldwell, The Top 20 Proth Primes
Chris Caldwell, The Prime Glossary, Proth prime

Cf. A080076.

lst2 = {}; r = 47; lst1 = Union[Flatten@Table[Select[1 + 2^k*Range[1, 2^Min[k, r - k], 2], # < 2^r && PrimeQ[#] &], {k, r}]]; Do[AppendTo[lst2, Length@Select[lst1, # < 2^n &]], {n, r}]; lst2

a(n)=my(c=0); for(m=1, n-1, k=1; until(k>2^m, p=k*2^m+1; if(p>2^n, break); if(isprime(p), c++); k=k+2)); c; \\ Arkadiusz Wesolowski, Mar 14 2014

A239234 Number of Proth primes < 10^n.

Original entry on oeis.org

0, 2, 6, 17, 36, 99, 249, 651, 1774, 5018, 13587, 39170, 115968, 323061, 953827, 2870277, 8165537, 24569821

Offset: 0

Arkadiusz Wesolowski, Mar 13 2014

nonn

			a(2) = 6 since first 6 Proth primes are 3, 5, 13, 17, 41, 97 all < 10^2.

Chris Caldwell, The Top 20 Proth Primes
Chris Caldwell, The Prime Glossary, Proth prime

Cf. A080076.

a(n)=my(c=0); for(m=1, floor(n*log(10)/log(2)), k=1; until(k>2^m, p=k*2^m+1; if(p>10^n, break); if(isprime(p), c++); k=k+2)); c;

A268353 a(n) is the exponent of 2 corresponding to the n-th Proth prime.

Original entry on oeis.org

1, 2, 2, 4, 3, 5, 4, 6, 4, 8, 5, 6, 6, 7, 5, 8, 5, 7, 6, 7, 6, 6, 7, 6, 6, 8, 7, 7, 7, 7, 7, 9, 8, 8, 7, 7, 7, 9, 7, 9, 7, 12, 10, 7, 7, 8, 8, 7, 10, 7, 9, 11, 10, 8, 9, 8, 10, 9, 8, 8, 8, 9, 8, 9, 8, 10, 10, 8, 13, 8, 8, 9, 8, 8, 8, 10, 9, 8, 8, 10, 11

Offset: 1

Robert Israel, Feb 02 2016

nonn

a(n) = m where A080076(n) = k*2^m + 1, k odd.

			The first Proth prime A080076(1) = 3 = 1*2^1 + 1, so a(1) = 1.
The second Proth prime A080076(2) = 5 = 1*2^2 + 1, so a(2) = 2.

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

Cf. A007814, A080076.

N:= 10^6: # for all Proth primes <= N
Proth:= sort(convert(select(isprime, {seq(seq(k*2^m+1, k = 1 .. min(2^m, (N-1)/2^m), 2), m=1..ilog2(N-1))}),list)):
map(t -> padic:-ordp(t-1,2), Proth);

a(n) = A007814(A080076(n)-1).

A331539 a(n) gives the number of primes of form (2n+1)2^m + 1 where m satisfies 2^m <= 2*n+1.

Original entry on oeis.org

1, 1, 1, 1, 3, 2, 1, 2, 1, 0, 2, 1, 2, 2, 2, 0, 1, 2, 2, 4, 1, 1, 1, 0, 1, 2, 2, 1, 2, 1, 1, 3, 3, 2, 2, 2, 2, 4, 1, 1, 3, 2, 2, 2, 1, 0, 3, 3, 2, 4, 1, 0, 3, 1, 1, 2, 2, 1, 3, 2, 0, 1, 2, 1, 2, 2, 2, 4, 1, 1, 4, 0, 1, 0, 2, 1, 2, 2, 0, 2, 2, 3, 5, 1, 1, 0, 1

Offset: 0

Jeppe Stig Nielsen, Jan 19 2020

nonn

For each index n, let k = 2*n+1. Then a(n) gives the number of primes of form k*2^m + 1 that are NOT considered Proth primes (A080076) because their m are too small.

In the edge case n=0, so k=1, we count 1*2^0 + 1 = 2 as a non-Proth prime.

			For n=10, we consider 21*2^m + 1, where m runs from 0 to 4 (the next value m=5 would make 2^m exceed 21). The number of cases where 21*2^m + 1 is prime, is 2, namely m=1 (prime 43) and m=4 (prime 337). So 2 primes means a(10)=2. Compare with the start of A032360, all k=21 primes.

Cf. A080076, A134876.

a[n_] := Sum[Boole @ PrimeQ[(2n+1)*2^m + 1], {m, 0, Log2[2n+1]}]; Array[a, 100, 0] (* Amiram Eldar, Jan 20 2020 *)

a(n) = my(k=2*n+1);sum(m=0,logint(k,2),ispseudoprime(k<

A338931 Least b such that b^(2^n) + 1 is an odd Pierpont prime (A005109).

Original entry on oeis.org

2, 2, 2, 2, 2, 54, 162, 8310407949893763072, 46438023168, 65229815808, 396718580736, 629856, 152461794335880672662217818112

Offset: 0

Jeppe Stig Nielsen, Nov 16 2020

Every term is even (A005843) and 3-smooth (A003586).
For n = 0, 1, 2, 3, 4, 7, 8, 9, 12, ..., the corresponding number b^(2^n) + 1 is also a Proth prime (A080076), while for n = 5, 6, 10, 11, ..., it is a non-Proth.
The form b^(2^n) + 1 is called a generalized Fermat number.

			a(7) corresponds to prime 8310407949893763072^128 + 1 = (2^47*3^10)^128 + 1.

Cf. A005109, A056993, A334053.

cp's OEIS Frontend

A046808 a(n) is the least integer greater than a(n-1) such that a(n-1)*2^a(n) + 1 is prime, a(1) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A083391 n-th Payam number E_{-}(n), defined as the smallest positive odd integer k such that for every positive integer n, the number k*2^n-1 is not divisible by any primes p such that the multiplicative order of 2 mod p is less than or equal to e.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A083556 n-th Payam number E_{+}(n), defined as the smallest positive odd integer k such that for every positive integer n, the number k*2^n+1 is not divisible by any primes p such that the multiplicative order of 2 mod p is less than or equal to e.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A214120 Number of Proth primes < 2^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A239234 Number of Proth primes < 10^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A268353 a(n) is the exponent of 2 corresponding to the n-th Proth prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A331539 a(n) gives the number of primes of form (2*n+1)*2^m + 1 where m satisfies 2^m <= 2*n+1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

A338931 Least b such that b^(2^n) + 1 is an odd Pierpont prime (A005109).

Views

Author

Keywords

Comments

Examples

Crossrefs

A331539 a(n) gives the number of primes of form (2n+1)2^m + 1 where m satisfies 2^m <= 2*n+1.