cp's OEIS Frontend

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

%I A378298 #62 Nov 28 2024 19:24:55
%S A378298 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,
%T A378298 14,30,15,64,36,16,41,66,18,18,43,88,20,44,21,62,72,22,23,136,42,40,
%U A378298 57,74,26,54,67,128,64,28,29,150,30,30,105,160,80,72,33,98
%N A378298 Number of solutions that satisfy the congruence: i^2 == j^2 (mod n) with 1 <= i < j <= n.
%C A378298 a(n) >= A060594(n) for n >= 4.
%H A378298 Alois P. Heinz, <a href="/A378298/b378298.txt">Table of n, a(n) for n = 1..10000</a>
%H A378298 Darío Clavijo, <a href="https://github.com/daedalus/MyOEISPrograms/blob/main/A378298.py">Python program</a>, Github.
%F A378298 a(n) = Sum_{i=1..n} Sum_{j=i+1..n} [i^2 mod n == j^2 mod n], where [] denotes the Iverson bracket.
%F A378298 a(n) = Sum_{i=1..n} Sum_{j=i+1..n} [A373749(n,i) = A373749(n,j)] , where [] denotes the Iverson bracket.
%F A378298 a(2^k) = A036289(k-1).
%F A378298 If p is an odd prime, then a(p) = (p-1)/2. - _Chai Wah Wu_, Nov 27 2024
%e A378298 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
%p A378298 a:= n-> add(i*(i-1), i=coeffs(add(x^(j^2 mod n), j=1..n)))/2:
%p A378298 seq(a(n), n=1..68);  # _Alois P. Heinz_, Nov 25 2024
%t A378298 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 *)
%o A378298 (Python)
%o A378298 from collections import defaultdict
%o A378298 def a(n: int) -> int:
%o A378298     s = defaultdict(int)
%o A378298     for i in range(1, n+1):
%o A378298         s[pow(i,2,n)] += 1
%o A378298     return sum(k*(k-1)>>1 for k in s.values())
%o A378298 print([a(n) for n in range(1, 69)])
%o A378298 (Python)
%o A378298 from sympy import isprime
%o A378298 def A378298(n):
%o A378298     if isprime(n): return n-1>>1
%o A378298     c, d = [0]*n, 0
%o A378298     for i in range(n):
%o A378298         d += c[m:=i**2%n]
%o A378298         c[m] += 1
%o A378298     return d # _Chai Wah Wu_, Nov 28 2024
%o A378298 (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
%o A378298 (PARI) a(n) = {
%o A378298 	my(v = vector(n), res = 0);
%o A378298 	for(i = 1, n,
%o A378298 		v[(i^2%n)+1]++;	
%o A378298 	);
%o A378298 	sum(i = 1, n, binomial(v[i], 2))
%o A378298 } \\ _David A. Corneth_, Nov 25 2024
%Y A378298 Cf. A000079, A000217, A036289, A060594, A373749.
%K A378298 nonn
%O A378298 1,4
%A A378298 _Darío Clavijo_, Nov 22 2024