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]

It appears that the asymptotic rate of growth is not known exactly - see Froberg.

Row sums of A101566. - Paul Barry (pbarry(AT)wit.ie), Jan 03 2005

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

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.

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

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.

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

Joerg Arndt, Fxtbook

H. Bottomley, Illustration of initial terms

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

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

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

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

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

Cf. A002033, A100529.

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

njas

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