cp's OEIS Frontend

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

%I A080076 #104 Jun 15 2025 23:16:37
%S A080076 3,5,13,17,41,97,113,193,241,257,353,449,577,641,673,769,929,1153,
%T A080076 1217,1409,1601,2113,2689,2753,3137,3329,3457,4481,4993,6529,7297,
%U A080076 7681,7937,9473,9601,9857,10369,10753,11393,11777,12161,12289,13313
%N A080076 Proth primes: primes of the form k*2^m + 1 with odd k < 2^m, m >= 1.
%C A080076 Named after the French farmer and self-taught mathematician François Proth (1852-1879). - _Amiram Eldar_, Jun 05 2021
%H A080076 T. D. Noe, <a href="/A080076/b080076.txt">Table of n, a(n) for n = 1..10000</a>
%H A080076 Chris K. Caldwell's The Top Twenty, <a href="https://t5k.org/top20/page.php?id=66">Proth</a>.
%H A080076 Bertalan Borsos, Attila Kovács and Norbert Tihanyi, <a href="https://doi.org/10.1007/s11139-021-00536-2">Tight upper and lower bounds for the reciprocal sum of Proth primes</a>, The Ramanujan Journal (2022).
%H A080076 James Grime and Brady Haran, <a href="https://www.youtube.com/watch?v=fcVjitaM3LY">78557 and Proth Primes</a>, Numberphile video, 2017.
%H A080076 Ernest G. Hibbs, <a href="https://www.proquest.com/openview/4012f0286b785cd732c78eb0fc6fce80">Component Interactions of the Prime Numbers</a>, Ph. D. Thesis, Capitol Technology Univ. (2022), see p. 33.
%H A080076 Youngik Lee, <a href="https://doi.org/10.20944/preprints202405.0952.v1">Hyperbolic Primality Test and Catalan-Mersenne Number Conjecture</a>, Brown Univ., Preprints.org (2024). See p. 6.
%H A080076 Max Lewis and Victor Scharaschkin, <a href="https://www.emis.de/journals/INTEGERS/papers/q80/q80.Abstract.html">k-Lehmer and k-Carmichael Numbers</a>, Integers, Vol. 16 (2016), #A80.
%H A080076 Rogério Paludo and Leonel Sousa, <a href="https://doi.org/10.1109/ASAP52443.2021.00031">Number Theoretic Transform Architecture suitable to Lattice-based Fully-Homomorphic Encryption</a>, 2021 IEEE 32nd Int'l Conf. Appl.-specific Sys., Architectures and Processors (ASAP) 163-170.
%H A080076 François Proth, <a href="https://fr.wikisource.org/wiki/Page:Comptes_rendus_hebdomadaires_des_s%C3%A9ances_de_l%E2%80%99Acad%C3%A9mie_des_sciences,_tome_087,_1878.djvu/932">Théorèmes sur les nombres premiers</a>, Comptes rendus de l'Académie des Sciences de Paris, Vol. 87 (1878), p. 926.
%H A080076 Mario Raso, <a href="https://iris.uniroma1.it/handle/11573/1732819">Integer Sequences in Cryptography: A New Generalized Family and its Application</a>, Ph. D. Thesis, Sapienza University of Rome (Italy 2025). See p. 66.
%H A080076 Hermann Stamm-Wilbrandt, <a href="/A080076/a080076.json.txt">a080076.json</a>, sorted array of all 122,742 Proth primes less than 2^40 (> 10^12).
%H A080076 Tsz-Wo Sze, <a href="https://arxiv.org/abs/0812.2596">Deterministic Primality Proving on Proth Numbers</a>, arXiv:0812.2596 [math.NT], 2009.
%H A080076 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ProthPrime.html">Proth Prime</a>.
%H A080076 Wikipedia, <a href="https://en.wikipedia.org/wiki/Proth_prime">Proth prime</a>.
%F A080076 Conjecture: a(n) ~ (n log n)^2 / 2. - _Thomas Ordowski_, Oct 19 2014
%F A080076 Sum_{n>=1} 1/a(n) is in the interval (0.7473924793, 0.7473924795) (Borsos et al., 2022). - _Amiram Eldar_, Jan 29 2022
%p A080076 N:= 20000: # to get all terms <= N
%p A080076 S:= select(isprime, {seq(seq(k*2^m+1, k = 1 .. min(2^m, (N-1)/2^m), 2), m=1..ilog2(N-1))}):
%p A080076 sort(convert(S,list)); # _Robert Israel_, Feb 02 2016
%t A080076 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 *)
%t A080076 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 *)
%o A080076 (PARI) is_A080076(N)=isproth(N)&&isprime(N) \\ see A080075 for isproth(). - _M. F. Hasler_, Oct 18 2014
%o A080076 next_A080076(N)={until(isprime(N=next_A080075(N)),);N}
%o A080076 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_
%Y A080076 Cf. A080075.
%Y A080076 Cf. A134876 (number of Proth primes), A214120, A239234.
%Y A080076 Cf. A248972.
%K A080076 nonn
%O A080076 1,1
%A A080076 _Eric W. Weisstein_, Jan 24 2003