# How many tuples in $\{0,\ldots, k\}^{\log n}$ that sum of its elements is $n$?

For integers $$n \ge 0$$ and $$k \ge 2$$, define $$E^k_n$$ as the set of tuples $$b \in \{0,\ldots, k\}^{\log n}$$, such that $$n = \sum_{0 \le i \le \log n} b_i 2 ^i.$$

Note that the only element of $$E^1_n$$ is simply $$n$$ in base $$2$$.

Clearly $$|E^k_n| \le k^{\log n} = n^{\log k}$$, but what is a better, ideally tight, upperbound?

My guess is that $$n^{\frac{\log k}{\log \log n} }$$ is an upperbound.

• $\log n$ is not an integer (for $n\ne1$). So, what does $\{\,0,\dots,k\,\}^{\log n}$ mean? Commented Jul 5, 2019 at 23:15
• Well, at least in theoretical computer science, by convention, logarithms are rounded down. Commented May 3, 2020 at 8:44
• Any thoughts about the answer that Greg posted last year? Commented May 3, 2020 at 9:16

Here is an answer for certain values of $$k$$, which disproves your guess and suggests an alternate conjecture.
Suppose that $$k=2^\ell-1$$ for some $$\ell\ge2$$. Then each digit $$b_i$$ can be written uniquely in binary: $$b_i = \sum_{j=0}^{\ell-1} a_{i,j}2^j$$ with each $$a_{i,j}\in\{0,1\}$$. Thus $$\sum_{0\le i\le \log n} b_i 2^i = \sum_{0\le i\le \log n} \sum_{j=0}^{\ell-1} a_{i,j}2^j 2^i = \sum_{j=0}^{\ell-1} 2^j \sum_{0\le i\le \log n} a_{i,j} 2^i.$$ But note that for fixed $$j$$, the inner sum simply equals every integer between $$0$$ and $$2^{\log n+1}-1$$ once each. In particular, the number of solutions to $$n = \sum_{0\le i\le \log n} b_i 2^i$$ is the same as the number of solutions to $$n = \sum_{j=0}^{\ell-1} 2^j m_j$$ with each $$0\le m_j < 2^{\log n+1}$$. The number of such solutions is easy to work out asymptotically; if I made no mistakes, the answer is approximately \begin{align*} \frac{n^{\ell-1}}{(\ell-1)!2^{\ell(\ell-1)/2}} &= \frac{n^{\log_2(k+1)-1}}{(\log_2(k+1)-1)!2^{\log_2(k+1)(\log_2(k+1)-1)/2}}. \end{align*} Since the denominator doesn't depend on $$n$$, this shows that for these values of $$k$$, the function grows faster than $$n^{(\log k)/\log\log n}$$.
My suspicion is that the correct rate of growth is something like $$n^{\log_2 k - 1}$$ for all $$k$$. (The $$n^{-1}$$ factor makes sense since there are $$kn$$ possible values for the sum and we want to single out one of them.)