21
1
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 code-golf, so fewest bytes wins.
1I 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 – 2019-08-26T13:01:58.2631@Ramillies Maybe it should be changed to MathJax. I.e. $x=x+x^j$ instead of
x -> x + x^j
. – Kevin Cruijssen – 2019-08-26T13:33:16.993@KevinCruijssen: Good point, that would certainly help. – Ramillies – 2019-08-26T13:37:06.403
I have added this to the OEIS as A309997. (It will be a draft until approved.)
– Peter Kagey – 2019-08-26T19:48:00.890