OFFSET
1,1
COMMENTS
If q is odd, then a(n) is the number of solutions to x^2 + y^2 = t in the finite field F_q for any t != 0.
Proof: We first show that if x^2 + y^2 = t has a solution for t != 0, then the number of solutions is q - Kronecker(-4,q). Let (x_0,y_0) be a solution, then the other points on the circle x^2 + y^2 = t are parametrized by the lines through (x_0,y_0) with slope in F_q U {oo}. The line with slope k has an intersection with the circle other than (x_0,y_0) if and only if 1 + k^2 != 0 (in which case the intersection is the point at infinity) and k != -x_0/y_0 (in which case the line is tangent to the circle), so we have (q+1)-3 more solutions if q == 1 (mod 4) and (q+1)-1 more solutions if q == 3 (mod 4). By a simple counting argument we can see that x^2 + y^2 = t has a solution for all t != 0.
LINKS
Jianing Song, Table of n, a(n) for n = 1..10000
EXAMPLE
For q = A246655(4) = 5, we see that in F_5:
- x^2 + y^2 = 1 has 4 solutions (0,+-1), (+-1,0);
- x^2 + y^2 = 2 has 4 solutions (+-1,+-1);
- x^2 + y^2 = -2 has 4 solutions (+-2,+-2);
- x^2 + y^2 = -1 has 4 solutions (+-2,0), (0,+-2),
so a(4) = 4.
For q = A246655(5) = 7, we see that in F_7:
- x^2 + y^2 = 1 has 8 solutions (0,+-1), (+-1,0), (+-2,+-2);
- x^2 + y^2 = 2 has 8 solutions (0,+-3), (+-3,0), (+-1,+-1);
- x^2 + y^2 = 3 has 8 solutions (+-1,+-3), (+-3,+-1);
- x^2 + y^2 = -3 has 8 solutions (+-2,0), (0,+-2), (+-3,+-3);
- x^2 + y^2 = -2 has 8 solutions (+-1,+-2), (+-2,+-1);
- x^2 + y^2 = -1 has 8 solutions (+-2,+-3), (+-3,+-2),
so a(5) = 8.
For q = A246655(7) = 9, we see that in F_9 = F_3(i):
- x^2 + y^2 = 1 has 8 solutions (0,+-1), (+-1,0), (+-i,+-i);
- x^2 + y^2 = -1 has 8 solutions (0,+-i), (+-i,0), (+-1,+-1);
- x^2 + y^2 = 1+i has 8 solutions (+-1,+-(1-i)), (+-(1-i),+-1);
- x^2 + y^2 = i has 8 solutions (0,+-(1-i)), (+-(1-i),0), (+-(1+i),+-(1+i));
- x^2 + y^2 = -1+i has 8 solutions (+-i,+-(1-i)), (+-(1-i),+-i);
- x^2 + y^2 = 1-i has 8 solutions (+-1,+-(1+i)), (+-(1+i),+-1);
- x^2 + y^2 = -i has 8 solutions (0,+-(1+i)), (+-(1+i),0), (+-(1-i),+-(1-i));
- x^2 + y^2 = -1-i has 8 solutions (+-i,+-(1+i)), (+-(1+i),+-i),
so a(7) = 8.
PROG
(PARI) lim_A367013(N) = for(n=2, N, if(isprimepower(n), print1(n - kronecker(-4, n), ", ")))
CROSSREFS
KEYWORD
nonn
AUTHOR
Jianing Song, Nov 01 2023
STATUS
approved