OFFSET
1,2
LINKS
Jianing Song, Table of n, a(n) for n = 1..5050 (first 100 rows)
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.
EXAMPLE
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
PROG
(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)]
(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
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Jack Zhang, May 27 2018
EXTENSIONS
Offset corrected by Jianing Song, Apr 20 2019
STATUS
approved