A367014 - OEIS

%I #19 Jan 19 2025 01:30:09

%S 10,33,76,145,385,568,801,1441,2353,4336,5185,7201,12673,16225,20385,

%T 25201,30721,33760,51985,70561,81313,105985,120001,151633,208801,

%U 230641,266176,305185,362881,394273,499201,537921,578593,712801,921985,1040401,1103233,1236385,1306801

%N 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 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 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 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 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 Jianing Song, <a href="/A367014/b367014.txt">Table of n, a(n) for n = 1..10000</a>

%e For q = A246655(3) = 4, we see that in F_4 = F_2(t), where t^2 + t + 1 = 0:

%e  - x*y = z*w = 0 has 7 solutions for the pair (x,y) and 7 solutions for the pair (z,w);

%e  - x*y = z*w = 1 has 3 solutions for the pair (x,y) and 3 solutions for the pair (z,w);

%e  - x*y = z*w = t has 3 solutions for the pair (x,y) and 3 solutions for the pair (z,w);

%e  - x*y = z*w = 1+t has 3 solutions for the pair (x,y) and 3 solutions for the pair (z,w),

%e so a(4) = 7*7 + 3*3*3 = 76.

%t Map[#^3+#^2-#&,Select[Range[200],PrimePowerQ]] (* _Paolo Xausa_, Nov 26 2023 *)

%o (PARI) lim_A367014(N) = for(n=2, N, if(isprimepower(n), print1(n^3 + n^2 - n, ", ")))

%o (Python)

%o from sympy import primepi, integer_nthroot

%o def A367014(n):

%o     def bisection(f,kmin=0,kmax=1):

%o         while f(kmax) > kmax: kmax <<= 1

%o         while kmax-kmin > 1:

%o             kmid = kmax+kmin>>1

%o             if f(kmid) <= kmid:

%o                 kmax = kmid

%o             else:

%o                 kmin = kmid

%o         return kmax

%o     def f(x): return int(n+x-sum(primepi(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length())))

%o     return (m:=bisection(f,n,n))*(m*(m+1)-1) # _Chai Wah Wu_, Jan 19 2025

%Y Cf. A246655, A101455 ({kronecker(-4,n)}).

%K nonn

%O 1,1

%A _Jianing Song_, Nov 01 2023