A378298 Number of solutions that satisfy the congruence: i^2 == j^2 (mod n) with 1 <= i < j <= n.

0, 0, 1, 2, 2, 2, 3, 8, 6, 4, 5, 14, 6, 6, 15, 24, 8, 12, 9, 26, 22, 10, 11, 48, 20, 12, 27, 38, 14, 30, 15, 64, 36, 16, 41, 66, 18, 18, 43, 88, 20, 44, 21, 62, 72, 22, 23, 136, 42, 40, 57, 74, 26, 54, 67, 128, 64, 28, 29, 150, 30, 30, 105, 160, 80, 72, 33, 98

Offset: 1

Author

Darío Clavijo, Nov 22 2024

Keywords

• nonn

Comments

a(n) >= A060594(n) for n >= 4.

Examples

			a(12) = 14 as the remainders 0 through 11 (mod 12) occur 2, 4, 0, 0, 4, 0, 0, 0, 0, 2, 0, 0 times respectively so a(12) = binomial(2, 2) + binomial(4, 2) + binomial(0, 2) + ... + binomial(0, 2) + binomial(0, 2) = 14. - _David A. Corneth_, Nov 25 2024
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000
• Darío Clavijo, Python program, Github.

Crossrefs

Cf. A000079, A000217, A036289, A060594, A373749.

Programs

Maple

a:= n-> add(i*(i-1), i=coeffs(add(x^(j^2 mod n), j=1..n)))/2:
seq(a(n), n=1..68);  # Alois P. Heinz, Nov 25 2024

Mathematica

a[n_]:=Sum[Sum[Boole[PowerMod[i,2 , n ]== PowerMod[j,2 ,n]],{j,i+1,n}],{i,n}]; Array[a,68] (* Stefano Spezia, Nov 22 2024 *)

PARI

a(n) = sum(i=1, n, sum(j=i+1, n, Mod(i, n)^2 == Mod(j, n)^2)); \\ Michel Marcus, Nov 25 2024

PARI

a(n) = {
	my(v = vector(n), res = 0);
	for(i = 1, n,
		v[(i^2%n)+1]++;	
	);
	sum(i = 1, n, binomial(v[i], 2))
} \\ David A. Corneth, Nov 25 2024

Python

from collections import defaultdict
def a(n: int) -> int:
    s = defaultdict(int)
    for i in range(1, n+1):
        s[pow(i,2,n)] += 1
    return sum(k*(k-1)>>1 for k in s.values())
print([a(n) for n in range(1, 69)])

Python

from sympy import isprime
def A378298(n):
    if isprime(n): return n-1>>1
    c, d = [0]*n, 0
    for i in range(n):
        d += c[m:=i**2%n]
        c[m] += 1
    return d # Chai Wah Wu, Nov 28 2024

Formula

a(n) = Sum_{i=1..n} Sum_{j=i+1..n} [i^2 mod n == j^2 mod n], where [] denotes the Iverson bracket.

a(n) = Sum_{i=1..n} Sum_{j=i+1..n} [A373749(n,i) = A373749(n,j)] , where [] denotes the Iverson bracket.

a(2^k) = A036289(k-1).

If p is an odd prime, then a(p) = (p-1)/2. - Chai Wah Wu, Nov 27 2024