cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 26 results. Next

A125790 Rectangular table where column k equals row sums of matrix power A078121^k, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 10, 9, 4, 1, 1, 36, 35, 16, 5, 1, 1, 202, 201, 84, 25, 6, 1, 1, 1828, 1827, 656, 165, 36, 7, 1, 1, 27338, 27337, 8148, 1625, 286, 49, 8, 1, 1, 692004, 692003, 167568, 25509, 3396, 455, 64, 9, 1, 1, 30251722, 30251721, 5866452, 664665, 64350, 6321, 680, 81, 10, 1
Offset: 0

Views

Author

Paul D. Hanna, Dec 10 2006, corrected Dec 12 2006

Keywords

Comments

Determinant of n X n upper left submatrix is 2^[n(n-1)(n-2)/6] (see A125791). Related to partitions of numbers into powers of 2 (see A078121). Triangle A078121 shifts left one column under matrix square.

Examples

			Recurrence T(n,k) = T(n,k-1) + T(n-1,2*k) is illustrated by:
  T(4,3) = T(4,2) + T(3,6) = 201 + 455 = 656;
  T(5,3) = T(5,2) + T(4,6) = 1827 + 6321 = 8148;
  T(6,3) = T(6,2) + T(5,6) = 27337 + 140231 = 167568.
Rows of this table begin:
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...;
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...;
  1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, ...;
  1, 10, 35, 84, 165, 286, 455, 680, 969, 1330, 1771, 2300, ...;
  1, 36, 201, 656, 1625, 3396, 6321, 10816, 17361, 26500, 38841, ...;
  1, 202, 1827, 8148, 25509, 64350, 140231, 274856, 497097, ...;
  1, 1828, 27337, 167568, 664665, 2026564, 5174449, 11622976, ...;
  1, 27338, 692003, 5866452, 29559717, 109082974, 326603719, ...;
  1, 692004, 30251721, 356855440, 2290267225, 10243585092, ...; ...
Triangle A078121 begins:
  1;
  1,   1;
  1,   2,   1;
  1,   4,   4,   1;
  1,  10,  16,   8,   1;
  1,  36,  84,  64,  16,  1;
  1, 202, 656, 680, 256, 32, 1; ...
where row sums form column 1 of this table A125790,
and column k of A078121 equals column 2^k-1 of this table A125790.
Matrix cube A078121^3 begins:
     1;
     3,    1;
     9,    6,    1;
    35,   36,   12,   1;
   201,  286,  144,  24,  1;
  1827, 3396, 2300, 576, 48, 1; ...
where row sums form column 3 of this table A125790,
and column 0 of A078121^3 forms column 2 of this table A125790.
		

Crossrefs

Cf. A078121; A002577; A125791; columns: A002577, A125792, A125793, A125794, A125795, A125796; diagonals: A125797, A125798; A125799 (antidiagonal sums); related table: A125800 (q=3).

Programs

  • Mathematica
    T[n_, k_] := T[n, k] = T[n, k-1] + T[n-1, 2*k]; T[0, ] = T[, 0] = 1; Table[T[n-k, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 15 2015 *)
  • PARI
    {T(n,k,p=0,q=2)=local(A=Mat(1), B); if(n
    				

Formula

T(n,k) = T(n,k-1) + T(n-1,2*k) for n>0, k>0, with T(0,n)=T(n,0)=1 for n>=0.
Conjecture: g.f. for n-th row is (Sum_{i=0..n-1} x^i Sum_{j=0..i} binomial(n+1,j)*T(n,i-j)*(-1)^j)/(1-x)^(n+1) for n > 0. - Mikhail Kurkov, May 03 2025

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

Views

Author

Paul D. Hanna, Dec 10 2006

Keywords

Comments

Triangle A078121 shifts left one column under matrix square and is related to partitions into powers of 2.
Number of partitions of 2^n into powers of 2, excluding the trivial partition 2^n=2^n. - Valentin Bakoev, Feb 15 2009

Examples

			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]
		

Crossrefs

Adding 1 to the members of A125792 we obtain A002577. [Valentin Bakoev, Feb 15 2009]
A diagonal of A152977.

Programs

  • Maple
    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
  • Mathematica
    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 *)
  • PARI
    {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),", "))
    
  • PARI
    {a(n, k=3) = if(n<1, n==0, sum(i=1, k, a(n-1, 2*i-1)))}; /* Michael Somos, Nov 24 2016 */

Formula

Is this sequence the same as A002575 (coefficients of Bell's formula)?
Denote the sum m^n + m^n + ... + m^n, k times, by k*m^n (m > 1, n > 0 and k are natural numbers). The general formula for the number of all partitions of the sum k*m^n into powers of m, smaller than m^n, is t_m(n, k)= 1 when n=1 or k=0, or = t_m(n, k-1) + Sum_{j=1..m} t_m(n-1, (k-1)*n+j), when n > 1 and k > 0. A125792 is obtained for m=2 and n=1,2,3,... [Valentin Bakoev, Feb 15 2009]
a(n) = A145515(n+1,2)-1. - Alois P. Heinz, Feb 27 2009
From Benedict W. J. Irwin, Nov 16 2016: (Start)
Conjecture: a(n+1) = Sum_{i_1=1..3} Sum_{i_2=1..2*i_1-1} ... Sum_{i_n=1..2*i_(n-1)-1} (2*i_n - 1). For example:
a(2) = Sum_{i=1..3} 2*i-1.
a(3) = Sum_{i=1..3} Sum_{j=1..2*i-1} 2*j-1.
a(4) = Sum_{i=1..3} Sum_{j=1..2*i-1} Sum_{k=1..2*j-1} 2*k-1. (End)

A111814 Column 0 of the matrix logarithm (A111813) of triangle A078121, which shifts columns left and up under matrix square; these terms are the result of multiplying the element in row n by n!.

Original entry on oeis.org

0, 1, 0, -2, 0, 216, 0, -568464, 0, 36058658688, 0, -53694310935340800, 0, 1790669979087018171448320, 0, -1280832788659041410080025283840000, 0, 18961468161294510864200732026858464699187200, 0
Offset: 0

Views

Author

Gottfried Helms and Paul D. Hanna, Aug 22 2005

Keywords

Comments

Surprisingly, the e.g.f. A(x) is an odd function: A(-x) = -A(x). Let q=2; the g.f. of column k of A078121^m (matrix power m) is: 1 + Sum_{n>=1} (m*q^k)^n/n! * Product_{j=0..n-1} A(q^j*x).

Examples

			E.g.f.: A(x) = x - 2/3!*x^3 + 216/5!*x^5 - 568464/7!*x^7 + ...
where A(x) satisfies:
x/(1-x) = A(x) + A(x)*A(2*x)/2! + A(x)*A(2*x)*A(2^2*x)/3!
+ A(x)*A(2*x)*A(2^2*x)*A(2^3*x)/4! + ...
also:
x/(1-x^2) = A(x) + A(x)*A(2*x)*A(2^2*x)/3!
+ A(x)*A(2*x)*A(2^2*x)*A(2^3*x)*A(2^4*x)/5! + ...
Let G(x) be the g.f. of A002577 (column 1 of A078121), then
G(x) = 1 + 2*A(x) + 2^2*A(x)*A(2*x)/2! +
2^3*A(x)*A(2*x)*A(2^2*x)/3! +
2^4*A(x)*A(2*x)*A(2^2*x)*A(2^3*x)/4! + ...
		

Crossrefs

Cf. A078121 (triangle), A002577, A111813 (matrix log); A110505 (q=-1), A111816 (q=3), A111819 (q=4), A111824 (q=5), A111829 (q=6), A111834 (q=7), A111839 (q=8).

Programs

  • PARI
    {a(n,q=2)=local(A=x/(1-x+x*O(x^n)));for(i=1,n, A=x/(1-x)/(1+sum(j=1,n,prod(k=1,j,subst(A,x,q^k*x))/(j+1)!))); return(n!*polcoeff(A,n))}

Formula

E.g.f. satisfies: x/(1-x) = Sum_{n>=1} Prod_{j=0..n-1} A(2^j*x)/(j+1). E.g.f. satisfies: x/(1-x^2) = Sum_{n>=1}Prod_{j=0..2*n}A(2^j*x)/(j+1).

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

Views

Author

Paul D. Hanna, Dec 10 2006

Keywords

Comments

Triangle A078121 shifts left one column under matrix square and is related to partitions into powers of 2.

Crossrefs

A diagonal of A152977.

Programs

  • PARI
    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]))

A111813 Matrix log of triangle A078121, which shifts columns left and up under matrix square; these terms are the result of multiplying each element in row n and column k by (n-k)!.

Original entry on oeis.org

0, 1, 0, 0, 2, 0, -2, 0, 4, 0, 0, -4, 0, 8, 0, 216, 0, -8, 0, 16, 0, 0, 432, 0, -16, 0, 32, 0, -568464, 0, 864, 0, -32, 0, 64, 0, 0, -1136928, 0, 1728, 0, -64, 0, 128, 0, 36058658688, 0, -2273856, 0, 3456, 0, -128, 0, 256, 0, 0, 72117317376, 0, -4547712, 0, 6912, 0, -256, 0, 512, 0
Offset: 0

Views

Author

Gottfried Helms and Paul D. Hanna, Aug 22 2005

Keywords

Comments

Column k equals 2^k multiplied by column 0 (A111814) when ignoring zeros above the diagonal.

Examples

			Matrix log of A078121, with factorial denominators, begins:
0;
1/1!, 0;
0/2!, 2/1!, 0;
-2/3!, 0/2!, 4/1!, 0;
0/4!, -4/3!, 0/2!, 8/1!, 0;
216/5!, 0/4!, -8/3!, 0/2!, 16/1!, 0;
0/6!, 432/5!, 0/4!, -16/3!, 0/2!, 32/1!, 0;
-568464/7!, 0/6!, 864/5!, 0/4!, -32/3!, 0/2!, 64/1!, 0; ...
		

Crossrefs

Cf. A078121, A111814 (column 0), A111810 (variant); log matrices: A110504 (q=-1), A111815 (q=3), A111818 (q=4), A111823 (q=5), A111828 (q=6), A111833 (q=7), A111838 (q=8).

Programs

  • PARI
    T(n,k,q=2)=local(A=Mat(1),B);if(n
    				

Formula

T(n, k) = 2^k*T(n-k, 0) = A111814(n-k) for n>=k>=0.

A125793 Column 3 of table A125790; also equals row sums of matrix power A078121^3.

Original entry on oeis.org

1, 4, 16, 84, 656, 8148, 167568, 5866452, 356855440, 38315189204, 7352635371152, 2547660633170900, 1607532367023451792, 1860491404939092059092, 3974085151281967171382928, 15751822048486986712162264020
Offset: 0

Views

Author

Paul D. Hanna, Dec 10 2006

Keywords

Comments

Triangle A078121 shifts left one column under matrix square and is related to partitions into powers of 2.

Crossrefs

Programs

  • PARI
    a(n)=local(p=3,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]))

A125795 Column 5 of table A125790; also equals row sums of matrix power A078121^5.

Original entry on oeis.org

1, 6, 36, 286, 3396, 64350, 2026564, 109082974, 10243585092, 1704787839326, 509106367263812, 275575947307878750, 272638898948894782532, 496470192421055920965982, 1674003944602430578138969156, 10505662319550964196499807897950, 123269344114733507237294056110191684
Offset: 0

Views

Author

Paul D. Hanna, Dec 10 2006

Keywords

Comments

Triangle A078121 shifts left one column under matrix square and is related to partitions into powers of 2.

Crossrefs

Programs

  • PARI
    a(n)=local(p=5,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]))

A125796 Column 6 of table A125790; also equals row sums of matrix power A078121^6.

Original entry on oeis.org

1, 7, 49, 455, 6321, 140231, 5174449, 326603719, 35994670257, 7036275790791, 2470183452677297, 1573137497080468423, 1832597507832323118257, 3932481446278522861786055, 15637033863127787477309461681, 115814953429924513361085880079303, 1604893891765170672173387008222303409
Offset: 0

Views

Author

Paul D. Hanna, Dec 10 2006

Keywords

Comments

Triangle A078121 shifts left one column under matrix square and is related to partitions into powers of 2.

Crossrefs

Programs

  • PARI
    a(n)=local(p=6,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]))

A000123 Number of binary partitions: number of partitions of 2n into powers of 2.

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 20, 26, 36, 46, 60, 74, 94, 114, 140, 166, 202, 238, 284, 330, 390, 450, 524, 598, 692, 786, 900, 1014, 1154, 1294, 1460, 1626, 1828, 2030, 2268, 2506, 2790, 3074, 3404, 3734, 4124, 4514, 4964, 5414, 5938, 6462, 7060, 7658, 8350, 9042, 9828
Offset: 0

Views

Author

Keywords

Comments

Also, a(n) = number of "non-squashing" partitions of 2n (or 2n+1), that is, partitions 2n = p_1 + p_2 + ... + p_k with 1 <= p_1 <= p_2 <= ... <= p_k and p_1 + p_2 + ... + p_i <= p_{i+1} for all 1 <= i < k [Hirschhorn and Sellers].
Row sums of A101566. - Paul Barry, Jan 03 2005
Equals infinite convolution product of [1,2,2,2,2,2,2,2,2] aerated A000079 - 1 times, i.e., [1,2,2,2,2,2,2,2,2] * [1,0,2,0,2,0,2,0,2] * [1,0,0,0,2,0,0,0,2]. - Mats Granvik and Gary W. Adamson, Aug 04 2009
Which can be further decomposed to the infinite convolution product of finally supported sequences, namely [1,1] aerated A000079 - 1 times with multiplicity A000027 + 1 times, i.e., [1,1] * [1,1] * [1,0,1] * [1,0,1] * [1,0,1] * ... (next terms are [1,0,0,0,1] 4 times, etc.). - Eitan Y. Levine, Jun 18 2023
Given A018819 = A000123 with repeats, polcoeff (1, 1, 2, 2, 4, 4, ...) * (1, 1, 1, ...) = (1, 2, 4, 6, 10, ...) = (1, 0, 2, 0, 4, 0, 6, ...) * (1, 2, 2, 2, ...). - Gary W. Adamson, Dec 16 2009
Let M = an infinite lower triangular matrix with (1, 2, 2, 2, ...) in every column shifted down twice. A000123 = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. Replacing (1, 2, 2, 2, ...) with (1, 3, 3, 3, ...) and following the same procedure, we obtain A171370: (1, 3, 6, 12, 18, 30, 42, 66, 84, 120, ...). - Gary W. Adamson, Dec 06 2009
First differences of the sequence are (1, 2, 2, 4, 4, 6, 6, 10, ...), A018819, i.e., the sequence itself with each term duplicated except for the first one (unless a 0 is prefixed before taking the first differences), as shown by the formula a(n) - a(n-1) = a(floor(n/2)), valid for all n including n = 0 if we let a(-1) = 0. - M. F. Hasler, Feb 19 2019
Sum over k <= n of number of partitions of k into powers of 2, A018819. - Peter Munn, Feb 21 2020

Examples

			For non-squashing partitions and binary partitions see the example in A018819.
For n=3, the a(3)=6 admitted partitions of 2n=6 are 1+1+1+1+1+1, 1+1+1+1+2, 1+1+2+2, 2+2+2, 1+1+4 and 2+4. - _R. J. Mathar_, Aug 11 2021
		

References

  • G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976.
  • 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.
  • N. G. de Bruijn, On Mahler's partition problem, Indagationes Mathematicae, vol. X (1948), 210-220.
  • G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
  • H. Gupta, A simple proof of the Churchhouse conjecture concerning binary partitions, Indian J. Pure Appl. Math. 3 (1972), 791-794.
  • H. Gupta, A direct proof of the Churchhouse conjecture concerning binary partitions, Indian J. Math. 18 (1976), 1-5.
  • 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).

Crossrefs

Cf. A000041, A002033, A002487, A002577, A005704-A005706, A023359, A040039, A100529. Partial sums and bisection of A018819.
A column of A072170. Row sums of A089177. Twice A033485.
Cf. A145515. - Alois P. Heinz, Apr 16 2009
Cf. A171370. - Gary W. Adamson, Dec 06 2009

Programs

  • Haskell
    import Data.List (transpose)
    a000123 n = a000123_list !! n
    a000123_list = 1 : zipWith (+)
       a000123_list (tail $ concat $ transpose [a000123_list, a000123_list])
    -- Reinhard Zumkeller, Nov 15 2012, Aug 01 2011
    
  • Magma
    [1] cat [n eq 1 select n+1 else Self(n-1) + Self(n div 2): n in [1..70]]; // Vincenzo Librandi, Dec 17 2016
    
  • Maple
    A000123 := proc(n) option remember; if n=0 then 1 else A000123(n-1)+A000123(floor(n/2)); fi; end; [ seq(A000123(i),i=0..50) ];
    # second Maple program: more efficient for large n; try: a( 10^25 );
    g:= proc(b, n) option remember; `if`(b<0, 0, `if`(b=0 or
          n=0, 1, `if`(b>=n, add((-1)^(t+1)*binomial(n+1, t)
          *g(b-t, n), t=1..n+1), g(b-1, n)+g(2*b, n-1))))
        end:
    a:= n-> (t-> g(n/2^(t-1), t))(max(ilog2(2*n), 1)):
    seq(a(n), n=0..60); # Alois P. Heinz, Apr 16 2009, revised Apr 14 2016
  • Mathematica
    a[0] = 1; a[n_] := a[n] = a[Floor[n/2]] + a[n-1]; Array[a,49,0] (* Jean-François Alcover, Apr 11 2011, after M. F. Hasler *)
    Fold[Append[#1, Total[Take[Flatten[Transpose[{#1, #1}]], #2]]] &, {1}, Range[2, 49]] (* Birkas Gyorgy, Apr 18 2011 *)
  • PARI
    {a(n) = my(A, m); if( n<1, n==0, m=1; A = 1 + O(x); while(m<=n, m*=2; A = subst(A, x, x^2) * (1+x) / (1-x)); polcoeff(A, n))}; /* Michael Somos, Aug 25 2003 */
    
  • PARI
    {a(n) = if( n<1, n==0, a(n\2) + a(n-1))}; /* Michael Somos, Aug 25 2003 */
    
  • PARI
    A123=[];A000123(n)={ n<3 && return(2^n); if( n<=#A123, A123[n] && return(A123[n]); A123[n-1] && return( A123[n] = A123[n-1]+A000123(n\2) ), n>2*#A123 && A123=concat(A123,vector((n-#A123)\2))); A123[if(n>#A123,1,n)]=2*sum(k=1,n\2-1,A000123(k),1)+(n%2+1)*A000123(n\2)} \\ Stores results in global vector A123 dynamically resized to at most 3n/4 when size is less than n/2. Gives a(n*10^6) in ~ n sec. - M. F. Hasler, Apr 30 2009
    
  • PARI
    {a(n)=polcoeff(exp(sum(m=1,n,2^valuation(2*m,2)*x^m/m)+x*O(x^n)),n)} \\ Paul D. Hanna, Oct 30 2012
    
  • Python
    from functools import lru_cache
    @lru_cache(maxsize=None)
    def A000123(n): return 1 if n == 0 else A000123(n-1) + A000123(n//2) # Chai Wah Wu, Jan 18 2022

Formula

a(n) = A018819(2*n).
a(n) = a(n-1) + a(floor(n/2)). For proof see A018819.
2 * a(n) = a(n+1) + a(n-1) if n is even. - Michael Somos, Jan 07 2011
G.f.: (1-x)^(-1) Product_{n>=0} (1 - x^(2^n))^(-1).
a(n) = Sum_{i=0..n} a(floor(i/2)) [O'Shea].
a(n) = (1/n)*Sum_{k=1..n} (A038712(k)+1)*a(n-k), n > 1, a(0)=1. - Vladeta Jovovic, Aug 22 2002
Conjecture: Limit_{n ->infinity} (log(n)*a(2n))/(n*a(n)) = c = 1.63... - Benoit Cloitre, Jan 26 2003 [The constant c is equal to 2*log(2) = 1.38629436... =A016627. - Vaclav Kotesovec, Aug 07 2019]
G.f. A(x) satisfies A(x^2) = ((1-x)/(1+x)) * A(x). - Michael Somos, Aug 25 2003
G.f.: Product_{k>=0} (1+x^(2^k))/(1-x^(2^k)) = (Product_{k>=0} (1+x^(2^k))^(k+1) )/(1-x) = Product_{k>=0} (1+x^(2^k))^(k+2). - Joerg Arndt, Apr 24 2005
From Philippe Flajolet, Sep 06 2008: (Start)
The asymptotic rate of growth is known precisely - see De Bruijn's paper. With p(n) the number of partitions of n into powers of two, the asymptotic formula of de Bruijn is: log(p(2*n)) = 1/(2*L2)*(log(n/log(n)))^2 + (1/2 + 1/L2 + LL2/L2)*log(n) - (1 + LL2/L2)*log(log(n)) + Phi(log(n/log(n))/L2), where L2=log(2), LL2=log(log(2)) and Phi(x) is a certain periodic function with period 1 and a tiny amplitude.
Numerically, Phi(x) appears to have a mean value around 0.66. An expansion up to O(1) term had been obtained earlier by Kurt Mahler. (End)
G.f.: exp( Sum_{n>=1} 2^A001511(n) * x^n/n ), where 2^A001511(n) is the highest power of 2 that divides 2*n. - Paul D. Hanna, Oct 30 2012
(n/2)*a(n) = Sum_{k = 0..n-1} (n-k)/A000265(n-k)*a(k). - Peter Bala, Mar 03 2019
Conjectures from Mikhail Kurkov, May 04 2025: (Start)
Sum_{k=0..n} a(2^m*k)*A106400(n-k) = A125790(m,2*n) for m >= 0, n >= 0.
Sum_{k=0..n} a(2^m*(2*k+1))*A106400(n-k) = A125790(m+1,2*n+1) for m >= 0, n >= 0.
More generally, if we define b(n,m,p,q) = Sum_{k=0..n} a(2^m*(2*p*k+2*q+1))*A106400(n-k) for m >= 0, p > 0, q >= 0, n >= 0, then it also looks like that we have b(n,m,p,q) = Sum_{k=0..m+1} A078121(m+1,k)*b(n,k,p/2,(q-1)/2), b(n,m,p,q) = Sum_{k=0..m+1} A078121(m+1,k)*b(n,k,p/2,q/2)*(-1)^(m+k+1) for m >= 0, p > 0, q >= 0, n >= 0. (End)
Conjecture: Sum_{i>=0} a(2^m*i + k)*x^i = f(k,x) / Product_{q>=0} (1 - x^(2^q)) for m > 0, 2^(m-1) <= k < 2^m where f(k,x) is g.f. for k-th row of A381810. - Mikhail Kurkov, May 17 2025

Extensions

More terms from Robin Trew (trew(AT)hcs.harvard.edu)
Values up to a(10^4) checked with given PARI code by M. F. Hasler, Apr 30 2009

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

Views

Author

Keywords

Comments

For given m, the general formula for t_m(n, k) and the corresponding tables T, computed as in the example, determine a family of related sequences (placed in the rows or in the columns of T). For example, the numbers from the second row of T, computed for given m and n > 2, are the (m+2)-gonal numbers. So the second row contains the first members of: A000290 (the square numbers) when m=2, A000326 (the pentagonal numbers) when m=3, and so on. But rows IV, V etc. of the given table are not represented in the OEIS till now. - Valentin Bakoev, Feb 25 2009; edited by M. F. Hasler, Feb 09 2014

Examples

			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 + ...
		

References

  • 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).

Crossrefs

a(n) = A000123(2^(n-1)) = A018818(2^n).
Column k=2 of A145515, diagonal of A152977. - Alois P. Heinz, Mar 25 2012
See also A002575, A002576.
A column of A125790.

Programs

  • Haskell
    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
  • Maple
    A002577 := proc(n) if n<=1 then n+1 else A000123(2^(n-1)); fi; end;
  • Mathematica
    $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 *)
  • PARI
    a(n)=polcoeff(prod(j=0,n,1/(1-x^(2^j)+x*O(x^(2^n)))),2^n) \\ Paul D. Hanna
    

Formula

a(n) is about 0.9233*Sum_j {i=0, 1, 2, 3, ...} 2^(j*(2n-j-1)/2)/j!. - Henry Bottomley, Jul 23 2003
a(n) = A078121(n+1, 1). - Paul D. Hanna, Sep 13 2004
A002577(n)-1 = A125792(n). - Let m > 1, n > 0 and k >= 0. The general formula for the number of all partitions of k*m^n into powers of m is t_m(n, k)= k+1 if n=1, t_m(n, k)= 1 if k=0, and t_m(n, k)= t_m(n, k-1) + t_m(n-1, k*m) if n > 1 and k > 0. A002577 is obtained for m=2 and n=1,2,3,... - Valentin Bakoev, Feb 25 2009
a(n) = [x^(2^n)] 1/Product_{j>=0} (1-x^(2^j)). - Alois P. Heinz, Sep 27 2011

Extensions

Edited by M. F. Hasler, Feb 09 2014
Showing 1-10 of 26 results. Next