cp's OEIS Frontend

A091143 Number of Pythagorean triples mod 2^n; i.e., number of solutions to x^2 + y^2 = z^2 mod 2^n.

%I A091143 #27 Aug 16 2025 04:49:26
%S A091143 1,4,24,96,448,1792,7680,30720,126976,507904,2064384,8257536,33292288,
%T A091143 133169152,534773760,2139095040,8573157376,34292629504,137304735744,
%U A091143 549218942976,2197949513728,8791798054912,35175782154240,140703128616960,562881233944576
%N A091143 Number of Pythagorean triples mod 2^n; i.e., number of solutions to x^2 + y^2 = z^2 mod 2^n.
%C A091143 This Mathematica program is much more efficient than the one given in A062775.
%H A091143 T. D. Noe, <a href="/A091143/b091143.txt">Table of n, a(n) for n = 0..100</a>
%H A091143 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 A091143 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,8,-32).
%F A091143 a(2*k) = (2^(k+1)-1)*2^(3*k), a(2*k-1) = (2^k-1)*2^(3*k-1).
%F A091143 From _Colin Barker_, Oct 27 2013: (Start)
%F A091143 a(n) = 4*a(n-1) + 8*a(n-2) - 32*a(n-3).
%F A091143 G.f.: 1 / ((4*x-1)*(8*x^2-1)). (End)
%p A091143 seq(op([(2^k-1)*2^(3*k-3),(2^k-1)*2^(3*k-1)]),k=1..30); # _Robert Israel_, Dec 03 2017
%t A091143 Table[n = 2^k; b = Table[0, {n}]; Do[ b[[1 + Mod[i^2, n]]]++, {i, 0, n - 1}]; cnt = 0; Do[m = x^2 + y^2; cnt = cnt + b[[1 + Mod[m, n]]], {x, 0, n - 1}, {y, 0, n - 1}]; cnt, {k, 0, 13}]
%o A091143 (PARI) Vec(1/((4*x-1)*(8*x^2-1)) + O(x^100)) \\ _Colin Barker_, Oct 27 2013
%Y A091143 Cf. A062775 (number of Pythagorean triples mod n).
%K A091143 nonn,easy
%O A091143 0,2
%A A091143 _T. D. Noe_, Dec 22 2003