A134876 -id:A134876 - cp's OEIS frontend

A080076 Proth primes: primes of the form k*2^m + 1 with odd k < 2^m, m >= 1.

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857, 10369, 10753, 11393, 11777, 12161, 12289, 13313

Offset: 1

Eric W. Weisstein, Jan 24 2003

nonn

Named after the French farmer and self-taught mathematician François Proth (1852-1879). - Amiram Eldar, Jun 05 2021

T. D. Noe, Table of n, a(n) for n = 1..10000
Chris K. Caldwell's The Top Twenty, Proth.
Bertalan Borsos, Attila Kovács and Norbert Tihanyi, Tight upper and lower bounds for the reciprocal sum of Proth primes, The Ramanujan Journal (2022).
James Grime and Brady Haran, 78557 and Proth Primes, Numberphile video, 2017.
Ernest G. Hibbs, Component Interactions of the Prime Numbers, Ph. D. Thesis, Capitol Technology Univ. (2022), see p. 33.
Youngik Lee, Hyperbolic Primality Test and Catalan-Mersenne Number Conjecture, Brown Univ., Preprints.org (2024). See p. 6.
Max Lewis and Victor Scharaschkin, k-Lehmer and k-Carmichael Numbers, Integers, Vol. 16 (2016), #A80.
Rogério Paludo and Leonel Sousa, Number Theoretic Transform Architecture suitable to Lattice-based Fully-Homomorphic Encryption, 2021 IEEE 32nd Int'l Conf. Appl.-specific Sys., Architectures and Processors (ASAP) 163-170.
François Proth, Théorèmes sur les nombres premiers, Comptes rendus de l'Académie des Sciences de Paris, Vol. 87 (1878), p. 926.
Mario Raso, Integer Sequences in Cryptography: A New Generalized Family and its Application, Ph. D. Thesis, Sapienza University of Rome (Italy 2025). See p. 66.
Hermann Stamm-Wilbrandt, a080076.json, sorted array of all 122,742 Proth primes less than 2^40 (> 10^12).
Tsz-Wo Sze, Deterministic Primality Proving on Proth Numbers, arXiv:0812.2596 [math.NT], 2009.
Eric Weisstein's World of Mathematics, Proth Prime.
Wikipedia, Proth prime.

Cf. A080075.
Cf. A134876 (number of Proth primes), A214120, A239234.
Cf. A248972.

N:= 20000: # to get all terms <= N
S:= select(isprime, {seq(seq(k*2^m+1, k = 1 .. min(2^m, (N-1)/2^m), 2), m=1..ilog2(N-1))}):
sort(convert(S,list)); # Robert Israel, Feb 02 2016

r[p_, n_] := Reduce[p == (2*m + 1)*2^n + 1 && 2^n > 2*m + 1 && n > 0 && m >= 0, {a, m}, Integers]; r[p_] := Catch[ Do[ If[ r[p, n] =!= False, Throw[True]], {n, 1, Floor[Log[2, p]]}]]; A080076 = Reap[ Do[ p = Prime[k]; If[ r[p] === True, Sow[p]], {k, 1, 2000}]][[2, 1]] (* Jean-François Alcover, Apr 06 2012 *)
nn = 13; Union[Flatten[Table[Select[1 + 2^n Range[1, 2^Min[n, nn - n + 1], 2], # < 2^(nn + 1) && PrimeQ[#] &], {n, nn}]]] (* T. D. Noe, Apr 06 2012 *)

is_A080076(N)=isproth(N)&&isprime(N) \\ see A080075 for isproth(). - M. F. Hasler, Oct 18 2014
next_A080076(N)={until(isprime(N=next_A080075(N)),);N}
A080076_first(N)=vector(N,i,N=if(i>1,next_A080076(N),3)) \\ M. F. Hasler, Jul 07 2022, following a suggestion from Bill McEachen

Conjecture: a(n) ~ (n log n)^2 / 2. - Thomas Ordowski, Oct 19 2014

Sum_{n>=1} 1/a(n) is in the interval (0.7473924793, 0.7473924795) (Borsos et al., 2022). - Amiram Eldar, Jan 29 2022

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<

cp's OEIS Frontend

A080076 Proth primes: primes of the form k*2^m + 1 with odd k < 2^m, m >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

A331540 Number of primes of the form k*2^n + 1 with k < 2^n.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

cp's OEIS Frontend

A080076 Proth primes: primes of the form k*2^m + 1 with odd k < 2^m, m >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

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

A331540 Number of primes of the form k*2^n + 1 with k < 2^n.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

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