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

Author

Eric W. Weisstein, Jan 24 2003

Keywords

• nonn

Comments

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

Links

• 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.

Crossrefs

Cf. A080075.

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

Cf. A248972.

Programs

Maple

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

Mathematica

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

PARI

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

Formula

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