Big-$O$ behaviour of sums-of-powers-of-$2$ partitions with restricted repetition

Question

Define $a_n^{(p)}$ as the number of ways of writing $n$ as a sum of powers of $2$, each power of $2$ used at most $p$ times, with permutations of a sum not counting as distinct. I prove here that $a_n^{(3)}=\lfloor\tfrac{n}{2}\rfloor+1$; the technique can be tweaked to show that, construed as a function of $n$, $a_n^{(2^t-1)}\in O(n^{t-1})$ for integer $t\ge1$. So if $p$ is a Mersenne number, $a_n^{(p)}\in O(n^{\log_2(p+1)-1})$. Does this result hold for arbitrary integer $p\ge2$? Failing that, can we determine some function $f(p)$ for which $a_n^{(p)}\in O(f(p))$ for such $p$?

Answer 1

I like to reserve $p$ for primes most of the time so I'll rename your variable $k$, and to make some subsequent expressions easier to read I'll rewrite your $a^{(k)}_n$ as $a(k, n)$. We of course have that $k$ is between two Mersenne numbers $2^i - 1, 2^{i+1} - 1$, where

$$i = \left\lfloor \log_2 (k+1) \right\rfloor.$$

and we also have that $a(k, n)$ is an increasing function of $k$ for fixed $n$, which gives

$$a(2^i - 1, n) \le a(k, n) \le a(2^{i+1} - 1, n) \in O(n^i).$$

We also have that $a(2^i - 1, n) \in \Theta(n^{i-1})$ (a lower bound and not just an upper bound, with an implied constant that depends on $i$ and can be calculated) so this gives that $a(k, n)$ is between $\Theta(n^{\lfloor \log_2(k+1) \rfloor-1})$ and $\Theta(n^{\lfloor \log_2(k+1) \rfloor})$.