A102295 Odd primes which set records for smallest absolute value of a quadratic nonresidue.

3, 5, 17, 73, 241, 1009, 2689, 8089, 33049, 53881, 87481, 483289, 515761, 1083289, 3818929, 9257329, 22000801, 48473881, 175244281, 427733329, 898716289, 8114538721, 9176747449, 23616331489

Offset: 1

Author

David L. Harden, Feb 19 2005

Keywords

• nonn

Comments

It is strange that each term of this sequence has, among its quadratic residues, only one more of -1,2,3,5,7,11... and thus gets into the sequence by 'doing the bare minimum' and not having the next term of that sequence as a quadratic residue also. For example, the quadratic residues modulo 73 include -1, 2 and 3 but not 5. With 241, 5 is a quadratic residue but 7 is not. With 1009, 7 is but 11 is not. This should stop at some point, but my computations haven't reached there yet (they have not been assisted electronically).

If someone wants to code up a program to compute members of this sequence quickly, one should strike a balance (if not using a totally different or much smarter approach) between using the sieve you can get by using the law of quadratic reciprocity (and the (-1/p) and (2/p) theorems) and using brute force to find primes with the right quadratic residues by chance.

For example, there are 2*3*5*6*8*9*11*14=1995840 residue classes modulo 8*3*5*7*11*13*17*19*23*29 containing odd primes with -1 and the primes up to 29 as quadratic residues. Simply enumerating these is significant work for a computer.

On the other hand, generating a smaller list of residue classes (for example, the 12960 residue classes modulo 8*3*5*7*11*13*17*19 which contain odd primes having -1 and the primes up to 19 as quadratic residues) and then leaving to chance (and brute force) the primality of p and that (23/p)=(29/p)=1 should be a more intelligent way to search for the smallest odd prime having -1 and the primes up to 29 as quadratic residues than using a complete sieve as described earlier. I am labeling this sequence as "hard" because extending it should become hard (exponentially hard, since each term should take roughly twice as much computation as the previous one) once the terms get to something around 20 digits.

I have now written a computer program to help me find members of this sequence. Among these, the term 3818929 is interesting because it is the first break in a pattern established by the previous terms, wherein the smallest prime p such that -1 and the primes up to the k-th prime are quadratic residues modulo p has the (k+1)st prime as a quadratic nonresidue. 3818929 is the smallest p to have -1 and the primes <= 41 as quadratic residues but it also has 43 (but not 47) as a quadratic residue. - David L. Harden, May 21 2005

This is A002224 with duplicates removed and 3 and 5 tacked on to the beginning. The remark about term 3818929 follows from the fact that it is the first duplicate in A002224.

Examples

			3 is the smallest odd prime. The smallest absolute value of a quadratic nonresidue modulo 3 is 1, since (-1/3)=-1.
17 is the smallest odd prime to have -1 and 2 as quadratic residues.
2689 is the smallest odd prime to have -1, 2, 3, 5, 7 and 11 as quadratic residues.
		

Extensions

More terms from David L. Harden, May 21 2005

More terms copied from A002224 by Max Alekseyev, May 21 2016