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,4

Comments

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

Links

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Darío Clavijo, Python program, Github.

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

Example

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

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 *)

Prog

(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
(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

Crossrefs

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

Sequence in context: A101360 A270371 A351108 * A184311 A110910 A119532

Adjacent sequences: A378295 A378296 A378297 * A378299 A378300 A378301

Keyword

nonn

Author

Darío Clavijo, Nov 22 2024

Status

approved