A018819 is A000123 with terms repeated. A000123 gives a formula for the asymptotics.
-----Original Message-----
From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On
Behalf Of Warren D Smith
Sent: Saturday, August 30, 2014 12:19 PM
To: math-fun@mailman.xmission.com
Subject: [math-fun] partitions into powers of 2
How many ways PB(N), are there to partition N into powers of 2?
Pretty soon I discovered most things I had to say about this, were already
stated here:
However, the OEIS, or at least this entry, does not discuss asymptotics.
(Shouldn't there be a section "asymptotics" for many sequences?)
It is easy to see that, if N>=1, then
N^(A+B*lg(N)) <= PB(N) <= N^(C+D*lg(N)) where lg(x) = log(x)/log(2) and
A,B,C,D are constants.
Indeed, C=D=1 and A=0,B=1/4 are valid, the former ought to be obvious.
To do a bit better: By using the recurrence
PB(N) = SUM( PB(j), j=0..floor(N/2) )
we can show
PB(N) <= (N/2+1)^lg(N).
It follows that
D=1, C=-1
should be valid asymptotically.
We also can see from the same recurrence that
PB(N) grows ultimately faster than N^((1-epsilon)*lg(N)) for any epsilon>0.
Thus
limit lg(PB(N))/lg(N)^2 = 1.
It is not so obvious, though, whether there is some expression of our form
(or any other simple form) that is asymptotic to PB(N) for large N... and if so,
what it is.
There are a huge number of generating function identities and recurrences
you can write down.
The recurrences
PB(2m+1) = PB(2m) = PB(2m-1) + PB(m)
suggest the approximate differential equation
2*PB'(x) = PB(x/2).
It might be possible to determine the asymptotics of PB by substituting
appropriate ansatzes into this differential equation.
Saddlepoint methods involving generating functions might also work.
_______________________________________________
math-fun mailing list
<mailto:math-fun@mailman.xmission.com> math-fun@mailman.xmission.com
<https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun