Let $\mathbb{N}$ denote the positive integers and let $S = \{n^2: n\in \mathbb{N}\}$. For any positive integer $k$ we define $$\text{sq}(k) = |\{F\subseteq S: F\neq \emptyset, F\text{ is finite and } k = \sum_{n\in F} n\}|.$$


  1. Is the function $\text{sq}:\mathbb{N}\to \mathbb{N}\cup\{0\}$ surjective?
  2. Is there $m_0>1$ such that $\text{sq}^{-1}(\{m\})$ is infinite for all $m\geq m_0$?
  • $\begingroup$ This is A033461 in the OEIS. $\endgroup$ – Charles Sep 3 '15 at 17:56

The generating function is $$ \sum_{n\geq 0} \text{sq}(n) z^n = \prod_{k\geq 1} (1+z^{k^2}). $$ Using complex integration you can use this to get an asymptotic formula for $\text{sq}(n)$. This involves quite some work, but the path is well described in Andrews, The theory of partitions, chapter 6. You will arrive at something like $\text{sq}(n)\sim e^{n^{1/3}}$ times some minor terms, hence $\text{sq}$ is ultimately increasing at a pretty fast rate. In particular, $\text{sq}(n)$ is not surjective. For $\text{sq}^{-1}$ you can either derive an asymptotic series or compute the proportion of all partitions not containing the summand $1^2$ to find that $\text{sq}$ is strictly increasing from some point onwards. Hence you will most likely obtain that $\text{sq}^{-1}(\{m\})$ is infinite if and only if $m=1$.


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.