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

Author

David W. Wilson

Keywords

• nonn

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

Crossrefs

Complement of A240370.

Cf. A053444, A064533, A243379.

Programs

Mathematica

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

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

Formula

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