A187468 Sum of the squares modulo 2^n of the odd numbers less than 2^n.

1, 2, 4, 40, 208, 928, 3904, 16000, 64768, 260608, 1045504, 4188160, 16764928, 67084288, 268386304, 1073643520, 4294770688, 17179475968, 68718690304, 274876334080, 1099508482048, 4398040219648, 17592173461504, 70368719011840, 281474926379008

Offset: 1

Author

J. M. Bergot, Mar 22 2011

Keywords

• nonn
• easy

Comments

There is a simple formula for this case; the sum of the squares of the odd numbers less than 2^n is A016131(n-1).

Can the general case for m^n, m > 2 be calculated with a formula of the same kind?

From R. J. Mathar, Aug 26 2013: (Start)

For n>=3, the sum of the squares of the even numbers less than 2^n (each square mod 2^n) are 8 times the sequence 1, 2, 12, 56, 304, 1376, 6336, 27008 etc. and appear to obey a(n)= +6*a(n-1) -48*a(n-3) +64*a(n-4).

For n>=1, the sum of the squares of the odd numbers less than 3^n (modulo 3^n) start as 2 times 1, 12, 144, 1404, 13689, 126360,.. and apparently obey a(n)= +12*a(n-1) -324*a(n-3) +729*a(n-4).

For n>=1, the sum of the squares of the odd numbers less than 4^n (modulo 4^n) start as 2 times 1, 28, 688, 13504, 238336,... and seem to obey a(n)= +28*a(n-1) -224*a(n-2) +512*a(n-3).

(End)

Examples

			For n=5, 2^5=32. The c_j, numbers prime to 32 are the odd numbers less than 32. The r_j = (c_j)^2 mod 32 are 1,9,25,17,17,25,9,1,1,9,25,17,17,25,9,1 = 4*52 = 208.
From the formula, for n=5, 2^(5-1) * (2^(5-1) - 3) = 16*13 = 208.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (6,-8).

Crossrefs

Cf. A016131.

Programs

Magma

[n le 2 select n else 2^(n-2)*(2^n - 6): n in [1..40]]; // G. C. Greubel, Dec 26 2024

Mathematica

Join[{1, 2}, Table[2^(n - 1) (2^(n - 1) - 3), {n, 3, 20}]]
LinearRecurrence[{6,-8}, {1,2,4,40}, 40] (* G. C. Greubel, Dec 26 2024 *)

Python

def A187468(n): return pow(2,n-2)*(pow(2,n) -6) +3*int(n==1) +4*int(n==2)
print([A187468(n) for n in range(1,41)]) # G. C. Greubel, Dec 26 2024

Formula

For n>2 the sum of all r_j = (c_j)^2 mod 2^n for a particular n is given by 2^(n-1)*(2^(n-1) - 3).

From Colin Barker, Aug 19 2013: (Start)

a(n) = 2^(n-2)*(2^n - 6) for n>2.

a(n) = 6*a(n-1) - 8*a(n-2) for n>4.

G.f.: x*(1 - 4*x + 32*x^3)/((1-2*x)*(1-4*x)). (End)

E.g.f.: (1/4)*(5 + 12*x + 8*x^2 - 6*exp(2*x) + exp(4*x)). - G. C. Greubel, Dec 26 2024

Extensions

Heavily edited by Olivier Gérard, Mar 23 2011

More terms from Colin Barker, Aug 19 2013