The On-Line Encyclopedia of Integer Sequences (OEIS)

A378298 revision #47

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

COMMENTS

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

LINKS

Table of n, a(n) for n=1..68.

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

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

(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: A378294 A378295 A378296 * A378300 A378301 A378302

KEYWORD

nonn,changed

AUTHOR

Darío Clavijo, Nov 22 2024

STATUS

editing