|
%I #94 Mar 23 2024 08:24:41
%S 3,5,13,17,41,97,113,193,241,257,353,449,577,641,673,769,929,1153,
%T 1217,1409,1601,2113,2689,2753,3137,3329,3457,4481,4993,6529,7297,
%U 7681,7937,9473,9601,9857,10369,10753,11393,11777,12161,12289,13313
%N Proth primes: primes of the form k*2^m + 1 with odd k < 2^m, m >= 1.
%C Named after the French farmer and self-taught mathematician François Proth (1852-1879). - _Amiram Eldar_, Jun 05 2021
%H T. D. Noe, <a href="/A080076/b080076.txt">Table of n, a(n) for n = 1..10000</a>
%H Chris K. Caldwell's The Top Twenty, <a href="https://t5k.org/top20/page.php?id=66">Proth</a>.
%H 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 James Grime and Brady Haran, <a href="https://www.youtube.com/watch?v=fcVjitaM3LY">78557 and Proth Primes</a>, Numberphile video, 2017.
%H 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 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 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 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ProthPrime.html">Proth Prime</a>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Proth_prime">Proth prime</a>.
%F Conjecture: a(n) ~ (n log n)^2 / 2. - _Thomas Ordowski_, Oct 19 2014
%F Sum_{n>=1} 1/a(n) is in the interval (0.7473924793, 0.7473924795) (Borsos et al., 2022). - _Amiram Eldar_, Jan 29 2022
%p N:= 20000: # to get all terms <= N
%p 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 sort(convert(S,list)); # _Robert Israel_, Feb 02 2016
%t 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 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 (PARI) is_A080076(N)=isproth(N)&&isprime(N) \\ see A080075 for isproth(). - _M. F. Hasler_, Oct 18 2014
%o next_A080076(N)={until(isprime(N=next_A080075(N)),);N}
%o 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 Cf. A080075.
%Y Cf. A134876 (number of Proth primes), A214120, A239234.
%Y Cf. A248972.
%K nonn
%O 1,1
%A _Eric W. Weisstein_, Jan 24 2003
|
