[Question]
  [
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](https://oeis.org/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\$:
$$\begin{array}{c} x \mapsto x + x^0 \\ x \mapsto x + x^2 \\ x \mapsto x + x^0\end{array} \qquad \textrm{or} \qquad \begin{array}{c}x \mapsto x + x^2 \\ x \mapsto x + x^1 \\ x \mapsto x + x^0\end{array}$$
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](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so fewest bytes wins.
  
[Answer]
# JavaScript (ES6), ~~111 ... 84~~ 80 bytes
[Returns true](https://codegolf.meta.stackexchange.com/a/9067/58563) 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!](https://tio.run/##LYzNCsIwEITvPsUePGTttpj4h0rak08hQkNNY0NJpBUptPXVY0APA/PNDGPVW/VV1zxfqfN3HUItmSOLMmdGsoYG0pJHagqdu8KwJuU04OlvEo2J@a1WMR2kdMgsCZymOt6kH4vhfBUEG4ItwY6AR@CR@JFArKPEPrYHcVtkte8uqnowBzKHyrvetzprvWGlYsvRzQgSlmP8xblEDF8 "JavaScript (Node.js) – 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
```
[Answer]
# [Haskell](https://www.haskell.org/), ~~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!](https://tio.run/##JYxBCoMwFAX3PcUvuojtV0xsKwXjNboIKbqIGI1BNIVQvHuqlIHHLB7Tt@uojAlhiDz3V/8eTh1YLtbPJOjmq9Sg59zKzVSpdmppnSIkSqq4FnmWWVld6kQwibZRRk2NkedzHqZWW@AwL9o6iMG1o4Jyl6@eX9r1hPMESAdHhGGBN7wjZUgLpE9kOTL2wKJkMgFB8Q/bOXY/y/AD "Haskell – 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
```
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 17 bytes
```
2¸[˜DIå#εIÝmy+]I¢
```
[Try it online!](https://tio.run/##yy9OTMpM/f/f6NCO6NNzXDwPL1U@t9X48NzcSu1Yz0OLgBJGZgA "05AB1E – Try It Online")
[Answer]
# [Python 2](https://docs.python.org/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!](https://tio.run/##HYzLDsIgFAXX@hUsSz1p5OIjNumXkC7wgbbBS0Nqgl@P4G7O5GSW7/oKTDm7wdv39W4Fww@Gxt53t/DhtWEZonANw6RdattZuLKTmFj4P84Vo@Xno1xHmavj6gxB44AjFEFpqAtoD6IT9Lnkt5slTiVfylLmHw "Python 2 – Try It Online")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 16 bytes
```
2+*¥þ³Ḷ¤F$n³Ạ$¿ċ
```
[Try it online!](https://tio.run/##y0rNyan8/99IW@vQ0sP7Dm1@uGPboSVuKnlA1q4FKof2H@n@//@/oTEA "Jelly – Try It Online")
A full program taking as its argument \$n\$ and returning the number of ways to reach \$n\$ using the minimal path length. Inefficient for larger \$n\$. 
[Answer]
# Perl 5 (`-lp`), 79 bytes
```
$e=$_;@,=(2);@,=map{$x=$_;map$x+$x**$_,0..log($e)/log$x}@,until$_=grep$_==$e,@,
```
[TIO](https://tio.run/##FchBCsIwEEDR/ZxjFm0dazOxikggNwkuQinEZqgVAuLVHdPV@3yJaxpVMToMd0@u4Xbn@ZAPlv3VwnLA0nUYaOj7lKcGY3uqYvl6ei/bnDC4aY1ScRjJkyqDhTOMYBiMBXMDHoD5AvbKvyzbnJeXHpP8AQ)
[Answer]
## CJam (27 bytes)
```
qi2a{{_W$,f#f+~2}%_W$&!}ge=
```
[Online demo](http://cjam.aditsu.net/#code=qi2a%7B%7B_W%24%2Cf%23f%2B~2%7D%25_W%24%26!%7Dge%3D&input=13)
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 `2`s (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.
[Answer]
# [Haskell](https://www.haskell.org/), 65 bytes
```
([2]%)
l%n|elem n l=sum[1|x<-l,x==n]|1>0=[x+x^k|x<-l,k<-[0..n]]%n
```
[Try it online!](https://tio.run/##JYrLCoMwFAX3/Yq7UFB6FRP7BONvdJGmECTWkBhCtRCK397UIgOH4TCDnIyyNvbsHjNORZrvbOoWZdUIDiyb3iMnS2gKi4ExJxbSVoyHfXiY7TVNwauydEKkLo5SO2DgX9rNkMAsjYLLKh/tb3oeMsZyyHpokpZTrPGARyQUSY3kirRCSk9Yn6nIgRPcoCv/XWMRv11v5XOKRef9Dw "Haskell – Try It Online")
Golfing [flawr's breadth-first-search](https://codegolf.stackexchange.com/a/190899/20260). I also tried going backwards from `n`, but it was longer:
**73 bytes**
```
q.pure
q l|elem 2l=sum[1|2<-l]|1>0=q[x|n<-l,x<-[0..n],i<-[0..n],x+x^i==n]
```
[Try it online!](https://tio.run/##PYrLCoMwEEX3/YpZdKF0FDP2QcH4G12kKYjEGowhviAUv72ppVAOXM6B21ZTp4wJDb@HIXXLqHYDmFUZ1QMZPi29YCsViZErKzM@CL/ardAXicjS1ErUf/MH/9CcWxn6Slvg4EZtZ9jDXHUKWLbZS7ubntuI8xiiBop9KQhzPOIJGSHLkV2RMiQ6Y34hGYNg@IM2vrudZXjXjameU0hq5z4 "Haskell – Try It Online")
[Answer]
# [R](https://www.r-project.org/), ~~78~~ 77 bytes
```
function(n,x=2){while(!{a=sum(x==n)})x=rep(D<-x[x<n],n+1)+outer(D,0:n,'^')
a}
```
[Try it online!](https://tio.run/##RczRCoIwFMbxe59i4YXn4AI9s6Jwd75FFEhsJNgxTGkgPvtqF7W7Hx9/vtFb7e3Mt6kbGFg6Tbi8711vYLO0@jU/wGnNuKLTo3lCU2/d2dV8kZyXmA/zZEZoZHFimV0zTNrVWyAUQqSiTCyoyCpyF1mGOBUUqCKP@Auo@K9Ee/xShd8DBVb@Aw "R – Try It Online")
Using a simplified Breadth-first Search
Unrolled code with explanation :
```
function(n){                              # function taking the target value n
  x=2                                     # initialize vector of x's with 2
  while(!(a<-sum(x==n))) {                # count how many x's are equal to n and store in a
                                          # loop while a == 0
    x=rep(D<-x[x<n],n+1)+outer(D,0:n,'^') # recreate the vector of x's 
                                          # with the next values: x + x^0:n
  }
a                                         # return a
}   
```
---
Shorter version with huge memory allocation (failing for bigger cases) :
# [R](https://www.r-project.org/), ~~70~~ 69 bytes
```
function(n,x=2){while(!{a=sum(x==n)})x=rep(x,n+1)+outer(x,0:n,'^')
a}
```
[Try it online!](https://tio.run/##RczBCsIwEATQe78i0kOzNIdmUxWF/RWhSIIF3ZbYYKD022Nz0NzeDMP45Ci5wPdlnFiyioSwfh7j08rDOtA7vGQkYtggkrezjIpbDe0UFuv30F1ZNbcGqmFLTiIIIWqhKydNYV94LNR5XAvMNIUX@A2w@7eIJ9hp8u8ZM/v0BQ "R – Try It Online")
-1 byte thanks to @RobinRyder
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), 24 bytes
```
VQIJ/mu+G^GHd2^U.lQ2NQJB
```
[Try it online!](https://tio.run/##K6gsyfj/PyzQ00s/t1TbPc7dI8UoLlQvJ9DIL9DL6f9/IyMzAA "Pyth – Try It Online")
This should produce the correct output, but is very slow (the 372 test case times out on TIO). I could make it shorter by replacing `.lQ2` with `Q`, but this would make the runtime horrendous.
Note: Produces no output for unreachable numbers \$(n \leq 1)\$
### Explanation
```
VQ                        # for N in range(Q (=input)):
   J                      #   J =
     m                    #     map(lambda d:
      u                   #       reduce(lambda G,H:
       +G^GH              #         G + G^H,
            d2            #         d (list), 2 (starting value) ),
              ^U.lQ2N     #       cartesian_product(range(log(Q, 2)), N)
    /                Q    #     .count(Q)
  IJ                  JB  #   if J: print(J); break
```
]