Problem #320: Let $S(N)$ count the number of distinct sums of the form...

---

Progress

Bleicher and Erdős [BlEr75] proved the lower bound\[\log S(N)\geq \frac{N}{\log N}\left(\log 2\prod_{i=3}^k\log_iN\right),\]valid for $k\geq 4$ and $\log_kN\geq k$, and also [BlEr76b] proved the upper bound\[\log S(N)\leq \frac{N}{\log N}\left(\log_r N \prod_{i=3}^r \log_iN\right),\]valid for $r\geq 1$ and $\log_{2r}N\geq 1$. (In these bounds $\log_in$ denotes the $i$-fold iterated logarithm.)

Bettin, Grenié, Molteni, and Sanna [BGMS25] improved the lower bound to\[\log S(N) \geq \frac{N}{\log N}\left(2\log 2\left(1-\frac{3/2}{\log_kN}\right)\prod_{i=3}^k\log_iN\right),\]valid for $k\geq 4$ and $\log_kN\geq 3/2$. (In particular this goes to infinity faster than the lower bound of Bleicher and Erdős.)

See also [321].