CINXE.COM
A000123 - OEIS
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> <html> <head> <link rel="stylesheet" href="/styles.css"> <meta name="format-detection" content="telephone=no"> <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta name=viewport content="width=device-width, initial-scale=1"> <meta name="keywords" content="OEIS,integer sequences,Sloane" /> <title>A000123 - OEIS</title> <link rel="search" type="application/opensearchdescription+xml" title="OEIS" href="/oeis.xml"> <script> var myURL = "\/A000123" function redir() { var host = document.location.hostname; if(host != "oeis.org" && host != "127.0.0.1" && !/^([0-9.]+)$/.test(host) && host != "localhost" && host != "localhost.localdomain") { document.location = "https"+":"+"//"+"oeis"+".org/" + myURL; } } function sf() { if(document.location.pathname == "/" && document.f) document.f.q.focus(); } </script> </head> <body bgcolor=#ffffff onload="redir();sf()"> <div class=loginbar> <div class=login> <a href="/login?redirect=%2fA000123">login</a> </div> </div> <div class=center><div class=top> <center> <div class=donors> The OEIS is supported by <a href="http://oeisf.org/#DONATE">the many generous donors to the OEIS Foundation</a>. </div> <div class=banner> <a href="/"><img class=banner border="0" width="600" src="/banner2021.jpg" alt="A000123 - OEIS"></a> </div> </center> </div></div> <div class=center><div class=pagebody> <div class=searchbarcenter> <form name=f action="/search" method="GET"> <div class=searchbargreet> <div class=searchbar> <div class=searchq> <input class=searchbox maxLength=1024 name=q value="" title="Search Query"> </div> <div class=searchsubmit> <input type=submit value="Search" name=go> </div> <div class=hints> <span class=hints><a href="/hints.html">Hints</a></span> </div> </div> <div class=searchgreet> (Greetings from <a href="/welcome">The On-Line Encyclopedia of Integer Sequences</a>!) </div> </div> </form> </div> <div class=sequence> <div class=space1></div> <div class=line></div> <div class=seqhead> <div class=seqnumname> <div class=seqnum> A000123 </div> <div class=seqname> Number of binary partitions: number of partitions of 2n into powers of 2. <br><font size=-1>(Formerly M1011 N0378)</font> </div> </div> <div class=scorerefs> 109 </div> </div> <div> <div class=seqdatabox> <div class=seqdata>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</div> <div class=seqdatalinks> (<a href="/A000123/list">list</a>; <a href="/A000123/graph">graph</a>; <a href="/search?q=A000123+-id:A000123">refs</a>; <a href="/A000123/listen">listen</a>; <a href="/history?seq=A000123">history</a>; <a href="/search?q=id:A000123&fmt=text">text</a>; <a href="/A000123/internal">internal format</a>) </div> </div> </div> <div class=entry> <div class=section> <div class=sectname>OFFSET</div> <div class=sectbody> <div class=sectline>0,2</div> </div> </div> <div class=section> <div class=sectname>COMMENTS</div> <div class=sectbody> <div class=sectline>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].</div> <div class=sectline>Row sums of <a href="/A101566" title="Binary partition sequence matrix.">A101566</a>. - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Jan 03 2005</div> <div class=sectline>Equals infinite convolution product of [1,2,2,2,2,2,2,2,2] aerated <a href="/A000079" title="Powers of 2: a(n) = 2^n.">A000079</a> - 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]. - <a href="/wiki/User:Mats_Granvik">Mats Granvik</a> and <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Aug 04 2009</div> <div class=sectline>Which can be further decomposed to the infinite convolution product of finally supported sequences, namely [1,1] aerated <a href="/A000079" title="Powers of 2: a(n) = 2^n.">A000079</a> - 1 times with multiplicity <a href="/A000027" title="The positive integers. Also called the natural numbers, the whole numbers or the counting numbers, but these terms are ambig...">A000027</a> + 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.). - <a href="/wiki/User:Eitan_Y._Levine">Eitan Y. Levine</a>, Jun 18 2023</div> <div class=sectline>Given <a href="/A018819" title="Binary partition function: number of partitions of n into powers of 2.">A018819</a> = <a href="/A000123" title="Number of binary partitions: number of partitions of 2n into powers of 2.">A000123</a> 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, ...). - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Dec 16 2009</div> <div class=sectline>Let M = an infinite lower triangular matrix with (1, 2, 2, 2, ...) in every column shifted down twice. <a href="/A000123" title="Number of binary partitions: number of partitions of 2n into powers of 2.">A000123</a> = 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 <a href="/A171370" title="Sequence generated from Lim:_{n..inf.} M^n, M = an infinite lower triangular matrix with (1,3,3,3,...) in every column, shif...">A171370</a>: (1, 3, 6, 12, 18, 30, 42, 66, 84, 120, ...). - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Dec 06 2009</div> <div class=sectline>First differences of the sequence are (1, 2, 2, 4, 4, 6, 6, 10, ...), <a href="/A018819" title="Binary partition function: number of partitions of n into powers of 2.">A018819</a>, 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. - <a href="/wiki/User:M._F._Hasler">M. F. Hasler</a>, Feb 19 2019</div> <div class=sectline>Sum over k <= n of number of partitions of k into powers of 2, <a href="/A018819" title="Binary partition function: number of partitions of n into powers of 2.">A018819</a>. - <a href="/wiki/User:Peter_Munn">Peter Munn</a>, Feb 21 2020</div> </div> </div> <div class=section> <div class=sectname>REFERENCES</div> <div class=sectbody> <div class=sectline>G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976.</div> <div class=sectline>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.</div> <div class=sectline>N. G. de Bruijn, On Mahler's partition problem, Indagationes Mathematicae, vol. X (1948), 210-220.</div> <div class=sectline>G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.</div> <div class=sectline>H. Gupta, A simple proof of the Churchhouse conjecture concerning binary partitions, Indian J. Pure Appl. Math. 3 (1972), 791-794.</div> <div class=sectline>H. Gupta, A direct proof of the Churchhouse conjecture concerning binary partitions, Indian J. Math. 18 (1976), 1-5.</div> <div class=sectline>N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).</div> <div class=sectline>N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).</div> </div> </div> <div class=section> <div class=sectname>LINKS</div> <div class=sectbody> <div class=sectline>Alois P. Heinz, <a href="/A000123/b000123.txt">Table of n, a(n) for n = 0..65536</a> (first 10001 terms from T. D. Noe)</div> <div class=sectline>Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 728</div> <div class=sectline>C. Banderier, H.-K. Hwang, V. Ravelomanana and V. Zacharovas, <a href="http://140.109.74.92/hk/wp-content/files/2012/07/mis-n-to-the-logn.pdf">Analysis of an exhaustive search algorithm in random graphs and the n^{c logn}-asymptotics</a>, 2012. - From <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Dec 23 2012</div> <div class=sectline>Sara Billey, Matjaž Konvalinka and Frederick A. Matsen IV, <a href="https://hal.archives-ouvertes.fr/hal-02173394">On trees, tanglegrams, and tangled chains</a>, hal-02173394 [math.CO], 2020.</div> <div class=sectline>Henry Bottomley, <a href="/A000123/a000123.gif">Illustration of initial terms</a></div> <div class=sectline>N. G. de Bruijn, <a href="http://www.dwc.knaw.nl/DL/publications/PU00018536.pdf">On Mahler's partition problem</a>, 1948.</div> <div class=sectline>R. F. Churchhouse, <a href="http://dx.doi.org/10.1017/S0305004100045072">Congruence properties of the binary partition function</a>, Proc. Cambridge Philos. Soc. 66 1969 371-376.</div> <div class=sectline>Philippe Deléham, <a href="/A033485/a033485.pdf">Letter to N. J. A. Sloane, Apr 20 1998</a></div> <div class=sectline>P. Dumas and P. Flajolet, <a href="http://jtnb.cedram.org/item?id=JTNB_1996__8_1_1_0">Asymptotique des recurrences mahleriennes: le cas cyclotomique</a>, Journal de Théorie des Nombres de Bordeaux 8 (1996), pp. 1-30.</div> <div class=sectline>Amanda Folsom et al, <a href="http://dx.doi.org/10.1016/j.disc.2015.12.019">On a general class of non-squashing partitions</a>, Discrete Mathematics 339.5 (2016): 1482-1506.</div> <div class=sectline>C.-E. Froberg, <a href="http://dx.doi.org/10.1007/BF01933448">Accurate estimation of the number of binary partitions</a>, Nordisk Tidskr. Informationsbehandling (BIT) 17 (1977), 386-391.</div> <div class=sectline>C.-E. Froberg, <a href="/A000123/a000123.pdf">Accurate estimation of the number of binary partitions</a> [Annotated scanned copy]</div> <div class=sectline>Maciej Gawron, Piotr Miska and Maciej Ulas, <a href="https://arxiv.org/abs/1703.01955">Arithmetic properties of coefficients of power series expansion of Prod_{n>=0} (1-x^(2^n))^t</a>, arXiv:1703.01955 [math.NT], 2017.</div> <div class=sectline>H. Gupta, <a href="http://dx.doi.org/10.1017/S0305004100049665">Proof of the Churchhouse conjecture concerning binary partitions</a>, Proc. Camb. Phil. Soc. 70 (1971), 53-56.</div> <div class=sectline>R. K. Guy, <a href="/A000123/a000123_1.pdf">Letters to N. J. A. Sloane and J. W. Moon, 1988</a></div> <div class=sectline>M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions, <a href="https://ajc.maths.uq.edu.au/pdf/30/ajc_v30_p193.pdf">Australasian J. Combin.</a>, 30 (2004), 193-196.</div> <div class=sectline>M. D. Hirschhorn and J. A. Sellers, <a href="http://www.math.psu.edu/sellersj/mike-m-ary.pdf">A different view of m-ary partitions</a></div> <div class=sectline>Youkow Homma, Jun Hwan Ryu and Benjamin Tong, <a href="http://sumry.yale.edu/sites/default/files/files/Sequence_nonsquashing_partitions.pdf">Sequence non-squashing partitions</a>, Slides from a talk, Jul 24 2014.</div> <div class=sectline>K. Ji and H. S. Wilf, <a href="http://www.jstor.org/stable/27642506">Extreme palindromes</a>, Amer. Math. Monthly, 115, no. 5 (2008), 447-451.</div> <div class=sectline>Y. Kachi and P. Tzermias, <a href="http://mi.mathnet.ru/adm508">On the m-ary partition numbers</a>, Algebra and Discrete Mathematics, Volume 19 (2015). Number 1, pp. 67-76.</div> <div class=sectline>Martin Klazar, <a href="http://arxiv.org/abs/1808.08449">What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I</a>, arXiv:1808.08449 [math.CO], 2018.</div> <div class=sectline>D. E. Knuth, <a href="http://www.fq.math.ca/Scanned/4-2/knuth.pdf">An almost linear recurrence</a>, Fib. Quart., 4 (1966), 117-128.</div> <div class=sectline>M. Konvalinka and I. Pak, <a href="http://www.math.ucla.edu/~pak/papers/CayleyComp7.pdf">Cayley compositions, partitions, polytopes, and geometric bijections</a> - <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Dec 22 2012</div> <div class=sectline>M. Konvalinka and I. Pak, <a href="https://doi.org/10.1016/j.jcta.2013.11.008">Cayley compositions, partitions, polytopes, and geometric bijections</a>, Journal of Combinatorial Theory, Series A, Volume 123, Issue 1, April 2014, Pages 86-91.</div> <div class=sectline>Vaclav Kotesovec, <a href="/A000123/a000123_2.pdf">Graph - the asymptotic ratio (10^8 terms)</a></div> <div class=sectline>M. Latapy, <a href="https://doi.org/10.46298/dmtcs.2279">Partitions of an integer into powers</a>, DMTCS Proceedings AA (DM-CCG), 2001, 215-228.</div> <div class=sectline>M. Latapy, <a href="/A005706/a005706.pdf">Partitions of an integer into powers</a>, DMTCS Proceedings AA (DM-CCG), 2001, 215-228. [Cached copy, with permission]</div> <div class=sectline>K. Mahler, <a href="https://doi.org/10.1112/jlms/s1-15.2.115">On a special functional equation</a>, Journ. London Math. Soc. 15 (1940), 115-123.</div> <div class=sectline>E. O'Shea, <a href="http://dx.doi.org/10.1016/j.disc.2004.07.016">M-partitions: optimal partitions of weight for one scale pan</a>, Discrete Math. 289 (2004), 81-93. See Lemma 29.</div> <div class=sectline>Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.</div> <div class=sectline>John L. Pfaltz, <a href="http://virginia.edu/~jlp/partition.ps">Evaluating the binary partition function when N = 2^n</a>, Congr. Numer, 109:3-12, 1995. [Broken link]</div> <div class=sectline>B. Reznick, <a href="http://dx.doi.org/10.1007/978-1-4612-3464-7_29">Some binary partition functions</a>, in "Analytic number theory" (Conf. in honor P. T. Bateman, Allerton Park, IL, 1989), 451-477, Progr. Math., 85, Birkhäuser Boston, Boston, MA, 1990.</div> <div class=sectline>O. J. Rodseth, <a href="http://dx.doi.org/10.1016/j.disc.2006.02.010">Enumeration of M-partitions</a>, Discrete Math., 306 (2006), 694-698.</div> <div class=sectline>O. J. Rodseth and J. A. Sellers, <a href="http://dx.doi.org/10.1006/jcta.2001.3223">Binary partitions revisited</a>, J. Combinatorial Theory, Series A 98 (2002), 33-45.</div> <div class=sectline>O. J. Rodseth and J. A. Sellers, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Sellers/sellers75.html">On a Restricted m-Non-Squashing Partition Function</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.</div> <div class=sectline>D. Ruelle, <a href="http://www.ams.org/notices/200208/fea-ruelle.pdf">Dynamical zeta functions and transfer operators</a>, Notices Amer. Math. Soc., 49 (No. 8, 2002), 887-895; see p. 888.</div> <div class=sectline>F. Ruskey, <a href="https://web.archive.org/web/20170508233132/theory.cs.uvic.ca/inf/nump/BinaryPartition.html">Info on binary partitions</a></div> <div class=sectline>N. J. A. Sloane and J. A. Sellers, <a href="https://arxiv.org/abs/math/0312418">On non-squashing partitions</a>, arXiv:math/0312418 [math.CO], 2003.</div> <div class=sectline>N. J. A. Sloane and J. A. Sellers, <a href="https://doi.org/10.1016/j.disc.2004.11.014">On non-squashing partitions</a>, Discrete Math., 294 (2005), 259-274.</div> <div class=sectline>Daniel G. Zhu, <a href="https://arxiv.org/abs/2402.10025">An improved lower bound on the Shannon capacities of complements of odd cycles</a>, arXiv:2402.10025 [math.CO], 2024.</div> <div class=sectline><a href="/index/Cor#core">Index entries for "core" sequences</a></div> </div> </div> <div class=section> <div class=sectname>FORMULA</div> <div class=sectbody> <div class=sectline>a(n) = <a href="/A018819" title="Binary partition function: number of partitions of n into powers of 2.">A018819</a>(2*n).</div> <div class=sectline>a(n) = a(n-1) + a(floor(n/2)). For proof see <a href="/A018819" title="Binary partition function: number of partitions of n into powers of 2.">A018819</a>.</div> <div class=sectline>2 * a(n) = a(n+1) + a(n-1) if n is even. - <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Jan 07 2011</div> <div class=sectline>G.f.: (1-x)^(-1) Product_{n>=0} (1 - x^(2^n))^(-1).</div> <div class=sectline>a(n) = Sum_{i=0..n} a(floor(i/2)) [O'Shea].</div> <div class=sectline>a(n) = (1/n)*Sum_{k=1..n} (<a href="/A038712" title="Let k be the exponent of highest power of 2 dividing n (A007814); a(n) = 2^(k+1)-1.">A038712</a>(k)+1)*a(n-k), n > 1, a(0)=1. - <a href="/wiki/User:Vladeta_Jovovic">Vladeta Jovovic</a>, Aug 22 2002</div> <div class=sectline>Conjecture: Limit_{n ->infinity} (log(n)*a(2n))/(n*a(n)) = c = 1.63... - <a href="/wiki/User:Benoit_Cloitre">Benoit Cloitre</a>, Jan 26 2003 [The constant c is equal to 2*log(2) = 1.38629436... =<a href="/A016627" title="Decimal expansion of log(4).">A016627</a>. - <a href="/wiki/User:Vaclav_Kotesovec">Vaclav Kotesovec</a>, Aug 07 2019]</div> <div class=sectline>G.f. A(x) satisfies A(x^2) = ((1-x)/(1+x)) * A(x). - <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Aug 25 2003</div> <div class=sectline>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). - <a href="/wiki/User:Joerg_Arndt">Joerg Arndt</a>, Apr 24 2005</div> <div class=sectline>From <a href="/wiki/User:Philippe_Flajolet">Philippe Flajolet</a>, Sep 06 2008: (Start)</div> <div class=sectline>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.</div> <div class=sectline>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)</div> <div class=sectline>G.f.: exp( Sum_{n>=1} 2^<a href="/A001511" title="The ruler function: exponent of the highest power of 2 dividing 2n. Equivalently, the 2-adic valuation of 2n.">A001511</a>(n) * x^n/n ), where 2^<a href="/A001511" title="The ruler function: exponent of the highest power of 2 dividing 2n. Equivalently, the 2-adic valuation of 2n.">A001511</a>(n) is the highest power of 2 that divides 2*n. - <a href="/wiki/User:Paul_D._Hanna">Paul D. Hanna</a>, Oct 30 2012</div> <div class=sectline>(n/2)*a(n) = Sum_{k = 0..n-1} (n-k)/<a href="/A000265" title="Remove all factors of 2 from n; or largest odd divisor of n; or odd part of n.">A000265</a>(n-k)*a(k). - <a href="/wiki/User:Peter_Bala">Peter Bala</a>, Mar 03 2019</div> </div> </div> <div class=section> <div class=sectname>EXAMPLE</div> <div class=sectbody> <div class=sectline>For non-squashing partitions and binary partitions see the example in <a href="/A018819" title="Binary partition function: number of partitions of n into powers of 2.">A018819</a>.</div> <div class=sectline>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. - <a href="/wiki/User:R._J._Mathar">R. J. Mathar</a>, Aug 11 2021</div> </div> </div> <div class=section> <div class=sectname>MAPLE</div> <div class=sectbody> <div class=sectline><a href="/A000123" title="Number of binary partitions: number of partitions of 2n into powers of 2.">A000123</a> := proc(n) option remember; if n=0 then 1 else <a href="/A000123" title="Number of binary partitions: number of partitions of 2n into powers of 2.">A000123</a>(n-1)+<a href="/A000123" title="Number of binary partitions: number of partitions of 2n into powers of 2.">A000123</a>(floor(n/2)); fi; end; [ seq(<a href="/A000123" title="Number of binary partitions: number of partitions of 2n into powers of 2.">A000123</a>(i), i=0..50) ];</div> <div class=sectline># second Maple program: more efficient for large n; try: a( 10^25 );</div> <div class=sectline>g:= proc(b, n) option remember; `if`(b<0, 0, `if`(b=0 or</div> <div class=sectline> n=0, 1, `if`(b>=n, add((-1)^(t+1)*binomial(n+1, t)</div> <div class=sectline> *g(b-t, n), t=1..n+1), g(b-1, n)+g(2*b, n-1))))</div> <div class=sectline> end:</div> <div class=sectline>a:= n-> (t-> g(n/2^(t-1), t))(max(ilog2(2*n), 1)):</div> <div class=sectline>seq(a(n), n=0..60); # <a href="/wiki/User:Alois_P._Heinz">Alois P. Heinz</a>, Apr 16 2009, revised Apr 14 2016</div> </div> </div> <div class=section> <div class=sectname>MATHEMATICA</div> <div class=sectbody> <div class=sectline>a[0] = 1; a[n_] := a[n] = a[Floor[n/2]] + a[n-1]; Array[a, 49, 0] (* <a href="/wiki/User:Jean-François_Alcover">Jean-François Alcover</a>, Apr 11 2011, after <a href="/wiki/User:M._F._Hasler">M. F. Hasler</a> *)</div> <div class=sectline>Fold[Append[#1, Total[Take[Flatten[Transpose[{#1, #1}]], #2]]] &, {1}, Range[2, 49]] (* <a href="/wiki/User:Birkas_Gyorgy">Birkas Gyorgy</a>, Apr 18 2011 *)</div> </div> </div> <div class=section> <div class=sectname>PROG</div> <div class=sectbody> <div class=sectline>(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))}; /* <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Aug 25 2003 */</div> <div class=sectline>(PARI) {a(n) = if( n<1, n==0, a(n\2) + a(n-1))}; /* <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Aug 25 2003 */</div> <div class=sectline>(PARI) A123=[]; <a href="/A000123" title="Number of binary partitions: number of partitions of 2n into powers of 2.">A000123</a>(n)={ n<3 && return(2^n); if( n<=#A123, A123[n] && return(A123[n]); A123[n-1] && return( A123[n] = A123[n-1]+<a href="/A000123" title="Number of binary partitions: number of partitions of 2n into powers of 2.">A000123</a>(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, <a href="/A000123" title="Number of binary partitions: number of partitions of 2n into powers of 2.">A000123</a>(k), 1)+(n%2+1)*<a href="/A000123" title="Number of binary partitions: number of partitions of 2n into powers of 2.">A000123</a>(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. - <a href="/wiki/User:M._F._Hasler">M. F. Hasler</a>, Apr 30 2009</div> <div class=sectline>(PARI) {a(n)=polcoeff(exp(sum(m=1, n, 2^valuation(2*m, 2)*x^m/m)+x*O(x^n)), n)} \\ <a href="/wiki/User:Paul_D._Hanna">Paul D. Hanna</a>, Oct 30 2012</div> <div class=sectline>(Haskell)</div> <div class=sectline>import Data.List (transpose)</div> <div class=sectline>a000123 n = a000123_list !! n</div> <div class=sectline>a000123_list = 1 : zipWith (+)</div> <div class=sectline> a000123_list (tail $ concat $ transpose [a000123_list, a000123_list])</div> <div class=sectline>-- <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Nov 15 2012, Aug 01 2011</div> <div class=sectline>(Magma) [1] cat [n eq 1 select n+1 else Self(n-1) + Self(n div 2): n in [1..70]]; // <a href="/wiki/User:Vincenzo_Librandi">Vincenzo Librandi</a>, Dec 17 2016</div> <div class=sectline>(Python)</div> <div class=sectline>from functools import lru_cache</div> <div class=sectline>@lru_cache(maxsize=None)</div> <div class=sectline>def <a href="/A000123" title="Number of binary partitions: number of partitions of 2n into powers of 2.">A000123</a>(n): return 1 if n == 0 else <a href="/A000123" title="Number of binary partitions: number of partitions of 2n into powers of 2.">A000123</a>(n-1) + <a href="/A000123" title="Number of binary partitions: number of partitions of 2n into powers of 2.">A000123</a>(n//2) # <a href="/wiki/User:Chai_Wah_Wu">Chai Wah Wu</a>, Jan 18 2022</div> </div> </div> <div class=section> <div class=sectname>CROSSREFS</div> <div class=sectbody> <div class=sectline>Cf. <a href="/A000041" title="a(n) is the number of partitions of n (the partition numbers).">A000041</a>, <a href="/A002033" title="Number of perfect partitions of n.">A002033</a>, <a href="/A002487" title="Stern's diatomic series (or Stern-Brocot sequence): a(0) = 0, a(1) = 1; for n > 0: a(2*n) = a(n), a(2*n+1) = a(n) + a(n+1).">A002487</a>, <a href="/A002577" title="Number of partitions of 2^n into powers of 2.">A002577</a>, <a href="/A005704" title="Number of partitions of 3n into powers of 3.">A005704</a>-<a href="/A005706" title="Number of partitions of 5n into powers of 5.">A005706</a>, <a href="/A023359" title="Number of compositions (ordered partitions) of n into powers of 2.">A023359</a>, <a href="/A040039" title="First differences of A033485; also A033485 with terms repeated.">A040039</a>, <a href="/A100529" title="a(n) = minimal k such that n has a partition into k parts with the property that every number <= m can be partitioned into a...">A100529</a>. Partial sums and bisection of <a href="/A018819" title="Binary partition function: number of partitions of n into powers of 2.">A018819</a>.</div> <div class=sectline>A column of <a href="/A072170" title="Square array T(n,k) (n >= 0, k >= 2) read by antidiagonals, where T(n,k) is the number of ways of writing n as Sum_{i>=0} c_...">A072170</a>. Row sums of <a href="/A089177" title="Triangle read by rows: T(n,k) (n >= 0, 0 <= k <= 1+log_2(floor(n))) giving number of non-squashing partitions of n into k parts.">A089177</a>. Twice <a href="/A033485" title="a(n) = a(n-1) + a(floor(n/2)), a(1) = 1.">A033485</a>.</div> <div class=sectline>Cf. <a href="/A145515" title="Square array A(n,k), n>=0, k>=0, read by antidiagonals: A(n,k) is the number of partitions of k^n into powers of k.">A145515</a>. - <a href="/wiki/User:Alois_P._Heinz">Alois P. Heinz</a>, Apr 16 2009</div> <div class=sectline>Cf. <a href="/A171370" title="Sequence generated from Lim:_{n..inf.} M^n, M = an infinite lower triangular matrix with (1,3,3,3,...) in every column, shif...">A171370</a>. - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Dec 06 2009</div> <div class=sectline>Sequence in context: <a href="/A322003" title="Indices where A028897(A322000(n)) increases. Partial sums of A072170(n,10).">A322003</a> <a href="/A088932" title="G.f.: 1/((1-x)^2*(1-x^2)*(1-x^4)*(1-x^8)).">A088932</a> <a href="/A088954" title="G.f.: 1/((1-x)^2*(1-x^2)*(1-x^4)*(1-x^8)*(1-x^16)).">A088954</a> * <a href="/A268752" title="Cubefree numbers n such that n^2 + 1 is prime.">A268752</a> <a href="/A277277" title="Number of overpal-free binary words of length n.">A277277</a> <a href="/A241337" title="Number of partitions p of n not including ceiling(mean(p)) as a part.">A241337</a></div> <div class=sectline>Adjacent sequences: <a href="/A000120" title="1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n).">A000120</a> <a href="/A000121" title="Number of representations of n as a sum of Fibonacci numbers (1 is allowed twice as a part).">A000121</a> <a href="/A000122" title="Expansion of Jacobi theta function theta_3(x) = Sum_{m =-oo..oo} x^(m^2) (number of integer solutions to k^2 = n).">A000122</a> * <a href="/A000124" title="Central polygonal numbers (the Lazy Caterer's sequence): n(n+1)/2 + 1; or, maximal number of pieces formed when slicing a pa...">A000124</a> <a href="/A000125" title="Cake numbers: maximal number of pieces resulting from n planar cuts through a cube (or cake): C(n+1,3) + n + 1.">A000125</a> <a href="/A000126" title="A nonlinear binomial sum.">A000126</a></div> </div> </div> <div class=section> <div class=sectname>KEYWORD</div> <div class=sectbody> <div class=sectline><span title="a sequence of nonnegative numbers">nonn</span>,<span title="it is very easy to produce terms of sequence">easy</span>,<span title="an important sequence">core</span>,<span title="an exceptionally nice sequence">nice</span></div> </div> </div> <div class=section> <div class=sectname>AUTHOR</div> <div class=sectbody> <div class=sectline><a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a></div> </div> </div> <div class=section> <div class=sectname>EXTENSIONS</div> <div class=sectbody> <div class=sectline>More terms from Robin Trew (trew(AT)hcs.harvard.edu)</div> <div class=sectline>Values up to a(10^4) checked with given PARI code by <a href="/wiki/User:M._F._Hasler">M. F. Hasler</a>, Apr 30 2009</div> </div> </div> <div class=section> <div class=sectname>STATUS</div> <div class=sectbody> <div class=sectline>approved</div> </div> </div> </div> <div class=space10></div> </div> </div></div> <p> <div class=footerpad></div> <div class=footer> <center> <div class=bottom> <div class=linksbar> <a href="/">Lookup</a> <a href="/wiki/Welcome"><font color="red">Welcome</font></a> <a href="/wiki/Main_Page"><font color="red">Wiki</font></a> <a href="/wiki/Special:RequestAccount">Register</a> <a href="/play.html">Music</a> <a href="/plot2.html">Plot 2</a> <a href="/demo1.html">Demos</a> <a href="/wiki/Index_to_OEIS">Index</a> <a href="/webcam">WebCam</a> <a href="/Submit.html">Contribute</a> <a href="/eishelp2.html">Format</a> <a href="/wiki/Style_Sheet">Style Sheet</a> <a href="/transforms.html">Transforms</a> <a href="/ol.html">Superseeker</a> <a href="/recent">Recents</a> </div> <div class=linksbar> <a href="/community.html">The OEIS Community</a> </div> <div class=linksbar> Maintained by <a href="http://oeisf.org">The OEIS Foundation Inc.</a> </div> <div class=dbinfo>Last modified November 28 20:56 EST 2024. Contains 378208 sequences.</div> <div class=legal> <a href="/wiki/Legal_Documents">License Agreements, Terms of Use, Privacy Policy</a> </div> </div> </center> </div> </body> </html>