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

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, 60, 64, 68, 72, 72, 80, 80, 84, 88, 96, 100, 104, 108, 108, 112, 120, 124, 128, 128, 132, 136, 140, 148, 152, 156, 164, 168, 168, 172, 180, 180, 192, 192, 196, 200, 212, 224, 228, 228, 232

Offset: 1

Author

Jianing Song, Nov 01 2023

Keywords

• nonn

Comments

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.

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.

Examples

			For q = A246655(4) = 5, we see that in F_5:
 - x^2 + y^2 = 1 has 4 solutions (0,+-1), (+-1,0);
 - x^2 + y^2 = 2 has 4 solutions (+-1,+-1);
 - x^2 + y^2 = -2 has 4 solutions (+-2,+-2);
 - x^2 + y^2 = -1 has 4 solutions (+-2,0), (0,+-2),
so a(4) = 4.
For q = A246655(5) = 7, we see that in F_7:
 - x^2 + y^2 = 1 has 8 solutions (0,+-1), (+-1,0), (+-2,+-2);
 - x^2 + y^2 = 2 has 8 solutions (0,+-3), (+-3,0), (+-1,+-1);
 - x^2 + y^2 = 3 has 8 solutions (+-1,+-3), (+-3,+-1);
 - x^2 + y^2 = -3 has 8 solutions (+-2,0), (0,+-2), (+-3,+-3);
 - x^2 + y^2 = -2 has 8 solutions (+-1,+-2), (+-2,+-1);
 - x^2 + y^2 = -1 has 8 solutions (+-2,+-3), (+-3,+-2),
so a(5) = 8.
For q = A246655(7) = 9, we see that in F_9 = F_3(i):
 - x^2 + y^2 = 1 has 8 solutions (0,+-1), (+-1,0), (+-i,+-i);
 - x^2 + y^2 = -1 has 8 solutions (0,+-i), (+-i,0), (+-1,+-1);
 - x^2 + y^2 = 1+i has 8 solutions (+-1,+-(1-i)), (+-(1-i),+-1);
 - x^2 + y^2 = i has 8 solutions (0,+-(1-i)), (+-(1-i),0), (+-(1+i),+-(1+i));
 - x^2 + y^2 = -1+i has 8 solutions (+-i,+-(1-i)), (+-(1-i),+-i);
 - x^2 + y^2 = 1-i has 8 solutions (+-1,+-(1+i)), (+-(1+i),+-1);
 - x^2 + y^2 = -i has 8 solutions (0,+-(1+i)), (+-(1+i),0), (+-(1-i),+-(1-i));
 - x^2 + y^2 = -1-i has 8 solutions (+-i,+-(1+i)), (+-(1+i),+-i),
so a(7) = 8.
		

Links

• Jianing Song, Table of n, a(n) for n = 1..10000

Crossrefs

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

Programs

PARI

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

Python

from sympy import primepi, integer_nthroot, kronecker_symbol
def A367013(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return int(n+x-sum(primepi(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length())))
    return (m:=bisection(f,n,n))-kronecker_symbol(-4,m) # Chai Wah Wu, Jan 19 2025