# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a000123
Showing 1-1 of 1

%I A000123 M1011 N0378 #262 Jan 05 2025 19:51:30
%S A000123 1,2,4,6,10,14,20,26,36,46,60,74,94,114,140,166,202,238,284,330,390,
%T A000123 450,524,598,692,786,900,1014,1154,1294,1460,1626,1828,2030,2268,2506,
%U A000123 2790,3074,3404,3734,4124,4514,4964,5414,5938,6462,7060,7658,8350,9042,9828
%N A000123 Number of binary partitions: number of partitions of 2n into powers of 2.
%C A000123 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].
%C A000123 Row sums of A101566. - _Paul Barry_, Jan 03 2005
%C A000123 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
%C A000123 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
%C A000123 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
%C A000123 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
%C A000123 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
%C A000123 Sum over k <= n of number of partitions of k into powers of 2, A018819. - _Peter Munn_, Feb 21 2020
%D A000123 G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976.
%D A000123 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.
%D A000123 N. G. de Bruijn, On Mahler's partition problem, Indagationes Mathematicae, vol. X (1948), 210-220.
%D A000123 G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
%D A000123 H. Gupta, A simple proof of the Churchhouse conjecture concerning binary partitions, Indian J. Pure Appl. Math. 3 (1972), 791-794.
%D A000123 H. Gupta, A direct proof of the Churchhouse conjecture concerning binary partitions, Indian J. Math. 18 (1976), 1-5.
%D A000123 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000123 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000123 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)
%H A000123 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 728
%H A000123 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 _N. J. A. Sloane_, Dec 23 2012
%H A000123 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.
%H A000123 Henry Bottomley, <a href="/A000123/a000123.gif">Illustration of initial terms</a>
%H A000123 N. G. de Bruijn, <a href="http://www.dwc.knaw.nl/DL/publications/PU00018536.pdf">On Mahler's partition problem</a>, 1948.
%H A000123 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.
%H A000123 Philippe Deléham, <a href="/A033485/a033485.pdf">Letter to N. J. A. Sloane, Apr 20 1998</a>
%H A000123 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.
%H A000123 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.
%H A000123 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.
%H A000123 C.-E. Froberg, <a href="/A000123/a000123.pdf">Accurate estimation of the number of binary partitions</a> [Annotated scanned copy]
%H A000123 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.
%H A000123 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.
%H A000123 R. K. Guy, <a href="/A000123/a000123_1.pdf">Letters to N. J. A. Sloane and J. W. Moon, 1988</a>
%H A000123 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.
%H A000123 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>
%H A000123 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.
%H A000123 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.
%H A000123 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.
%H A000123 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.
%H A000123 D. E. Knuth, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/4-2/knuth.pdf">An almost linear recurrence</a>, Fib. Quart., 4 (1966), 117-128.
%H A000123 M. Konvalinka and I. Pak, <a href="http://www.math.ucla.edu/~pak/papers/CayleyComp7.pdf">Cayley compositions, partitions, polytopes, and geometric bijections</a> - _N. J. A. Sloane_, Dec 22 2012
%H A000123 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.
%H A000123 Vaclav Kotesovec, <a href="/A000123/a000123_2.pdf">Graph - the asymptotic ratio (10^8 terms)</a>
%H A000123 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.
%H A000123 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]
%H A000123 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.
%H A000123 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.
%H A000123 Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.
%H A000123 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]
%H A000123 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.
%H A000123 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.
%H A000123 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.
%H A000123 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.
%H A000123 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.
%H A000123 F. Ruskey, <a href="https://web.archive.org/web/20170508233132/theory.cs.uvic.ca/inf/nump/BinaryPartition.html">Info on binary partitions</a>
%H A000123 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.
%H A000123 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.
%H A000123 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.
%H A000123 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A000123 a(n) = A018819(2*n).
%F A000123 a(n) = a(n-1) + a(floor(n/2)). For proof see A018819.
%F A000123 2 * a(n) = a(n+1) + a(n-1) if n is even. - _Michael Somos_, Jan 07 2011
%F A000123 G.f.: (1-x)^(-1) Product_{n>=0} (1 - x^(2^n))^(-1).
%F A000123 a(n) = Sum_{i=0..n} a(floor(i/2)) [O'Shea].
%F A000123 a(n) = (1/n)*Sum_{k=1..n} (A038712(k)+1)*a(n-k), n > 1, a(0)=1. - _Vladeta Jovovic_, Aug 22 2002
%F A000123 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]
%F A000123 G.f. A(x) satisfies A(x^2) = ((1-x)/(1+x)) * A(x). - _Michael Somos_, Aug 25 2003
%F A000123 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
%F A000123 From _Philippe Flajolet_, Sep 06 2008: (Start)
%F A000123 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.
%F A000123 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)
%F A000123 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
%F A000123 (n/2)*a(n) = Sum_{k = 0..n-1} (n-k)/A000265(n-k)*a(k). - _Peter Bala_, Mar 03 2019
%e A000123 For non-squashing partitions and binary partitions see the example in A018819.
%e A000123 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
%p A000123 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) ];
%p A000123 # second Maple program: more efficient for large n; try: a( 10^25 );
%p A000123 g:= proc(b, n) option remember; `if`(b<0, 0, `if`(b=0 or
%p A000123       n=0, 1, `if`(b>=n, add((-1)^(t+1)*binomial(n+1, t)
%p A000123       *g(b-t, n), t=1..n+1), g(b-1, n)+g(2*b, n-1))))
%p A000123     end:
%p A000123 a:= n-> (t-> g(n/2^(t-1), t))(max(ilog2(2*n), 1)):
%p A000123 seq(a(n), n=0..60); # _Alois P. Heinz_, Apr 16 2009, revised Apr 14 2016
%t A000123 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_ *)
%t A000123 Fold[Append[#1, Total[Take[Flatten[Transpose[{#1, #1}]], #2]]] &, {1}, Range[2, 49]] (* _Birkas Gyorgy_, Apr 18 2011 *)
%o A000123 (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 */
%o A000123 (PARI) {a(n) = if( n<1, n==0, a(n\2) + a(n-1))}; /* _Michael Somos_, Aug 25 2003 */
%o A000123 (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
%o A000123 (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
%o A000123 (Haskell)
%o A000123 import Data.List (transpose)
%o A000123 a000123 n = a000123_list !! n
%o A000123 a000123_list = 1 : zipWith (+)
%o A000123    a000123_list (tail $ concat $ transpose [a000123_list, a000123_list])
%o A000123 -- _Reinhard Zumkeller_, Nov 15 2012, Aug 01 2011
%o A000123 (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
%o A000123 (Python)
%o A000123 from functools import lru_cache
%o A000123 @lru_cache(maxsize=None)
%o A000123 def A000123(n): return 1 if n == 0 else A000123(n-1) + A000123(n//2) # _Chai Wah Wu_, Jan 18 2022
%Y A000123 Cf. A000041, A002033, A002487, A002577, A005704-A005706, A023359, A040039, A100529. Partial sums and bisection of A018819.
%Y A000123 A column of A072170. Row sums of A089177. Twice A033485.
%Y A000123 Cf. A145515. - _Alois P. Heinz_, Apr 16 2009
%Y A000123 Cf. A171370. - _Gary W. Adamson_, Dec 06 2009
%K A000123 nonn,easy,core,nice
%O A000123 0,2
%A A000123 _N. J. A. Sloane_
%E A000123 More terms from Robin Trew (trew(AT)hcs.harvard.edu)
%E A000123 Values up to a(10^4) checked with given PARI code by _M. F. Hasler_, Apr 30 2009

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE