0,2

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 (pbarry(AT)wit.ie), 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]. [From Mats Granvik, Gary W. Adamson (mats.granvik(AT)abo.fi), Aug 04 2009]

G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976.

N. G. de Bruijn, On Mahler's partition problem, Indagationes Mathematicae, vol. X (1948), 210-220.

R. F. Churchhouse, Congruence properties of the binary partition function. Proc. Cambridge Philos. Soc. 66 1969 371-376.

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.

G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.

C.-E. Froberg, Accurate estimation of the number of binary partitions, Nordisk Tidskr. Informationsbehandling (BIT) 17 (1977), 386-391.

H. Gupta, Proof of the Churchhouse conjecture concerning binary partitions, Proc. Camb. Phil. Soc. 70 (1971), 53-56.

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.

K. Ji and H. S. Wilf, Extreme palindromes, Amer. Math. Monthly, 115, no. 5 (2008), 447-451.

D. E. Knuth, An almost linear recurrence, Fib. Quart., 4 (1966), 117-128.

K. Mahler, On a special functional equation, Journ. London Math. Soc. 15 (1940), 115-123.

E. O'Shea, M-partitions: optimal partitions of weight for one scale pan, Discrete Math. 289 (2004), 81-93. See Lemma 29.

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.

O. J. Rodseth, Enumeration of M-partitions, Discrete Math., 306 (2006), 694-698.

O. J. Rodseth and J. A. Sellers, Binary partitions revisited, J. Combinatorial Theory, Series A 98 (2002), 33-45.

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. Ruelle, Dynamical zeta functions and transfer operators, Notices Amer. Math. Soc., 49 (No. 8, 2002), 887-895; see p. 888.

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

T. D. Noe, Table of n, a(n) for n = 0..10000

Joerg Arndt, Fxtbook

H. Bottomley, Illustration of initial terms

P. Dumas and P. Flajolet, Asymptotique des recurrences mahleriennes: le cas cyclotomique, Journal de Theorie des Nombres de Bordeaux 8 (1996), pp. 1-30.

M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions, Australasian J. Combin., 30 (2004), 193-196.

M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions

M. Latapy, Partitions of an integer into powers, DMTCS Proceedings AA (DM-CCG), 2001, 215-228.

John L. Pfaltz, Evaluating the binary partition function when N = 2^n, Congr. Numer, 109:3-12, 1995.

F. Ruskey, Info on binary partitions

N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.

Index entries for "core" sequences

a(n)=a(n-1)+a([n/2]). For proof see A018819.

G.f.: (1-x)^(-1) Product_{n=0..inf} (1 - x^(2^n))^(-1).

a(n) = Sum_{i=0..n} a([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 (vladeta(AT)eunet.rs), Aug 22 2002

Conjecture: lim n ->infinity (log(n)*a(2n))/(n*a(n)) = c = 1.63... - Benoit Cloitre (benoit7848c(AT)orange.fr), Jan 26 2003

G.f. A(x) satisfies A(x^2)=((1-x)/(1+x))A(x). - Michael Somos, Aug 25 2003

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

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:

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)

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) ];

Contribution from Alois P. Heinz (heinz(AT)hs-heilbronn.de), Apr 16 2009: (Start)

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);

## more efficient for large n; try: a( 10^14 ); ## (End)

(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))

(PARI) a(n)=if(n<1, n==0, a(n\2)+a(n-1))

(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]

Cf. A000041, A002577, A005704, A005705, A005706, A018819, A023359, A040039, A002487.

A column of A072170. Row sums of A089177. Twice A033485.

Cf. A002033, A100529.

Cf. A145515. [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Apr 16 2009]

Sequence in context: A001307 A088932 A088954 this_sequence A103257 A103259 A082380

Adjacent sequences: A000120 A000121 A000122 this_sequence A000124 A000125 A000126

nonn,easy,core,nice

N. J. A. Sloane (njas(AT)research.att.com).

More terms from Robin Trew (trew(AT)hcs.harvard.edu).

Values up to a(10^4) checked with given PARI code. [From M. F. Hasler (MHasler(AT)univ-ag.fr), Apr 30 2009]