cp's OEIS Frontend

A062775 Number of Pythagorean triples mod n: total number of solutions to x^2 + y^2 = z^2 mod n.

%I A062775 #56 Feb 26 2024 01:25:08
%S A062775 1,4,9,24,25,36,49,96,99,100,121,216,169,196,225,448,289,396,361,600,
%T A062775 441,484,529,864,725,676,891,1176,841,900,961,1792,1089,1156,1225,
%U A062775 2376,1369,1444,1521,2400,1681,1764,1849,2904,2475,2116,2209,4032,2695,2900
%N A062775 Number of Pythagorean triples mod n: total number of solutions to x^2 + y^2 = z^2 mod n.
%C A062775 a(n) is multiplicative and, for a prime p, a(p) = p^2. Hence a(n) = n^2 if n is squarefree.
%H A062775 Amiram Eldar, <a href="/A062775/b062775.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from T. D. Noe, terms 1001..5000 from Seiichi Manyama)
%H A062775 Gottfried Helms, <a href="https://groups.google.com/forum/#!msg/sci.math.research/pt0D1MdwNkU/LaVUc6A7FrEJ">Pythagorean triples mod n / Solution enhanced</a>, newsgroup sci.math.research, 2003.
%H A062775 László Tóth, <a href="http://arxiv.org/abs/1404.4214">Counting solutions of quadratic congruences in several variables revisited</a>,arXiv:1404.4214 [math.NT], 2014.
%H A062775 László Tóth, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Toth/toth12.html">Counting Solutions of Quadratic Congruences in Several Variables Revisited</a>, J. Int. Seq. 17 (2014), Article 14.11.6.
%H A062775 <a href="/index/Su#sums_of_squares">Index to sequences related to sums of squares</a>.
%F A062775 a(n) is multiplicative. For the powers of primes p, there are four cases. For p=2, there are cases for even and odd powers: a(2^(2k-1)) = 2^(3k-1) (2^k-1) and a(2^(2k)) = 2^(3k) (2^(k+1)-1). Similarly, for odd primes p, a(p^(2k-1)) = p^(3k-2) (p^k+p^(k-1)-1) and a(p^(2k)) = p^(3k-1) (p^(k+1)+p^k-1). - _T. D. Noe_, Dec 22 2003
%F A062775 From  _Gottfried Helms_, May 13 2004: (Start)
%F A062775 If the canonical form of n is n = 2^i * 3^j * 5^k *... * p^q, then it appears that a(n) = n * f(2, i) * f(3, j) * f(5, k) * ... * f(p, q), where f(p, 1) = p for any prime p; f(2, i) = 2^i + 2^i - 2^ceiling(i/2); f(p, i) = p^i + p^(i-1) - p^floor((i-1)/2) for any odd prime p.
%F A062775 For example, a(7) = 49 because a(7) = 7*f(7, 1) = 7*7; a(16) = 448 because a(16) = a(2^4) = 16 * f(2, 4) = 16 * (16+16-4) = 16*28 = 448; a(12) = 216 because a(12) = a(3*2^2) = 12*f(2, 2)*f(3, 1) = 12*(4+4-2)*3 = 216. (End)
%F A062775 Sum_{k=1..n} a(k) ~ c * n^3, where c = (16/45) * Product_{p prime} (1 + 1/(p^3 + p^2 + p)) = (16/45)*zeta(3)/zeta(4) = 0.39488943478263044166... . - _Amiram Eldar_, Oct 18 2022, Nov 30 2023
%p A062775 A062775 := proc(n)
%p A062775     a := 1;
%p A062775     for pe in ifactors(n)[2] do
%p A062775         p := op(1,pe) ;
%p A062775         e := op(2,pe) ;
%p A062775         if p = 2 then
%p A062775             if type(e,'odd') then
%p A062775                 a := a*p^((3*e+1)/2)*(2^((e+1)/2)-1) ;
%p A062775             else
%p A062775                 a := a*p^(3*e/2)*(2^(e/2+1)-1) ;
%p A062775             end if;
%p A062775         else
%p A062775             if type(e,'odd') then
%p A062775                 a := a*p^((3*e-1)/2)*(p^((e+1)/2)+p^((e-1)/2)-1) ;
%p A062775             else
%p A062775                 a := a*p^(3*e/2-1)*(p^(e/2+1)+p^(e/2)-1) ;
%p A062775             end if;
%p A062775         end if;
%p A062775     end do:
%p A062775     a ;
%p A062775 end proc:
%p A062775 seq(A062775(n),n=1..100) ; # _R. J. Mathar_, Jun 25 2018
%t A062775 Table[cnt=0; Do[If[Mod[x^2+y^2-z^2, n]==0, cnt++ ], {x, 0, n-1}, {y, 0, n-1}, {z, 0, n-1}]; cnt, {n, 50}]
%t A062775 f[p_, e_] := If[OddQ[e], p^(3*(e+1)/2 - 2)*(p^((e+1)/2) + p^((e-1)/2) - 1), p^(3*e/2 - 1) * (p^(e/2 + 1) + p^(e/2) - 1)]; f[2, e_] := If[OddQ[e], 2^(3*(e+1)/2 - 1)*(2^((e+1)/2) - 1), 2^(3*e/2)*(2^(e/2+1)-1)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 50] (* _Amiram Eldar_, Oct 18 2022 *)
%Y A062775 Cf. A091143 (number of solutions to x^2 + y^2 = z^2 mod 2^n).
%Y A062775 Cf. A060968, A087687, A002117, A013662.
%Y A062775 Number of solutions to x^k + y^k = z^k mod n: this sequence (k=2), A063454 (k=3), A288099 (k=4), A288100 (k=5), A288101 (k=6), A288102 (k=7), A288103 (k=8), A288104 (k=9), A288105 (k=10).
%K A062775 nonn,nice,mult
%O A062775 1,2
%A A062775 Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 18 2001
%E A062775 More terms from _Sascha Kurz_, Mar 25 2002