%I A000123 M1011 N0378
%S A000123 1,2,4,6,10,14,20,26,36,46,60,74,94,114,140,166,202,238,284,330,390,450,
%T A000123 524,598,692,786,900,1014,1154,1294,1460,1626,1828,2030,2268,2506,2790,
%U A000123 3074,3404,3734,4124,4514,4964,5414,5938,6462,7060,7658,8350,9042
%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 (pbarry(AT)wit.ie), 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]. [From Mats Granvik, Gary W. Adamson (mats.granvik(AT)abo.fi), 
               Aug 04 2009]
%D A000123 G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976.
%D A000123 N. G. de Bruijn, On Mahler's partition problem, Indagationes Mathematicae, 
               vol. X (1948), 210-220.
%D A000123 R. F. Churchhouse, Congruence properties of the binary partition function. 
               Proc. Cambridge Philos. Soc. 66 1969 371-376.
%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 G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence 
               Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
%D A000123 C.-E. Froberg, Accurate estimation of the number of binary partitions, 
               Nordisk Tidskr. Informationsbehandling (BIT) 17 (1977), 386-391.
%D A000123 H. Gupta, Proof of the Churchhouse conjecture concerning binary partitions, 
               Proc. Camb. Phil. Soc. 70 (1971), 53-56.
%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 K. Ji and H. S. Wilf, Extreme palindromes, Amer. Math. Monthly, 115, 
               no. 5 (2008), 447-451.
%D A000123 D. E. Knuth, An almost linear recurrence, Fib. Quart., 4 (1966), 117-128.
%D A000123 K. Mahler, On a special functional equation, Journ. London Math. Soc. 
               15 (1940), 115-123.
%D A000123 E. O'Shea, M-partitions: optimal partitions of weight for one scale pan, 
               Discrete Math. 289 (2004), 81-93. See Lemma 29.
%D A000123 B. Reznick, Some binary partition functions, in "Analytic number theory" 
               (Conf. in honor P. T. Bateman, Allerton Park, IL, 1989), 451-477, 
               Progr. Math., 85, Birkhaeuser Boston, Boston, MA, 1990.
%D A000123 O. J. Rodseth, Enumeration of M-partitions, Discrete Math., 306 (2006), 
               694-698.
%D A000123 O. J. Rodseth and J. A. Sellers, Binary partitions revisited, J. Combinatorial 
               Theory, Series A 98 (2002), 33-45.
%D A000123 O. J. Rodseth and J. A. Sellers, On a Restricted m-Non-Squashing Partition 
               Function, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.
%D A000123 D. Ruelle, Dynamical zeta functions and transfer operators, Notices Amer. 
               Math. Soc., 49 (No. 8, 2002), 887-895; see p. 888.
%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 T. D. Noe, <a href="b000123.txt">Table of n, a(n) for n = 0..10000</a>
%H A000123 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Fxtbook</a>
%H A000123 H. Bottomley, <a href="A000123.gif">Illustration of initial terms</a>
%H A000123 P. Dumas and P. Flajolet, <a href="http://algo.inria.fr/flajolet/Publications/
               publist.html">Asymptotique des recurrences mahleriennes: le cas cyclotomique</
               a>, Journal de Theorie des Nombres de Bordeaux 8 (1996), pp. 1-30.
%H A000123 M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions, 
               <a href="http://www.lacim.uqam.ca/~plouffe/OEIS/archive_in_pdf/mike-m-ary.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 M. Latapy, <a href="http://www.dmtcs.org/proceedings/">Partitions of 
               an integer into powers</a>, DMTCS Proceedings AA (DM-CCG), 2001, 
               215-228.
%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.
%H A000123 F. Ruskey, <a href="http://www.theory.cs.uvic.ca/~cos/inf/nump/BinaryPartition.html">
               Info on binary partitions</a>
%H A000123 N. J. A. Sloane and J. A. Sellers, <a href="http://arXiv.org/abs/math.CO/
               0312418">On non-squashing partitions</a>, Discrete Math., 294 (2005), 
               259-274.
%H A000123 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%F A000123 a(n)=a(n-1)+a([n/2]). For proof see A018819.
%F A000123 G.f.: (1-x)^(-1) Product_{n=0..inf} (1 - x^(2^n))^(-1).
%F A000123 a(n) = Sum_{i=0..n} a([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 (vladeta(AT)eunet.rs), Aug 22 2002
%F A000123 Conjecture: lim n ->infinity (log(n)*a(2n))/(n*a(n)) = c = 1.63... - 
               Benoit Cloitre (benoit7848c(AT)orange.fr), Jan 26 2003
%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.: prod(k=0, inf, (1+x^(2^k))/(1-x^(2^k)), or prod(k=0, inf, 1+x^(2^k))^(k+1))/
               (1-x), or prod(k=0, inf, (1+x^(2^k))^(k+2)) - Joerg Arndt (arndt(AT)jjj.de), 
               Apr 24 2005
%F A000123 Comment from Philippe Flajolet (Philippe.Flajolet(AT)inria.fr), 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:
%F A000123 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),
%F A000123 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)
%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 Contribution from Alois P. Heinz (heinz(AT)hs-heilbronn.de), Apr 16 2009: 
               (Start)
%p A000123 g:= proc(b, n) option remember; local t; if b<0 then 0 elif b=0 or n=0 
               then 1 elif b>=n then add (g(b-t, n) *binomial (n+1, t) *(-1)^(t+1), 
               t=1..n+1) else g(b-1, n) +g(2*b, n-1) fi end: a:= proc(n) local t; 
               t:= nops (convert (n, base, 2)); g(n /2^(t-1), t) end: seq (a(n), 
               n=0..60);
%p A000123 ## more efficient for large n; try: a( 10^14 ); ## (End)
%o A000123 (PARI) a(n)=local(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))
%o A000123 (PARI) a(n)=if(n<1,n==0,a(n\2)+a(n-1))
%o A000123 (PARI) a(n)={ n<3 & return(1<<n); if( n<=#A123, A123[n] & return(A123[n]); 
               A123[n-1] & return( A123[n] = A123[n-1]+a(n\2) ), n>2*#A123 & A123=vector(n\2)); 
               A123[ if(n<=#A123,n,1) ]=2*sum(k=1,n\2-1,a(k),1)+(n%2+1)*a(n\2) } 
               /* allocates a global vector A123 of size n/2. Gives a(n*10^6) in 
               ~ n sec */ [From M. F. Hasler (MHasler(AT)univ-ag.fr), Apr 30 2009]
%Y A000123 Cf. A000041, A002577, A005704, A005705, A005706, A018819, A023359, A040039, 
               A002487.
%Y A000123 A column of A072170. Row sums of A089177. Twice A033485.
%Y A000123 Cf. A002033, A100529.
%Y A000123 Cf. A145515. [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Apr 16 
               2009]
%Y A000123 Sequence in context: A001307 A088932 A088954 this_sequence A103257 A103259 
               A082380
%Y A000123 Adjacent sequences: A000120 A000121 A000122 this_sequence A000124 A000125 
               A000126
%K A000123 nonn,easy,core,nice
%O A000123 0,2
%A A000123 N. J. A. Sloane (njas(AT)research.att.com).
%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. [From M. F. Hasler 
               (MHasler(AT)univ-ag.fr), Apr 30 2009]