%I #17 Jan 19 2025 01:30:12

%S 2,4,4,4,8,8,8,12,12,16,16,20,24,24,28,28,32,32,36,40,44,48,48,52,60,

%T 60,64,68,72,72,80,80,84,88,96,100,104,108,108,112,120,124,128,128,

%U 132,136,140,148,152,156,164,168,168,172,180,180,192,192,196,200,212,224,228,228,232

%N Let q be the n-th prime power (A246655), then a(n) = q - Kronecker(-4,q).

%C 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.

%C 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.

%H Jianing Song, <a href="/A367013/b367013.txt">Table of n, a(n) for n = 1..10000</a>

%e For q = A246655(4) = 5, we see that in F_5:

%e - x^2 + y^2 = 1 has 4 solutions (0,+-1), (+-1,0);

%e - x^2 + y^2 = 2 has 4 solutions (+-1,+-1);

%e - x^2 + y^2 = -2 has 4 solutions (+-2,+-2);

%e - x^2 + y^2 = -1 has 4 solutions (+-2,0), (0,+-2),

%e so a(4) = 4.

%e For q = A246655(5) = 7, we see that in F_7:

%e - x^2 + y^2 = 1 has 8 solutions (0,+-1), (+-1,0), (+-2,+-2);

%e - x^2 + y^2 = 2 has 8 solutions (0,+-3), (+-3,0), (+-1,+-1);

%e - x^2 + y^2 = 3 has 8 solutions (+-1,+-3), (+-3,+-1);

%e - x^2 + y^2 = -3 has 8 solutions (+-2,0), (0,+-2), (+-3,+-3);

%e - x^2 + y^2 = -2 has 8 solutions (+-1,+-2), (+-2,+-1);

%e - x^2 + y^2 = -1 has 8 solutions (+-2,+-3), (+-3,+-2),

%e so a(5) = 8.

%e For q = A246655(7) = 9, we see that in F_9 = F_3(i):

%e - x^2 + y^2 = 1 has 8 solutions (0,+-1), (+-1,0), (+-i,+-i);

%e - x^2 + y^2 = -1 has 8 solutions (0,+-i), (+-i,0), (+-1,+-1);

%e - x^2 + y^2 = 1+i has 8 solutions (+-1,+-(1-i)), (+-(1-i),+-1);

%e - x^2 + y^2 = i has 8 solutions (0,+-(1-i)), (+-(1-i),0), (+-(1+i),+-(1+i));

%e - x^2 + y^2 = -1+i has 8 solutions (+-i,+-(1-i)), (+-(1-i),+-i);

%e - x^2 + y^2 = 1-i has 8 solutions (+-1,+-(1+i)), (+-(1+i),+-1);

%e - x^2 + y^2 = -i has 8 solutions (0,+-(1+i)), (+-(1+i),0), (+-(1-i),+-(1-i));

%e - x^2 + y^2 = -1-i has 8 solutions (+-i,+-(1+i)), (+-(1+i),+-i),

%e so a(7) = 8.

%o (PARI) lim_A367013(N) = for(n=2, N, if(isprimepower(n), print1(n - kronecker(-4, n), ", ")))

%o (Python)

%o from sympy import primepi, integer_nthroot, kronecker_symbol

%o def A367013(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))-kronecker_symbol(-4,m) # _Chai Wah Wu_, Jan 19 2025

%Y Cf. A246655, A101455 ({kronecker(-4,n)}), A181062 (x*y or x^2-y^2 instead of x^2+y^2).

%K nonn

%O 1,1

%A _Jianing Song_, Nov 01 2023