[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: http://oeis.org/A018819 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.
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
On 8/30/14, Warren D Smith <warren.wds@gmail.com> wrote:
How many ways PB(N), are there to partition N into powers of 2? ... limit lg(PB(N))/lg(N)^2 = 1.
Actually, I got skeptical of this limit claim, and soon found another argument based on the approximate differential equation suggesting that instead limit lg(PB(N))/lg(N)^2 = 1/2. And there is hope the latter can be made rigorous by bounding the error in the DiffEq approximation... Oops. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
On 8/30/14, Warren D Smith <warren.wds@gmail.com> wrote:
How many ways PB(N), are there to partition N into powers of 2?
PB(3)=2 PB(5)=4 PB(9)=10 PB(17)=36 PB(33)=202 PB(65)=1828 PB(129)=27338 PB(257)=692004 PB(513)=30251722 PB(1025)=2320518948 PB(2049)=316359580362 PB(4097)=77477180493604 PB(8193)=34394869942983370 PB(16385)=2.78939e+19=N^(0.329570*lgN) PB(32769)=4.16037e+22=N^(0.333950*lgN) PB(65537)=1.14788e+26=N^(0.338160*lgN) PB(131073)=5.8888e+29=N^(0.342193*lgN) PB(262145)=5.64265e+33=N^(0.346049*lgN) PB(524289)=1.01392e+38=N^(0.349732*lgN) PB(1048577)=3.42887e+42=N^(0.353247*lgN) PB(2097153)=2.18936e+47=N^(0.356601*lgN) PB(4194305)=2.64707e+52=N^(0.359803*lgN) PB(8388609)=6.07631e+57=N^(0.362860*lgN) PB(16777217)=2.65451e+63=N^(0.365781*lgN) PB(33554433)=2.21183e+69=N^(0.368573*lgN) PB(67108865)=3.52225e+75=N^(0.371244*lgN) PB(134217729)=1.07397e+82=N^(0.373801*lgN) PB(268435457)=6.28084e+88=N^(0.376251*lgN) PB(536870913)=7.05642e+95=N^(0.378599*lgN) PB(1073741825)=1.52522e+103=N^(0.380853*lgN) PB(2147483649)=6.3513e+110=N^(0.383017*lgN) PB(4294967297)=5.10186e+118=N^(0.385096*lgN) PB(8589934593)=7.91504e+126=N^(0.387096*lgN) ...aha, I see David Wilson found the asymptotic formula in OEIS via N.G. de Bruijn: On Mahler's partition problem, Indagationes Mathematicae, vol. X (1948) 210-220. OK, I'll stop computing now :)
participants (2)
-
David Wilson -
Warren D Smith