A053443 x^2 + y^2 does not take on all possible values mod n.

4, 8, 9, 12, 16, 18, 20, 24, 27, 28, 32, 36, 40, 44, 45, 48, 49, 52, 54, 56, 60, 63, 64, 68, 72, 76, 80, 81, 84, 88, 90, 92, 96, 98, 99, 100, 104, 108, 112, 116, 117, 120, 121, 124, 126, 128, 132, 135, 136, 140, 144, 147, 148, 152, 153, 156, 160, 162, 164, 168, 171

Offset

1,1

Comments

Sequence gives values of n such there is not always a solution 1 < z < n to x^2 + y^2 = z (mod n). - Benoit Cloitre, Jan 04 2002; corrected by Carmine Suriano, Jun 19 2013

The asymptotic density of this sequence is 1- 3/(8*K^2) = 1 - (3/4) * A243379 = 0.35791..., where K is the Landau-Ramanujan constant (A064533). - Amiram Eldar, Dec 19 2020

Links

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Formula

n divisible by p^2 where p = 2 or prime p == 3 (mod 4).

Mathematica

Select[Range[200], AnyTrue[FactorInteger[#], Mod[First[#1], 4] > 1 && Last[#1] > 1 &] &] (* Amiram Eldar, Dec 19 2020 *)

Prog

(PARI) is(n)=my(v=vectorsmall(n, i, 1)); for(x=0, n\2, for(y=0, x, v[(x^2+y^2)%n+1]=0)); vecmax(v) \\ Charles R Greathouse IV, Jun 19 2013
(PARI) is(n)=forprime(p=2, 97, my(o=valuation(n, p)); if(o, if(o>1&&p%4>1, return(1)); n/=p^o)); my(f=factor(n)); for(i=1, #f[, 1], if(f[i, 2]>1&&f[i, 1]%4>1, return(1))); 0 \\ Charles R Greathouse IV, Jun 19 2013

Crossrefs

Complement of A240370.

Cf. A053444, A064533, A243379.

Sequence in context: A359468 A034043 A278517 * A360070 A048098 A322109

Adjacent sequences: A053440 A053441 A053442 * A053444 A053445 A053446

Keyword

nonn

Author

David W. Wilson

Status

approved