This code challenge will have you compute the number of ways to reach $n$ starting from $2$ using maps of the form $x mapsto x + x^j$ (with $j$ a non-negative integer), and doing so in the minimum number of steps.

(Note, this is related to OEIS sequence A307092.)

Example

So for example, $f(13) = 2$ because three maps are required, and there are two distinct sequences of three maps that will send $2$ to $13$:

$$beginarrayc x mapsto x + x^0 \ x mapsto x + x^2 \ x mapsto x + x^0endarray qquad textrmor qquad beginarraycx mapsto x + x^2 \ x mapsto x + x^1 \ x mapsto x + x^0endarray$$

Resulting in $2 to 3 to 12 to 13$ or $2 to 6 to 12 to 13$.

Example values

f(2) = 1 (via [])
f(3) = 1 (via [0])
f(4) = 1 (via [1])
f(5) = 1 (via [1,0])
f(12) = 2 (via [0,2] or [2,1])
f(13) = 2 (via [0,2,0] or [2,1,0], shown above)
f(19) = 1 (via [4,0])
f(20) = 2 (via [1,2] or [3,1])
f(226) = 3 (via [2,0,2,1,0,1], [3,2,0,0,0,1], or [2,3,0,0,0,0])
f(372) = 4 (via [3,0,1,0,1,1,0,1,1], [1,1,0,2,0,0,0,1,1], [0,2,0,2,0,0,0,0,1], or [2,1,0,2,0,0,0,0,1])

Challenge

The challenge is to produce a program which takes an integer $n ge 2$ as an input, and outputs the number of distinct paths from $2$ to $n$ via a minimal number of maps of the form $x mapsto x + x^j$.

This is code-golf, so fewest bytes wins.

JavaScript (ES6),  111 ... 84  80 bytes

Returns true rather than $1$ for $n=2$.

f=(n,j)=>(g=(i,x,e=1)=>i?e>n?g(i-1,x):g(i-1,x+e)+g(i,x,e*x):x==n)(j,2)||f(n,-~j)

Try it online!

Commented

f = ( // f is the main recursive function taking:
 n, // n = input
 j // j = maximum number of steps
) => ( //
 g = ( // g is another recursive function taking:
 i, // i = number of remaining steps
 x, // x = current sum
 e = 1 // e = current exponentiated part
 ) => //
 i ? // if there's still at least one step to go:
 e > n ? // if e is greater than n:
 // add the result of a recursive call with:
 g(i - 1, x) // i - 1, x unchanged and e = 1
 : // else:
 // add the sum of recursive calls with:
 g(i - 1, x + e) + // i - 1, x + e and e = 1
 g(i, x, e * x) // i unchanged, x unchanged and e = e * x
 : // else:
 x == n // stop recursion; return 1 if x = n
)(j, 2) // initial call to g with i = j and x = 2
|| f(n, -~j) // if it fails, try again with j + 1

05AB1E, 17 bytes

2¸[˜DIå#εIÝmy+]I¢

Try it online!

Haskell, 78 75 bytes

This implementation uses a breath-first-search in the "tree" of iteratively all necessary mappings x -> x + x^j.

j#x=x+x^j
f n=[sum[1|x<-l,x==n]|l<-iterate((#)<$>[0..n]<*>)[2],n`elem`l]!!0

Try it online!

Explanation

-- computes the mapping x -> x + x^j
j#x=x+x^j 
--iteratively apply this function for all exponents [0,1,...,n] (for all previous values, starting with the only value [2])
 iterate((#)<$>[0..n]<*>)[2] 
-- find each iteration where our target number occurs
 [ |l<-...........................,n`elem`l] 
-- find how many times it occurs
 sum [1|x<-l,x==n] 
-- pick the first entry
f n=.............................................................!!0

Python 2, 72 bytes

f=lambda n,l=[2]:l.count(n)or f(n,[x+x**j for x in l for j in range(n)])

Try it online!

Perl 5 (-lp), 79 bytes

$e=$_;@,=(2);@,=map$x=$_;map$x+$x**$_,0..log($e)/log$x@,until$_=grep$_==$e,@,

TIO

CJam (27 bytes)

qi2a_W$,f#f+~2%_W$&!ge=

Online demo

Warning: this gets very memory-intensive very fast.

Dissection:

qi e# Read input and parse to int n (accessed from the bottom of the stack as W$)
2a e# Start with [2]
 e# Loop
 e# Map each integer x in the current list
 _W$,f#f+~ e# to x+x^i for 0 <= i < n
 2 e# and add a bonus 2 for the special case
 % e# Gather these in the new list
 _W$&! e# Until the list contains an n
g
e= e# Count occurrences

The bonus 2s (to handle the special case of input 2, because while loops are more expensive than do-while loops) mean that the size of the list grows very fast, and the use of exponents up to n-1 means that the values of the larger numbers in the list grow very fast.