login
Elite primes: a prime number p is called elite if only a finite number of Fermat numbers 2^(2^n)+1 are quadratic residues mod p.
9

%I #54 May 15 2024 22:30:30

%S 3,5,7,41,15361,23041,26881,61441,87041,163841,544001,604801,6684673,

%T 14172161,159318017,446960641,1151139841,3208642561,38126223361,

%U 108905103361,171727482881,318093312001,443069456129,912680550401,1295536619521,1825696645121,2061584302081

%N Elite primes: a prime number p is called elite if only a finite number of Fermat numbers 2^(2^n)+1 are quadratic residues mod p.

%C Křížek, Luca, Shparlinski, & Somer show that a(n) >> n log^2 n. - _Charles R Greathouse IV_, Jan 25 2017

%C Let d = 2^r*d' be the multiplicative order of 2 modulo p. Note that 2^2^s == 2^d == 1 (mod p), so p divides none of.

%H Dennis Martin, <a href="/A102742/b102742.txt">Table of n, a(n) for n = 1..29</a>

%H Alexander Aigner, <a href="https://doi.org/10.1007/BF01298923">Über Primzahlen, nach denen (fast) alle Fermatzahlen quadratische Nichtreste sind</a>, Monatsh. Math., Vol. 101 (1986), pp. 85-93; <a href="https://eudml.org/doc/178266">alternative link</a>.

%H Alain Chaumont and Tom Mueller, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Mueller/mueller12.html">All Elite Primes Up to 250 Billion</a>, J. Integer Sequences, Vol. 9 (2006), Article 06.3.8.

%H Matthew Just, <a href="https://arxiv.org/abs/2102.00906">On upper bounds for the count of elite primes</a>, arXiv:2102.00906 [math.NT], 2021.

%H Michal Křížek, Florian Luca, Igor E. Shparlinski, and Lawrence Somer, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL14/Krizek/krizek2.html">On the complexity of testing elite primes</a>, Journal of Integer Sequences, Vol. 14 (2011), Article 11.1.2, 5 pp.

%H Xiaoquin Li, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Li/li28r3.html">Verifying Two Conjectures on Generalized Elite Primes</a>, JIS 12 (2009) 09.4.7.

%H Dennis Martin, <a href="http://www.primenace.com/papers/math/ElitePrimes.htm">Elite Prime Search</a>. [Broken link]

%H Dennis Martin, <a href="/A102742/a102742.html">Elite Prime Search</a>. [Cached copy, with permission of author]

%H Dennis Martin, <a href="/A102742/a102742_1.html">Elite and Anti-Elite Prime Search Methodology</a> [Cached copy, with permission of author]

%H Tom Müller, <a href="http://projecteuclid.org/euclid.em/1175789738">Searching for large elite primes</a>, Experimental Mathematics, Vol. 15, Nol. 2 (2006), pp. 183-186.

%H Tom Muller and A. Reinhart, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Mueller/mueller445.html"> On generalized Elite Primes</a>, Journal of Integer Sequences, Vol. 11 (2008), Article 08.3.1.

%H Tom Müller, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Mueller/mueller6.html">On the Fermat Periods of Natural Numbers</a>, Journal of Integer Sequences, Vol. 13 (2010), Article 10.9.5.

%H Tom Müller, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Mueller/mueller10.html">On the Exponents of Non-Trivial Divisors of Odd Numbers and a Generalization of Proth's Primality Theorem</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.2.7.

%F Sum_{n>=1} 1/a(n) = A344785. - _Amiram Eldar_, May 30 2021

%o (PARI) list_upto(N)={forprime(p=3,N,r=2^valuation(p-1,2); a=Mod(3,p); v=List(); k=0; while(1,listput(v,a); a=(a-1)^2+1; for(j=1,#v,if(v[j]==a,k=j;break(2)))); for(i=k,#v,znorder(v[i]) % r != 0 && next(2)); print1(p,", "))} \\ Slow, only for illustration, _Jeppe Stig Nielsen_, Jan 28 2020

%o (PARI) isElite(n) = if(isprime(n) && n > 2, my(d = znorder(Mod(2,n)), StartPoint = valuation(d,2), LengthTest = znorder(Mod(2, d >> StartPoint))); for(i = StartPoint, StartPoint + LengthTest - 1, if(issquare(Mod(2,n)^2^i + 1), return(0))); 1, 0) \\ _Jianing Song_, May 15 2024

%Y Cf. A128852, A344785. Subsequence of A129802.

%K nonn

%O 1,1

%A _Tom Mueller_, Feb 08 2005; extended Jun 16 2005

%E a(17) from _Tom Mueller_, Jul 20 2005

%E a(18)-a(21) from _Tom Mueller_, Apr 18 2006

%E 6 further terms from _Tom Mueller_, Apr 16 2007