# How many ways to reach an integer by addition and multiplication

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?

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$$.

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