1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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})$$

$\endgroup$
0
$\begingroup$

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.