Growth Rate of Power of 2 Partition Function

Question

I was wondering how to find the growth rate of the function defined by the number of ways to partition $2^n$ as powers of 2. After a search through OEIS I came across OEIS A002577 which is what I'm looking for. I can't seem to find any link to asymptotics for this function. Could someone help?

Answer 1

Go a bit deeper. OEIS A000123 gives the number of ways of partitioning $2n$ (multiplication, not exponentiation) into powers of two. In the formulas section there is this from Philippe Flajolet (typesetting and expansion of abbreviations is mine):

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(2n) =\frac1{2\log2}\left(\log\frac n{\log n}\right)^2+\left(\frac12+\frac1{\log2}+\frac{\log\log2}{\log2}\right)\log n\\ -\left(1+\frac{\log\log2}{\log2}\right)\log\log n+\Phi\left(\frac{\log\frac n{\log n}}{\log2}\right)$$ where […] $\Phi(x)$ is a certain periodic function with period 1 and a tiny amplitude.

I will abbreviate the above RHS to $A\left(\log\frac n{\log n}\right)^2+B\log n +C\log\log n+O(1)$. To get the growth rate of the number of partitions of $2^n$, substitute $n\to2^{n-1}$: $$\log p(2^n)=A\left(\log\frac{2^{n-1}}{\log2^{n-1}}\right)^2+B\log2^{n-1}+C\log\log2^{n-1}+O(1)$$ $$=A((n-1)\log2-\log((n-1)\log2))^2+B(n-1)\log2+C\log((n-1)\log2)+O(1)$$ Define $m=(n-1)\log2=O(n)$: $$=A(m-\log m)^2+Bm+C\log m+O(1)$$ Therefore $$p(2^n)=e^{A(m-\log m)^2+Bm+C\log m+O(1)}=O(e^{n^2})$$

Answer 2

Maybe this is what you're looking for: let $b(n)$ be the number of partitions of $2^n$ into powers of $2$, and assume that $2^{n+1}$ is an integer. Then de Bruijn (1948) showed that there exists a function $\psi$ of period $1$ such that $$\begin{split}\ln b(n+1)&=\tfrac{1}{2\ln 2}(n\ln 2-\ln n-\ln\ln 2)^2\\ &\quad+\left(\tfrac{1}{2}+\tfrac{1}{\ln 2}+\tfrac{\ln \ln 2}{\ln 2}\right)n\ln 2\\ &\quad-\left(1+\tfrac{\ln\ln 2}{\ln 2}\right)(\ln n+\ln\ln 2)\\ &\quad+ \psi\left(\tfrac{n\ln 2-\ln\ln n -\ln\ln2 }{\ln 2}\right)+ o(1)\text{.}\end{split}$$