A002577
Number of partitions of 2^n into powers of 2.
Original entry on oeis.org
1, 2, 4, 10, 36, 202, 1828, 27338, 692004, 30251722, 2320518948, 316359580362, 77477180493604, 34394869942983370, 27893897106768940836, 41603705003444309596874, 114788185359199234852802340, 588880400923055731115178072778, 5642645813427132737155703265972004
Offset: 0
To compute t_2(6,1) we can use a table T, defined as T[i,j]= t_2(i,j), for i=1,2,...,6(=n), and j= 0,1,2,...,32(= k*m^{n-1}). It is: 1,2,3,4,5,6,7,8,9...,33; 1,4,9,16,25,36,49...,81; (so the second row contains the first members of A000290 -- the square numbers) 1,10,35,84,165,...,969; (so the third row contains the first members of A000447. The r-th tetrahedral number is given by formula r(r+1)(r+2)/6. This row (also A000447) contains the tetrahedral numbers, obtained for r=1,3,5,7,...) 1,36,201,656,1625; 1,202,1827; 1,1828; Column 1 contains the first 6 members of A002577. - _Valentin Bakoev_, Feb 25 2009
G.f. = 1 + 2*x + 4*x^2 + 10*x^3 + 36*x^4 + 202*x^5 + 1828*x^6 + ...
- R. F. Churchhouse, Binary partitions, pp. 397-400 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
- Lawrence, Jim. "Dual-Antiprisms and Partitions of Powers of 2 into Powers of 2." Discrete & Computational Geometry, Vol. 16 (2019): 465-478. See page 466.
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- Alois P. Heinz, Table of n, a(n) for n = 0..85
- V. Bakoev, Algorithmic approach to counting of certain types m-ary partitions, Discrete Mathematics, 275 (2004) pp.17-41.
- C. Banderier, H.-K. Hwang, V. Ravelomanana and V. Zacharovas, Analysis of an exhaustive search algorithm in random graphs and the n^{c logn}-asymptotics, 2012. - From _N. J. A. Sloane_, Dec 23 2012
- G. Blom and C.-E. Froeberg, Om myntvaexling, (On money-changing) [ Swedish ], Nordisk Matematisk Tidskrift, 10 (1962), 55-69, 103.
- G. Blom and C.-E. Froeberg, Om myntvaexling (On money-changing) [Swedish], Nordisk Matematisk Tidskrift, 10 (1962), 55-69, 103. [Annotated scanned copy]
- R. F. Churchhouse, Congruence properties of the binary partition function, Math. Proc. Cambr. Phil. Soc. vol 66, no. 2 (1969), 365-370.
- Carl-Erik Froberg, Accurate estimation of the number of binary partitions, BIT Numerical Mathematics vol. 17, no 4 (1977) 386-391.
- C.-E. Froberg, Accurate estimation of the number of binary partitions [Annotated scanned copy]
- H. Minc, The free commutative entropic logarithmetic, Proc. Roy. Soc. Edinburgh Sect. A 65 1959 177-192 (1959).
-
import Data.MemoCombinators (memo2, list, integral)
a002577 n = a002577_list !! n
a002577_list = f [1] where
f xs = (p' xs $ last xs) : f (1 : map (* 2) xs)
p' = memo2 (list integral) integral p
p 0 = 1; p [] = 0
p ks'@(k:ks) m = if m < k then 0 else p' ks' (m - k) + p' ks m
-- Reinhard Zumkeller, Nov 27 2015
-
A002577 := proc(n) if n<=1 then n+1 else A000123(2^(n-1)); fi; end;
-
$RecursionLimit = 10^5; (* b = A000123 *) b[0] = 1; b[n_?EvenQ] := b[n] = b[n-1] + b[n/2]; b[n_?OddQ] := b[n] = b[n-1] + b[(n-1)/2]; a[n_] := b[2^(n-1)]; a[0] = 1; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Nov 23 2011 *)
a[ n_] := SeriesCoefficient[ 1 / Product[ 1 - x^2^k, {k, 0, n}], {x, 0, 2^n}]; (* Michael Somos, Apr 21 2014 *)
-
a(n)=polcoeff(prod(j=0,n,1/(1-x^(2^j)+x*O(x^(2^n)))),2^n) \\ Paul D. Hanna
A094373
Expansion of (1-x-x^2)/((1-x)*(1-2*x)).
Original entry on oeis.org
1, 2, 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, 8193, 16385, 32769, 65537, 131073, 262145, 524289, 1048577, 2097153, 4194305, 8388609, 16777217, 33554433, 67108865, 134217729, 268435457, 536870913, 1073741825, 2147483649, 4294967297, 8589934593
Offset: 0
G.f. = 1 + 2*x + 3*x^2 + 5*x^3 + 9*x^4 + 17*x^5 + 33*x^6 + 65*x^7 + ...
Apart from the initial 1, identical to
A000051.
-
a:=[2,3];; for n in [3..40] do a[n]:=3*a[n-1]-2*a[n-2]; od; Concatenation([1], a); # G. C. Greubel, Nov 06 2019
-
[(2^n-0^n)/2+1: n in [0..40]]; // Vincenzo Librandi, Jun 10 2011
-
R:=PowerSeriesRing(Integers(), 35); Coefficients(R!( (1-x-x^2)/((1-x)*(1-2*x)))); // Marius A. Burtea, Oct 25 2019
-
1, seq((2^n - 0^n)/2 +1, n=1..40); # G. C. Greubel, Nov 06 2019
-
CoefficientList[Series[(1-x-x^2)/((1-x)*(1-2*x)), {x, 0, 40}], x] (* or *) Join[{1}, LinearRecurrence[{3, -2}, {2, 3}, 40]] (* Vladimir Joseph Stephan Orlovsky, Jan 22 2012 *)
a[ n_]:= If[n<0, 0, 1 + Quotient[2^n, 2]]; (* Michael Somos, May 26 2014 *)
a[ n_]:= SeriesCoefficient[(1-x-x^2)/((1-x)(1-2x)), {x, 0, n}]; (* Michael Somos, May 26 2014 *)
LinearRecurrence[{3,-2},{1,2,3},40] (* Harvey P. Dale, Aug 09 2015 *)
-
a(n)=2^n\2+1 \\ Charles R Greathouse IV, Apr 05 2013
-
Vec((1-x-x^2)/((1-x)*(1-2*x))+O(x^40)) \\ Charles R Greathouse IV, Apr 05 2013
-
[(2^n - 0^n)/2 + 1 for n in (0..40)] # G. C. Greubel, Nov 06 2019
A125792
Column 2 of table A125790; also equals row sums of matrix power A078121^2.
Original entry on oeis.org
1, 3, 9, 35, 201, 1827, 27337, 692003, 30251721, 2320518947, 316359580361, 77477180493603, 34394869942983369, 27893897106768940835, 41603705003444309596873, 114788185359199234852802339, 588880400923055731115178072777, 5642645813427132737155703265972003
Offset: 0
G.f.: 1 + 3*x + 9*x^2 + 35*x^3 + 201*x^4 + 1827*x^5 + 27337*x^6 + 692003*x^7 + ...
To obtain t_2(5,1) we use the table T, defined as T[i,j]= t_2(i,j), for i=1,2,...,5(=n), and j= 0,1,2,...,16(= k*m^{n-1}). It is 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,3,5,7,9,11,13,15,17 1,9,25,49,81 1,35,165 1,201 Column 1 contains the first 5 members of A125792. [_Valentin Bakoev_, Feb 15 2009]
-
g:= proc(b, n, k) option remember; local t; if b<0 then 0 elif b=0 or n=0 or k<=1 then 1 elif b>=n then add(g(b-t, n, k) *binomial(n+1, t) *(-1)^(t+1), t=1..n+1); else g(b-1, n, k) +g(b*k, n-1, k) fi end: a:= n-> g(1, n+1,2)-1: seq(a(n), n=0..25); # Alois P. Heinz, Feb 27 2009
-
T[n_, k_] := T[n, k] = T[n, k-1] + T[n-1, 2*k]; T[0, ] = T[, 0] = 1; Table[T[n, 2], {n, 0, 20} ] (* Jean-François Alcover, Jun 15 2015 *)
-
{a(n)=local(p=2,q=2,A=Mat(1), B); for(m=1, n+1, B=matrix(m, m); for(i=1, m, for(j=1, i, if(j==i||j==1, B[i, j]=1, B[i, j]=(A^q)[i-1, j-1]); )); A=B); return(sum(c=0,n,(A^p)[n+1,c+1]))}
for(n=0,25,print1(a(n),", "))
-
{a(n, k=3) = if(n<1, n==0, sum(i=1, k, a(n-1, 2*i-1)))}; /* Michael Somos, Nov 24 2016 */
A125794
Column 4 of table A125790; also equals row sums of matrix power A078121^4.
Original entry on oeis.org
1, 5, 25, 165, 1625, 25509, 664665, 29559717, 2290267225, 314039061413, 77160820913241, 34317392762489765, 27859502236825957465, 41575811106337540656037, 114746581654195790543205465, 588765612737696531880325270437, 5642056933026209681424588087899225
Offset: 0
-
a(n)=local(p=4,q=2,A=Mat(1), B); for(m=1, n+1, B=matrix(m, m); for(i=1, m, for(j=1, i, if(j==i || j==1, B[i, j]=1, B[i, j]=(A^q)[i-1, j-1]); )); A=B); return(sum(c=0,n,(A^p)[n+1,c+1]))
A210772
Number of partitions of 2^n into powers of 2 less than or equal to 8.
Original entry on oeis.org
1, 2, 4, 10, 35, 165, 969, 6545, 47905, 366145, 2862209, 22632705, 180007425, 1435853825, 11470030849, 91693092865, 733276217345, 5865135816705, 46916791205889, 375317149057025, 3002468471537665, 24019472891510785, 192154683614691329, 1537233070859485185
Offset: 0
a(3) = 10 because there are 10 partitions of 2^3 = 8 into powers of 2 less than or equal to 8: [1,1,1,1,1,1,1,1], [2,1,1,1,1,1,1], [2,2,1,1,1,1], [2,2,2,1,1], [2,2,2,2], [4,1,1,1,1], [4,2,1,1], [4,2,2], [4,4], [8].
-
a:= n-> `if`(n<2, 2^n, (Matrix(4, (i, j)-> `if`(i=j-1, 1, `if`(i=4,
[-64, 120, -70, 15][j], 0)))^(n-2). <<4, 10, 35, 165>>)[1,1]):
seq(a(n), n=0..30);
-
LinearRecurrence[{15,-70,120,-64},{1,2,4,10,35,165},30] (* Harvey P. Dale, Aug 27 2022 *)
-
Vec((1 - 13*x + 44*x^2 - 30*x^3 - 11*x^4 - 12*x^5) / ((1 - x)*(1 - 2*x)*(1 - 4*x)*(1 - 8*x)) + O(x^40)) \\ Colin Barker, Jan 26 2018
A210773
Number of partitions of 2^n into powers of 2 less than or equal to 16.
Original entry on oeis.org
1, 2, 4, 10, 36, 201, 1625, 17361, 222241, 3160641, 47594625, 738433281, 11633144321, 184687354881, 2943499290625, 47004182220801, 751333186150401, 12015464030289921, 192200500444954625, 3074832660977745921, 49194319991205396481, 787085099922532597761
Offset: 0
-
a:= n-> `if`(n<4, [1, 2, 4, 10][n+1], (Matrix(5, (i, j)-> `if`(i=j-1, 1, `if`(i=5, [1024, -1984, 1240, -310, 31][j], 0)))^(n-4). <<36, 201, 1625, 17361, 222241>>)[1,1]): seq(a(n), n=0..30);
-
LinearRecurrence[{31,-310,1240,-1984,1024},{1,2,4,10,36,201,1625,17361,222241},30] (* Harvey P. Dale, Oct 02 2020 *)
A210774
Number of partitions of 2^n into powers of 2 less than or equal to 32.
Original entry on oeis.org
1, 2, 4, 10, 36, 202, 1827, 25509, 497097, 12070289, 333620001, 9898583617, 304816671873, 9567029991681, 303182221750785, 9654673365689345, 308196987575257089, 9850278328626941953, 315016627560700387329, 10077456621734453460993, 322429412555504845881345
Offset: 0
-
a:= n-> `if`(n<5, [1, 2, 4, 10, 36][n+1], (Matrix(6, (i, j)-> `if`(i=j-1, 1, `if`(i=6, [-32768, 64512, -41664, 11160, -1302, 63][j], 0)))^(n-5). <<202, 1827, 25509, 497097, 12070289, 333620001>>)[1,1]): seq(a(n), n=0..20);
A210775
Number of partitions of 2^n into powers of 2 less than or equal to 64.
Original entry on oeis.org
1, 2, 4, 10, 36, 202, 1828, 27337, 664665, 23693265, 1092226081, 58686573121, 3431048928385, 209706732148993, 13113096655221249, 829504773400454145, 52778852611947546625, 3367976225848670392321, 215235141069830389702657, 13764966441742878856593409
Offset: 0
-
a:= n-> `if`(n<7, [1, 2, 4, 10, 36, 202, 1828][n+1], (Matrix(7, (i, j)-> `if`(i=j-1, 1, `if`(i=7, [2097152, -4161536, 2731008, -755904, 94488, -5334, 127][j], 0)))^(n-6). <<1828, 27337, 664665, 23693265, 1092226081, 58686573121, 3431048928385>>)[1,1]): seq(a(n), n=0..20);
A210776
Number of partitions of 2^n into powers of 2 less than or equal to 128.
Original entry on oeis.org
1, 2, 4, 10, 36, 202, 1828, 27338, 692003, 29559717, 1933411785, 169368653201, 17695666168609, 2038699559609921, 247324139826203777, 30811717563505088769, 3890604470232727499265, 494612931489164269609985, 63094694253683687355107329
Offset: 0
- Alois P. Heinz, Table of n, a(n) for n = 0..150
- Index entries for linear recurrences with constant coefficients, signature (255, -21590, 777240, -12850368, 99486720, -353730560, 534773760, -268435456).
-
gf:= (1 +(-253 +(21084 +(-735070 +(11379734 +(-76688022 +(199113750 +(-120814102 +(-42258923 +(-28134460 +(-57698752+(1018234880 +(-4990304256 +4009754624*x) *x) *x) *x) *x) *x) *x) *x) *x) *x) *x) *x) *x)/ mul(2^j*x-1, j=0..7): a:= n-> coeff(series(gf, x, n+1), x, n): seq(a(n), n=0..20);
A210777
Number of partitions of 2^n into powers of 2 less than or equal to 256.
Original entry on oeis.org
1, 2, 4, 10, 36, 202, 1828, 27338, 692004, 30251721, 2290267225, 275723872209, 45943934602273, 9336623954364993, 2119856439870545025, 510453118614955153665, 126696287737269468934657, 31933986928271408429425665, 8111646059635412792802330625
Offset: 0
- Alois P. Heinz, Table of n, a(n) for n = 0..130
- Index entries for linear recurrences with constant coefficients, signature (511, -86870, 6304280, -211823808, 3389180928, -25822330880, 91089797120, -137170518016, 68719476736).
-
gf:= (-1 +(509 +(-85852 +(6132574 +(-199557654 +(2989899926 +(-19831247382 +(51093934102 +(-30886151190 +(-10790841321 +(-7148051274 +(100712240 +(-272750006528 +(-281547988992 +(28916158300160 +(-83085001490432 +54717883351040*x) *x) *x) *x) *x) *x) *x) *x) *x) *x) *x) *x) *x) *x) *x) *x)/ mul(2^j*x-1, j=0..8): a:= n-> coeff(series(gf, x, n+1), x, n): seq(a(n), n=0..20);
Showing 1-10 of 12 results.
Comments