# Count the number of shortest paths to n

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\$$:

$$\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 , so fewest bytes wins.

• I think it should be explicitly noted that the ^ symbol denotes exponentiation. It could be XOR as well (for instance C uses ^ for bitwise XOR). – Ramillies Aug 26 at 13:01
• @Ramillies Maybe it should be changed to MathJax. I.e. $x=x+x^j$ instead of x -> x + x^j. – Kevin Cruijssen Aug 26 at 13:33
• @KevinCruijssen: Good point, that would certainly help. – Ramillies Aug 26 at 13:37
• I have added this to the OEIS as A309997. (It will be a draft until approved.) – Peter Kagey Aug 26 at 19:48

# Jelly, 16 bytes

2+*¥þ³Ḷ¤F$n³Ạ$¿ċ


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

# 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


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],neleml]!!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<-...........................,neleml]
-- find how many times it occurs
sum   [1|x<-l,x==n]
-- pick the first entry
f n=.............................................................!!0


# 05AB1E, 17 bytes

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


Try it online!

# 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!

• Nice way of implementing BFS recursively. – Joel Aug 27 at 3:30

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

([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!

Golfing flawr's breadth-first-search. 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!

# R, 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!

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, 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!

-1 byte thanks to @RobinRyder

• !(a<-sum(x==n)) could be !{a=sum(x==n)} for -1 byte in both cases. – Robin Ryder Sep 6 at 8:37

# Pyth, 24 bytes

VQIJ/mu+G^GHd2^U.lQ2NQJB


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