A016131 -id:A016131 - cp's OEIS frontend

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

J. M. Bergot, Mar 22 2011

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)

			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.

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

Cf. A016131.

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

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 *)

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

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

Heavily edited by Olivier Gérard, Mar 23 2011

More terms from Colin Barker, Aug 19 2013

A083333 a(n) = 10a(n-2) - 16a(n-4) for n>=4, with a(0)=a(1)=1, a(2)=6, a(3)=10.

Original entry on oeis.org

1, 1, 6, 10, 44, 84, 344, 680, 2736, 5456, 21856, 43680, 174784, 349504, 1398144, 2796160, 11184896, 22369536, 89478656, 178956800, 715828224, 1431655424, 5726623744, 11453245440, 45812985856, 91625967616, 366503878656

Offset: 0

Mario Catalani (mario.catalani(AT)unito.it), Apr 24 2003

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,10,0,-16).

Cf. A016131, A082412 (bisections).

Cf. A001045, A016116, A083332.

I:=[1,1,6,10]; [n le 4 select I[n] else 10*Self(n-2) -16*Self(n-4): n in [1..41]]; // G. C. Greubel, Dec 27 2024

CoefficientList[Series[(1+x-4x^2)/(1-10x^2+16x^4), {x, 0, 30}], x]
LinearRecurrence[{0,10,0,-16},{1,1,6,10},30] (* Harvey P. Dale, Aug 04 2024 *)

def A083333(n): return 2^((n-1)/2)*( (n%2)*(2^(n+1) -1) + ((n+1)%2)*sqrt(2)*(2^(n+1) +1))/3
print([A083333(n) for n in range(41)]) # G. C. Greubel, Dec 27 2024

G.f.: (1+x-4*x^2)/(1-10*x^2+16*x^4).
Limit_{n -> oo} A083332(n)/a(n) = 3.
a(n) = A001045(n+1)*A016116(n). - R. J. Mathar, Jul 08 2009
From G. C. Greubel, Dec 27 2024: (Start)
a(n) = (1/3)*2^((n-3)/2)*( (1-(-1)^n)*(2^(n+1) - 1) + (1+(-1)^n)*sqrt(2)*(2^(n+1) + 1) ).
E.g.f.: (1/3)*(2*cosh(2*sqrt(2)*x) + cosh(sqrt(2)*x)) + (1/(3*sqrt(2)))*(2*sinh(2*sqrt(2)*x) - sinh(sqrt(2)*x)). (End)

A092055 a(n) = binomial(2 + 2^n,3).

Original entry on oeis.org

1, 4, 20, 120, 816, 5984, 45760, 357760, 2829056, 22500864, 179481600, 1433753600, 11461636096, 91659526144, 733141975040, 5864598896640, 46914643623936, 375308558925824, 3002434111406080, 24019335451770880, 192154133857304576, 1537230871833083904, 12297838178567454720

Offset: 0

Henry Bottomley, Feb 19 2004

a(n) = Sum_{i=1...(2^n)} i*(i+1)/2, this sequence is thus similar to A016131 as it is a sum of triangular numbers on the interval <1,2^n>, A016131 is a sum of triangular numbers on the interval <1,2^n - 1>. - Ctibor O. Zizka, Mar 03 2009

a(n) is the number of unordered (not necessarily distinct) triples of subsets taken from the power set of {1,2,...,n}. Cf. A007582 (pairs of such subsets). - Geoffrey Critzer, Jul 10 2013

			a(5) = C(2+2^5,3) = C(34,3) = 5984.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (14,-56,64).

Cf. A000079, A007581, A092056, A016131.

[Binomial(2^n+2, 3): n in [0..30]]; // G. C. Greubel, Dec 27 2024

seq(binomial(2+2^n, 3), n=0..25); # Zerinvary Lajos, Feb 22 2008

nn=20;Table[Coefficient[Series[1/(1-x)^(2^n),{x,0,nn}],x^3],{n,0,nn}] (* Geoffrey Critzer, Jul 10 2013 *)
Binomial[2+2^Range[0,30], 3] (* G. C. Greubel, Dec 27 2024 *)

Vec((1-10*x+20*x^2)/((1-2*x)*(1-4*x)*(1-8*x)) + O(x^100)) \\ Colin Barker, Sep 13 2014

def A092055(n): return binomial(pow(2,n)+2,3)
print([A092055(n) for n in range(41)]) # G. C. Greubel, Dec 27 2024

a(n) = (2^(3*n-1) +3*2^(2*n-1) + 2^n)/3 = A092056(3, n).
a(n) = A000079(n)*A007581(n).
a(n) = 2*a(n-1) + 4^(n-1) + 8^(n-1).
a(n) = [x^3] 1/(1-x)^(2^n). - Geoffrey Critzer, Jul 11 2013
a(n) = 14*a(n-1) - 56*a(n-2) + 64*a(n-3). - Colin Barker, Sep 13 2014
G.f.: (1-10*x+20*x^2) / ((1-2*x)*(1-4*x)*(1-8*x)). - Colin Barker, Sep 13 2014
E.g.f.: (1/6)*(2*exp(2*x) + 3*exp(4*x) + exp(8*x)). - G. C. Greubel, Dec 27 2024

A025992 Expansion of 1/((1-2x)(1-5x)(1-7x)(1-8*x)).

Original entry on oeis.org

1, 22, 313, 3666, 38493, 377286, 3529681, 31947322, 282198565, 2447183310, 20920905369, 176852694018, 1481626607917, 12322682753494, 101879323774177, 838170485025354, 6867569457133749, 56077266261254238

Offset: 0

N. J. A. Sloane

From Bruno Berselli, May 09 2013: (Start)
a(n) - 2*a(n-1), for n>0, gives A019928 (after 1);
a(n) - 5*a(n-1), for n>0, gives A016311 (after 1);
a(n) - 7*a(n-1), for n>0, gives A016297 (after 1);
a(n) - 8*a(n-1), for n>0, gives A016296 (after 1);
a(n) - 7*a(n-1) + 10*a(n-2), for n>1, gives A016177 (after 15);
a(n) - 9*a(n-1) + 14*a(n-2), for n>1, gives A016162 (after 13);
a(n) - 10*a(n-1) + 16*a(n-2), for n>1, gives A016161 (after 12);
a(n) - 12*a(n-1) + 35*a(n-2), for n>1, gives A016131 (after 10);
a(n) - 13*a(n-1) + 40*a(n-2), for n>1, gives A016130 (after 9);
a(n) - 15*a(n-1) + 56*a(n-2), for n>1, gives A016127 (after 7);
a(n) - 20*a(n-1) +131*a(n-2) -280*a(n-3), for n>2, gives A000079 (after 4);
a(n) - 17*a(n-1) +86*a(n-2) -112*a(n-3), for n>2, gives A000351 (after 25);
a(n) - 15*a(n-1) +66*a(n-2) -80*a(n-3), for n>2, gives A000420 (after 49);
a(n) - 14*a(n-1) +59*a(n-2) -70*a(n-3), for n>2, gives A001018 (after 64),
and naturally: a(n) - 22*a(n-1) + 171*a(n-2) - 542*a(n-3) + 560*a(n-4), for n>3, gives 0 (see Harvey P. Dale in Formula lines). (End)

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Index entries for linear recurrences with constant coefficients, signature (22,-171,542,-560).

Cf. A000079, A000351, A000420, A001018, A016127, A016130, A016131, A016161, A016162, A016177, A016296, A016297, A016311, A019928.

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!(1/((1-2*x)*(1-5*x)*(1-7*x)*(1-8*x)))); // Bruno Berselli, May 09 2013

CoefficientList[Series[1/((1-2x)(1-5x)(1-7x)(1-8x)),{x,0,30}],x] (* or *) LinearRecurrence[ {22,-171,542,-560},{1,22,313,3666},30] (* Harvey P. Dale, Jan 29 2013 *)

a(n) = n+=3; (5*8^n-9*7^n+5*5^n-2^n)/90 \\ Charles R Greathouse IV, Oct 03 2016

def A025992(n): return (5*pow(8,n+3)-9*pow(7,n+3)+pow(5,n+4)-pow(2,n+3))//90
print([A025992(n) for n in range(41)]) # G. C. Greubel, Dec 27 2024

a(0)=1, a(1)=22, a(2)=313, a(3)=3666, a(n) = 22*a(n-1) - 171*a(n-2) + 542*a(n-3) - 560*a(n-4). - Harvey P. Dale, Jan 29 2013
a(n) = (5*8^(n+3) - 9*7^(n+3) + 5^(n+4) - 2^(n+3))/90. - Yahia Kahloune, May 07 2013
E.g.f.: (1/90)*(-8*exp(2*x) + 625*exp(5*x) - 3087*exp(7*x) + 2560*exp(8*x)). - G. C. Greubel, Dec 27 2024

A096041 Triangle read by rows: T(n,k) = (n+1,k)-th element of (M^7-M)/6, where M is the infinite lower Pascal's triangle matrix, 1<=k<=n.

Original entry on oeis.org

1, 8, 2, 57, 24, 3, 400, 228, 48, 4, 2801, 2000, 570, 80, 5, 19608, 16806, 6000, 1140, 120, 6, 137257, 137256, 58821, 14000, 1995, 168, 7, 960800, 1098056, 549024, 156856, 28000, 3192, 224, 8, 6725601, 8647200, 4941252, 1647072, 352926, 50400

Offset: 1

Gary W. Adamson, Jun 17 2004

			Triangle begins:
1
8 2
57 24 3
400 228 48 4
2801 2000 570 80 5
19608 16806 6000 1140 120 6

Cf. A007318. First column gives A023000. Row sums give A016131.

P:= proc(n) option remember; local M; M:= Matrix(n, (i, j)-> binomial(i-1, j-1)); (M^7-M)/6 end: T:= (n, k)-> P(n+1)[n+1, k]: seq(seq(T(n, k), k=1..n), n=1..11); # Alois P. Heinz, Oct 07 2009

P[n_] := P[n] = With[{M = Array[Binomial[#1-1, #2-1]&, {n, n}]}, (MatrixPower[M, 7] - M)/6]; T[n_, k_] := P[n+1][[n+1, k]]; Table[ Table[T[n, k], {k, 1, n}], {n, 1, 11}] // Flatten (* Jean-François Alcover, Jan 28 2015, after Alois P. Heinz *)

Edited with more terms by Alois P. Heinz, Oct 07 2009

A340554 T(n, k) = [x^k] hypergeom([-2^n/2, -2^n/2 - 1/2], [1/2], x). Triangle read by rows, T(n, k) for n >= 0.

Original entry on oeis.org

1, 1, 1, 3, 1, 10, 5, 1, 36, 126, 84, 9, 1, 136, 2380, 12376, 24310, 19448, 6188, 680, 17, 1, 528, 40920, 1107568, 13884156, 92561040, 354817320, 818809200, 1166803110, 1037158320, 573166440, 193536720, 38567100, 4272048, 237336, 5456, 33

Offset: 0

Peter Luschny, Feb 03 2021

			Triangle starts:
                           [0] 1, 1
                           [1] 1, 3
                         [2] 1, 10, 5
                     [3] 1, 36, 126, 84, 9
     [4] 1, 136, 2380, 12376, 24310, 19448, 6188, 680, 17

G. C. Greubel, Rows n = 0..11 of the irregular triangle, flattened

Cf. A001146 (row sums), A000051 (main diagonal), A016131 (central terms), A201461, A028297.

p:= func< n | n eq 0 select 1 else 2^(n-1) >;
T:= func< n,k | Factorial(2^n+1)/(Factorial(2*k)*Factorial(2^n-2*k+1)) >;
[T(n,k): k in [0..p(n)], n in [0..8]]; // G. C. Greubel, Dec 30 2024

CoeffList := p -> op(PolynomialTools:-CoefficientList(p, x)):
Tpoly := proc(n) simplify(hypergeom([-2^n/2, -2^n/2 - 1/2], [1/2], x)):
CoeffList(%) end: seq(Tpoly(n), n = 0..5);

Tpoly[n_] := HypergeometricPFQ[{-2^n/2, -2^n/2 - 1/2}, {1/2}, x];
Table[CoefficientList[Tpoly[n], x], {n, 0, 5}] // Flatten

# from sage.all import * # (use for Python)
def p(n): return 1 if n==0 else pow(2,n-1)
def T(n,k): return rising_factorial(-pow(2,n)-1, 2*k)/factorial(2*k)
print(flatten([[T(n,k) for k in range(p(n)+1)] for n in range(8)])) # G. C. Greubel, Dec 30 2024

T(n, k) = (2^n + 1)!/((2*k)! * (2^n - 2*k + 1)!), for n >= 0, 0 <= k <= p(n), where p(n) = 1 if n = 0 otherwise p(n) = 2^(n-1). Alternative form: T(n, k) = Pochhammer(-2^n - 1, 2*k)/(2*k)!. - G. C. Greubel, Dec 30 2024

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Python

Formula

Extensions

A083333 a(n) = 10*a(n-2) - 16*a(n-4) for n>=4, with a(0)=a(1)=1, a(2)=6, a(3)=10.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A092055 a(n) = binomial(2 + 2^n,3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A025992 Expansion of 1/((1-2*x)*(1-5*x)*(1-7*x)*(1-8*x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Formula

A096041 Triangle read by rows: T(n,k) = (n+1,k)-th element of (M^7-M)/6, where M is the infinite lower Pascal's triangle matrix, 1<=k<=n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions

A340554 T(n, k) = [x^k] hypergeom([-2^n/2, -2^n/2 - 1/2], [1/2], x). Triangle read by rows, T(n, k) for n >= 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A083333 a(n) = 10a(n-2) - 16a(n-4) for n>=4, with a(0)=a(1)=1, a(2)=6, a(3)=10.

A025992 Expansion of 1/((1-2x)(1-5x)(1-7x)(1-8*x)).