cp's OEIS Frontend

A367014 Let q be the n-th prime power (A246655), then a(n) = q^3 + q^2 - q; number of solutions to x*y = z*w in the finite field F_q.

%I A367014 #19 Jan 19 2025 01:30:09
%S A367014 10,33,76,145,385,568,801,1441,2353,4336,5185,7201,12673,16225,20385,
%T A367014 25201,30721,33760,51985,70561,81313,105985,120001,151633,208801,
%U A367014 230641,266176,305185,362881,394273,499201,537921,578593,712801,921985,1040401,1103233,1236385,1306801
%N A367014 Let q be the n-th prime power (A246655), then a(n) = q^3 + q^2 - q; number of solutions to x*y = z*w in the finite field F_q.
%C A367014 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.
%C A367014 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.
%C A367014 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.
%C A367014 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).
%H A367014 Jianing Song, <a href="/A367014/b367014.txt">Table of n, a(n) for n = 1..10000</a>
%e A367014 For q = A246655(3) = 4, we see that in F_4 = F_2(t), where t^2 + t + 1 = 0:
%e A367014  - x*y = z*w = 0 has 7 solutions for the pair (x,y) and 7 solutions for the pair (z,w);
%e A367014  - x*y = z*w = 1 has 3 solutions for the pair (x,y) and 3 solutions for the pair (z,w);
%e A367014  - x*y = z*w = t has 3 solutions for the pair (x,y) and 3 solutions for the pair (z,w);
%e A367014  - x*y = z*w = 1+t has 3 solutions for the pair (x,y) and 3 solutions for the pair (z,w),
%e A367014 so a(4) = 7*7 + 3*3*3 = 76.
%t A367014 Map[#^3+#^2-#&,Select[Range[200],PrimePowerQ]] (* _Paolo Xausa_, Nov 26 2023 *)
%o A367014 (PARI) lim_A367014(N) = for(n=2, N, if(isprimepower(n), print1(n^3 + n^2 - n, ", ")))
%o A367014 (Python)
%o A367014 from sympy import primepi, integer_nthroot
%o A367014 def A367014(n):
%o A367014     def bisection(f,kmin=0,kmax=1):
%o A367014         while f(kmax) > kmax: kmax <<= 1
%o A367014         while kmax-kmin > 1:
%o A367014             kmid = kmax+kmin>>1
%o A367014             if f(kmid) <= kmid:
%o A367014                 kmax = kmid
%o A367014             else:
%o A367014                 kmin = kmid
%o A367014         return kmax
%o A367014     def f(x): return int(n+x-sum(primepi(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length())))
%o A367014     return (m:=bisection(f,n,n))*(m*(m+1)-1) # _Chai Wah Wu_, Jan 19 2025
%Y A367014 Cf. A246655, A101455 ({kronecker(-4,n)}).
%K A367014 nonn
%O A367014 1,1
%A A367014 _Jianing Song_, Nov 01 2023