How many ways to reach an integer by addition and multiplication

Question

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?

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