OFFSET
1,1
COMMENTS
The number of solutions to x*y = z*w in F_q is Sum_{t in F_q} (number of solutions to x*y = t)^2. The number of solutions to x*y = 0 is 2*q-1, and the number of solutions to x*y = t for t != 0 is q-1, the number of units in F_q. So the total number is (2*q-1)^2 + (q-1)^2*(q-1) = q^3 + q^2 - q.
If q is odd, then a(n) is also the number of solutions to x^2 + y^2 = z^2 + w^2 in the finite field F_q.
Proof 1: the number is Sum_{t in F_q} (number of solutions to x^2 - z^2 = t)^2. For odd q, there is a one-to-one correspondence between the solutions to x*y = t and the solutions to x^2 - y^2 = t.
Proof 2: the number is Sum_{t in F_q} (number of solutions to x^2 + y^2 = t)^2. The number of solutions to x^2 + y^2 = 0 is 2*q-1 if q == 1 (mod 4) and 1 if q == 3 (mod 4), and the number of solutions to x^2 + y^2 = t for t != 0 is q-1 if q == 1 (mod 4) and q+1 if q == 3 (mod 4) (see A367013). So the total number is (2*q-1)^2 + (q-1)^2*(q-1) = q^3 + q^2 - q for q == 1 (mod 4) and 1^2 + (q+1)^2*(q-1) = q^3 + q^2 - q for q == 3 (mod 4).
LINKS
Jianing Song, Table of n, a(n) for n = 1..10000
EXAMPLE
For q = A246655(3) = 4, we see that in F_4 = F_2(t), where t^2 + t + 1 = 0:
- x*y = z*w = 0 has 7 solutions for the pair (x,y) and 7 solutions for the pair (z,w);
- x*y = z*w = 1 has 3 solutions for the pair (x,y) and 3 solutions for the pair (z,w);
- x*y = z*w = t has 3 solutions for the pair (x,y) and 3 solutions for the pair (z,w);
- x*y = z*w = 1+t has 3 solutions for the pair (x,y) and 3 solutions for the pair (z,w),
so a(4) = 7*7 + 3*3*3 = 76.
MATHEMATICA
Map[#^3+#^2-#&, Select[Range[200], PrimePowerQ]] (* Paolo Xausa, Nov 26 2023 *)
PROG
(PARI) lim_A367014(N) = for(n=2, N, if(isprimepower(n), print1(n^3 + n^2 - n, ", ")))
CROSSREFS
KEYWORD
nonn
AUTHOR
Jianing Song, Nov 01 2023
STATUS
approved