cp's OEIS Frontend

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

%I A367013 #17 Jan 19 2025 01:30:12
%S A367013 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 A367013 60,64,68,72,72,80,80,84,88,96,100,104,108,108,112,120,124,128,128,
%U A367013 132,136,140,148,152,156,164,168,168,172,180,180,192,192,196,200,212,224,228,228,232
%N A367013 Let q be the n-th prime power (A246655), then a(n) = q - Kronecker(-4,q).
%C A367013 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 A367013 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 A367013 Jianing Song, <a href="/A367013/b367013.txt">Table of n, a(n) for n = 1..10000</a>
%e A367013 For q = A246655(4) = 5, we see that in F_5:
%e A367013  - x^2 + y^2 = 1 has 4 solutions (0,+-1), (+-1,0);
%e A367013  - x^2 + y^2 = 2 has 4 solutions (+-1,+-1);
%e A367013  - x^2 + y^2 = -2 has 4 solutions (+-2,+-2);
%e A367013  - x^2 + y^2 = -1 has 4 solutions (+-2,0), (0,+-2),
%e A367013 so a(4) = 4.
%e A367013 For q = A246655(5) = 7, we see that in F_7:
%e A367013  - x^2 + y^2 = 1 has 8 solutions (0,+-1), (+-1,0), (+-2,+-2);
%e A367013  - x^2 + y^2 = 2 has 8 solutions (0,+-3), (+-3,0), (+-1,+-1);
%e A367013  - x^2 + y^2 = 3 has 8 solutions (+-1,+-3), (+-3,+-1);
%e A367013  - x^2 + y^2 = -3 has 8 solutions (+-2,0), (0,+-2), (+-3,+-3);
%e A367013  - x^2 + y^2 = -2 has 8 solutions (+-1,+-2), (+-2,+-1);
%e A367013  - x^2 + y^2 = -1 has 8 solutions (+-2,+-3), (+-3,+-2),
%e A367013 so a(5) = 8.
%e A367013 For q = A246655(7) = 9, we see that in F_9 = F_3(i):
%e A367013  - x^2 + y^2 = 1 has 8 solutions (0,+-1), (+-1,0), (+-i,+-i);
%e A367013  - x^2 + y^2 = -1 has 8 solutions (0,+-i), (+-i,0), (+-1,+-1);
%e A367013  - x^2 + y^2 = 1+i has 8 solutions (+-1,+-(1-i)), (+-(1-i),+-1);
%e A367013  - x^2 + y^2 = i has 8 solutions (0,+-(1-i)), (+-(1-i),0), (+-(1+i),+-(1+i));
%e A367013  - x^2 + y^2 = -1+i has 8 solutions (+-i,+-(1-i)), (+-(1-i),+-i);
%e A367013  - x^2 + y^2 = 1-i has 8 solutions (+-1,+-(1+i)), (+-(1+i),+-1);
%e A367013  - x^2 + y^2 = -i has 8 solutions (0,+-(1+i)), (+-(1+i),0), (+-(1-i),+-(1-i));
%e A367013  - x^2 + y^2 = -1-i has 8 solutions (+-i,+-(1+i)), (+-(1+i),+-i),
%e A367013 so a(7) = 8.
%o A367013 (PARI) lim_A367013(N) = for(n=2, N, if(isprimepower(n), print1(n - kronecker(-4, n), ", ")))
%o A367013 (Python)
%o A367013 from sympy import primepi, integer_nthroot, kronecker_symbol
%o A367013 def A367013(n):
%o A367013     def bisection(f,kmin=0,kmax=1):
%o A367013         while f(kmax) > kmax: kmax <<= 1
%o A367013         while kmax-kmin > 1:
%o A367013             kmid = kmax+kmin>>1
%o A367013             if f(kmid) <= kmid:
%o A367013                 kmax = kmid
%o A367013             else:
%o A367013                 kmin = kmid
%o A367013         return kmax
%o A367013     def f(x): return int(n+x-sum(primepi(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length())))
%o A367013     return (m:=bisection(f,n,n))-kronecker_symbol(-4,m) # _Chai Wah Wu_, Jan 19 2025
%Y A367013 Cf. A246655, A101455 ({kronecker(-4,n)}), A181062 (x*y or x^2-y^2 instead of x^2+y^2).
%K A367013 nonn
%O A367013 1,1
%A A367013 _Jianing Song_, Nov 01 2023