Elite and Anti-Elite Prime Search Methodology

Dennis R. Martin

DP Technology Corp.,

dennis.martin@dptechnology.com

A prime number *p* is **elite** if only finitely many Fermat numbers *F _{m}* = 2^(2

Instead of checking whether a
certain congruence is solvable or not for each Fermat residue within the Fermat
period *L* (as given by expression (4)
in reference [1] or expression (22) in reference [2]), however, the Jacobi symbols of the Fermat residues are
utilized. The algorithm for computing the Jacobi symbol was taken from

An important result from Aigner [4] is that for any prime number written in the form *p* = 2* ^{S}h*
+ 1 with

Those results combine to lead to
the following algorithm to check the eliteness or anti-eliteness of a candidate
prime *p*:

- Compute the residue of
*p*mod 240. If (*p*mod 240) is a member of {23, 47, 143, 167}, then*p*can be neither elite nor anti-elite, so exit and go on to the next candidate. - Determine the latest possible Fermat period start
*S*. - Inside of a For/Next loop from 0 to
*S*, compute the Fermat residues modulo*p*up to*F*and save those residues in an array. If a period is completed (if a residue repeats) prior to_{S}*F*being reached, then flag that condition and exit the loop._{S} - Calculate the Jacobi symbol of the last residue
*r*, which will either correspond to*F*(if the loop in step 3 was completed to_{S}*S*) or will correspond to the term at the end of a period,*F*where_{e }*e*=*s*+*L*– 1 (if the loop in step 3 was exited early). - If the Jacobi symbol in step 4 is -1, then
*r*is a quadratic non-residue, which means*p*could not be anti-elite. So check if the (*p*mod 240) value from step 1 is a member of {11, 13, 19, 23, 31, 47, 59, 61, 71, 79, 91, 109, 119, 131, 133, 139, 143, 151, 167, 179, 181, 191, 199, 211, 229, 239}, because then*p*cannot be elite either, so exit and go on to the next candidate. - If the Jacobi symbol in step 4 is 1, then
*r*is a quadratic residue, which means*p*could not be elite. So check if the (*p*mod 240) value from step 1 is a member of {7, 23, 43, 47, 67, 83, 103, 107, 127, 143, 163, 167, 187, 203, 223, 227}, because then*p*cannot be anti-elite either, so exit and go on to the next candidate. - If the loop in step 3 was not exited early (i.e. a
Fermat period has not yet been completed) then setup a Do/Until Loop to
loop until a period does complete (i.e. until we find a residue
*r*_{e+}_{1}=*r*that is already a member of the array saved in step 3). For each residue inside this loop calculate its Jacobi symbol. If the Jacobi symbol of any Fermat residue does not match the Jacobi symbol corresponding to_{s}*F*from step 4, then_{S}*p*can be neither elite nor anti-elite, so exit and go on to the next candidate. - Find the index of the first repeating residue
*r*inside the array from step 3 and setup another For/Next loop to go from that index to the end of the array. For each residue inside this loop calculate its Jacobi symbol. Once again if the Jacobi symbol of any Fermat residue does not match the Jacobi symbol corresponding to_{s}*F*from step 4, then_{e}*p*can be neither elite nor anti-elite, so exit and go on to the next candidate. - If the Jacobi symbols from the loops in steps 7 and 8
are all identical, then
*p*is elite if those Jacobi symbols are -1 and*p*is anti-elite if they are all +1. The Fermat period*L*is the number of Fermat residues looped through in steps 7 and 8 combined.

The results of this currently ongoing search are given on the Elite Prime Search and Anti-Elite Prime Search pages [8, 9]. As of February 12, 2009, this search is complete up to 1E14. There are 29 elite primes less than 1E14 and 113 anti-elite primes less than 1E14.

The elite and anti-elite primes appear as sequences A102742 and A128852 in Sloane’s Online Encyclopedia of Integer Sequences (OEIS) [6].

References

[1] Alain Chaumont and Tom Mueller, All Elite Primes Up to 250 Billion, J. Integer Sequences, Vol. 9 (2006), Article 06.3.8.

[2] Tom Mueller, On Anti-Elite Prime Numbers, J. Integer Sequences, Vol. 10 (2007), Article 07.9.4.

[3] Chris Caldwell, The Prime Pages: Jacobi symbol.

[4] Alexander Aigner; Üeber Primzahlen, nach denen (fast) alle Fermatzahlen quadratische Nichtreste sind. Monatsh. Math. 101 (1986), pp. 85-93.

[5] Wilfrid Keller, Fermat factoring status.

[6] N. J. A. Sloane, Online Encyclopedia of Integer Sequences (OEIS), electronically published at: https://oeis.org/.

[7] M. Kķ˛ek, F. Luca, L. Somer, On the convergence of series of reciprocals of primes related to the Fermat numbers. J. Number Theory 97 (2002), 95–112.

[8] Dennis R. Martin, Elite Prime Search.

[9] Dennis R. Martin, Anti-Elite Prime Search.

Copyright © 2008-2009 by Dennis R. Martin, ALL RIGHTS RESERVED.

No part of this document may be reproduced, retransmitted, or redistributed by any means, without providing a proper reference crediting Dennis R. Martin.