login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A062775 Number of Pythagorean triples mod n: total number of solutions to x^2 + y^2 = z^2 mod n. 14

%I

%S 1,4,9,24,25,36,49,96,99,100,121,216,169,196,225,448,289,396,361,600,

%T 441,484,529,864,725,676,891,1176,841,900,961,1792,1089,1156,1225,

%U 2376,1369,1444,1521,2400,1681,1764,1849,2904,2475,2116,2209,4032,2695,2900

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

%C a(n) is multiplicative and, for a prime p, a(p) = p^2. Hence a(n) = n^2 if n is squarefree.

%D See newsgroup sci.math.research; subject: Re: Pythagorean triples mod n / Solution enhanced; author: Gottfried Helms; Message-ID: brv5i2$28v$1(AT)news.ks.uiuc.edu; Date: Fri, Dec 19 2003 15: 30: 10 +0000 (UTC)

%H Seiichi Manyama, <a href="/A062775/b062775.txt">Table of n, a(n) for n = 1..5000</a> (terms 1..1000 from T. D. Noe)

%H L. Tóth, <a href="http://arxiv.org/abs/1404.4214">Counting solutions of quadratic congruences in several variables revisited</a>, arXiv preprint arXiv:1404.4214, 2014

%H L. Toth, <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) # 14.11.6.

%H <a href="/index/Su#sums_of_squares">Index to sequences related to sums of squares</a>

%F 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 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^ceil(i/2); f(p, i) = p^i + p^(i-1) - p^floor((i-1)/2) for any odd prime p. 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. - _Gottfried Helms_, May 13 2004

%p A062775 := proc(n)

%p a := 1;

%p for pe in ifactors(n)[2] do

%p p := op(1,pe) ;

%p e := op(2,pe) ;

%p if p = 2 then

%p if type(e,'odd') then

%p a := a*p^((3*e+1)/2)*(2^((e+1)/2)-1) ;

%p else

%p a := a*p^(3*e/2)*(2^(e/2+1)-1) ;

%p end if;

%p else

%p if type(e,'odd') then

%p a := a*p^((3*e-1)/2)*(p^((e+1)/2)+p^((e-1)/2)-1) ;

%p else

%p a := a*p^(3*e/2-1)*(p^(e/2+1)+p^(e/2)-1) ;

%p end if;

%p end if;

%p end do:

%p a ;

%p end proc:

%p seq(A062775(n),n=1..100) ; # _R. J. Mathar_, Jun 25 2018

%t 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}]

%Y Cf. A091143 (number of solutions to x^2 + y^2 = z^2 mod 2^n).

%Y Cf. A060968, A087687.

%Y 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 nonn,nice,mult

%O 1,2

%A Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 18 2001

%E More terms from _Sascha Kurz_, Mar 25 2002

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 11 04:29 EST 2018. Contains 318049 sequences. (Running on oeis4.)