A199854 Primes of the form 1 + m^2 + n^2 with gcd(m,n)=1.

3, 11, 59, 83, 107, 131, 179, 227, 251, 347, 443, 467, 563, 587, 971, 1019, 1091, 1187, 1259, 1283, 1307, 1451, 1523, 1571, 1619, 1811, 1907, 1931, 2027, 2099, 2411, 2459, 2579, 2819, 2939, 2963, 3203, 3251, 3299, 3371, 3467, 3491, 3539, 3779, 3803, 3923, 3947

Offset: 1

Author

Michel Marcus, Dec 22 2012

Keywords

• nonn

Examples

			First such decompositions are 3 = 1 + 1^2 + 1^2, 11 = 1 + 1^2 + 3^2, 59 = 1 + 3^2 + 7^2.
First instance of several decompositions for the same prime: 131 = 1 + 3^2 + 11^2 = 1 + 7^2 + 9^2.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• Mario Raso, Integer Sequences in Cryptography: A New Generalized Family and its Application, Ph. D. Thesis, Sapienza University of Rome (Italy 2025). See p. 112.
• J. Wu, Primes of the form 1 + m^2 + n^2 in short intervals, Proc. Amer. Math. Soc. 126 (1998), 1-8.

Crossrefs

Cf. A056899 (when the decomposition has m=1).

Programs

Maple

filter:= proc(n) local S,x,y;
 if not isprime(n) then return false fi;
 S:= map(t -> subs(t,[x,y]),[isolve](x^2 + y^2 = n-1));
 ormap(t -> t[1] > 0 and t[2] >= t[1] and igcd(t[1],t[2])=1, S)
end proc:
select(filter, [seq(i,i=3..5000,2)]); # Robert Israel, Sep 30 2024

PARI

hasform(p) = {q = p - 1; for (k = 1, q/2, if (issquare(k) && issquare(q-k) && (gcd(k, q-k)==1), return(1));); return(0);}