Inspired by the title of a recent question, which turned out to be about something else.
Start with any number. Then repeatedly add any positive integer or multiply by any integer greater than $1$.
Let $f(n)$ be the number of ways to reach $n$.
For example, $f(3)=6$ because $$3=2+1=1+2=(1+1)+1=(1×2)+1=1×3$$ The first few values are https://oeis.org/A348378 $$1,3,6,15,27,63,117,...$$ On one hand, it always seems to be a multiple of $3$. On the other, the first twenty terms are close to $0.988×2^n$ with an oscillation of size around $1.4^n$.
How would one prove either of those things?


1 Answer 1


An integer $n \ge 1$ can be reached from $j < n$ by adding a positive integer, and also by multiplying $j$ with a positive factor if $j$ is a divisor of $n$.

Therefore the function can be recursively defined as $f(0) = 1$ and $$ f(n) = \sum_{0 \le j < n} f(j) + \sum_{\substack{1 \le j < n\\ j \mid n}} f(j) $$ for $n \ge 1$.

If $n \ge 2$ then $f(0) = 1$ occurs in the first sum, and $f(1)=1$ occurs in both sums, so that $$ \tag{$*$} f(n) = 3 + \sum_{2 \le j < n} f(j) + \sum_{\substack{2 \le j < n\\ j \mid n}} f(j) $$ for $n \ge 2$.

With respect to the first question:

It follows from $(*)$ and induction that $f(n)$ is a multiple of three for all $n \ge 2$:

  • $f(2) = 3$ since the two sums on the right are empty.
  • For $n \ge 3$ is $f(n)$ equal to $3$ plus a sum of terms $f(j)$ with $2 \le j < n$.

With respect to the second question I have only a very rough estimate so far:

$$ \sum_{j=0}^{n-1} f(j) \le f(n) \le 2 \sum_{j=0}^{n-1} f(j) $$ implies that $$ 2^{n-1} \le f(n) \le 2 \cdot 3^{n-1} $$ for $n \ge 1$.

  • $\begingroup$ The second sum will be dominated by $j=n/2$ when $n$ is even $\endgroup$
    – Empy2
    Jan 24 at 13:51

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.