login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A091143 Number of Pythagorean triples mod 2^n; i.e., number of solutions to x^2 + y^2 = z^2 mod 2^n. 2
1, 4, 24, 96, 448, 1792, 7680, 30720, 126976, 507904, 2064384, 8257536, 33292288, 133169152, 534773760, 2139095040, 8573157376, 34292629504, 137304735744, 549218942976, 2197949513728, 8791798054912, 35175782154240, 140703128616960, 562881233944576 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

This Mathematica program is much more efficient than the one given in A062775.

LINKS

T. D. Noe, Table of n, a(n) for n = 0..100

L. Toth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014) # 14.11.6.

Index entries for linear recurrences with constant coefficients, signature (4,8,-32).

FORMULA

a(2*k) = (2^(k+1)-1)*2^(3*k), a(2*k-1) = (2^k-1)*2^(3*k-1).

From Colin Barker, Oct 27 2013:

a(n) = 4*a(n-1) + 8*a(n-2) - 32*a(n-3).

G.f.: 1 / ((4*x-1)*(8*x^2-1)). (End)

MAPLE

seq(op([(2^k-1)*2^(3*k-3), (2^k-1)*2^(3*k-1)]), k=1..30); # Robert Israel, Dec 03 2017

MATHEMATICA

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

PROG

(PARI) Vec(1/((4*x-1)*(8*x^2-1)) + O(x^100)) \\ Colin Barker, Oct 27 2013

CROSSREFS

Cf. A062775 (number of Pythagorean triples mod n).

Sequence in context: A054603 A100381 A319793 * A119920 A100738 A139238

Adjacent sequences:  A091140 A091141 A091142 * A091144 A091145 A091146

KEYWORD

nonn,easy

AUTHOR

T. D. Noe, Dec 22 2003

STATUS

approved

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 February 20 04:24 EST 2020. Contains 332063 sequences. (Running on oeis4.)