A305191 Table read by rows: T(n,k) is the number of pairs (x,y) mod n such that x^2 + y^2 == k (mod n), for k from 0 to n-1.

1, 2, 2, 1, 4, 4, 4, 8, 4, 0, 9, 4, 4, 4, 4, 2, 8, 8, 2, 8, 8, 1, 8, 8, 8, 8, 8, 8, 8, 16, 16, 0, 8, 16, 0, 0, 9, 12, 12, 0, 12, 12, 0, 12, 12, 18, 8, 8, 8, 8, 18, 8, 8, 8, 8, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 4, 32, 16, 0, 16, 32, 4, 0, 16, 8, 16, 0, 25, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12

Offset: 1

Author

Jack Zhang, May 27 2018

Keywords

• nonn
• tabl

Examples

			Table begins:
  1;
  2,  2;
  1,  4,  4;
  4,  8,  4,  0;
  9,  4,  4,  4,  4;
  2,  8,  8,  2,  8,  8;
  1,  8,  8,  8,  8,  8,  8;
  8, 16, 16,  0,  8, 16,  0,  0;
  9, 12, 12,  0, 12, 12,  0, 12, 12;
E.g., for n = 4:
4 pairs satisfy x^2 + y^2 = 4k: (0, 0), (0, 2), (2, 0), (2, 2)
8 pairs satisfy x^2 + y^2 = 4k+1: (0, 1), (0, 3), (1, 0), (1, 2), (2, 1), (2, 3), (3, 0), (3, 2)
4 pairs satisfy x^2 + y^2 = 4k+2: (1, 1), (1, 3), (3, 1), (3, 3)
0 pairs satisfy x^2 + y^2 = 4k+3
		

Links

• Jianing Song, Table of n, a(n) for n = 1..5050 (first 100 rows)

Crossrefs

Cf. A155918 (number of nonzeros in row n).

Cf. A086933 (1st column), A060968 (2nd column), A086932 (right diagonal).

Programs

PARI

row(n) = {v = vector(n); for (x=0, n-1, for (y=0, n-1, k = (x^2 + y^2) % n; v[k+1]++;);); v;} \\ Michel Marcus, Jun 08 2018

PARI

T(n,k)=
{
    my(r=1, f=factor(n));
    for(j=1, #f[, 1], my(p=f[j, 1], e=f[j, 2], b=valuation(k,p));
        if(p==2, r*=if(b>=e-1, 2^e, if((k/2^b)%4==1, 2^(e+1), 0)));
        if(p%4==1, r*=if(b>=e, ((p-1)*e+p)*p^(e-1), (b+1)*(p-1)*p^(e-1)));
        if(p%4==3, r*=if(b>=e, p^(e-(e%2)), if(b%2, 0, (p+1)*p^(e-1))));
    );
    return(r);
}
tabl(nn) = for(n=1, nn, for(k=0, n-1, print1(T(n, k), ", ")); print()) \\ Jianing Song, Apr 20 2019

Python

[[len([(x, y) for x in range(n) for y in range(n) if (pow(x,2,n)+pow(y,2,n))%n==d]) for d in range(n)] for n in range(1,10)]

Formula

T(n,k) is multiplicative with respect to n, that is, if gcd(n,m)=1 then T(n*m,k) = T(n,k mod n)*T(m,k mod m).

T(n,0) = A086933(n). Let n = p^e and k = r*p^b (0 <= b < e, gcd(r,p) = 1, 0 < k < n). For p == 1 (mod 4), T(n,k) = (b+1)*(p-1)*p^(e-1). For p == 3 (mod 4), T(n,k) = (p+1)*p^(e-1) if b even; 0 if b odd. For p = 2, T(n,k) = 2^e if k = 2^(e-1); 2^(e+1) if b <= e-2 and r == 1 (mod 4); 0 if r == 3 (mod 4). [Corrected by Jianing Song, Apr 20 2019]

If p is an odd prime then T(p,k) = p - (-1)^(p-1)/2 if k > 0, otherwise p + (p-1)*(-1)^(p-1)/2.

Extensions

Offset corrected by Jianing Song, Apr 20 2019