"D1›Di4L+DŠ/®δ.V+>ß"©.V
Port of @xnor's Python answer, so make sure to upvote that answer as well.
Still pretty long, since 05AB1E is very verbose for recursive functions.
Try it online or verify most test cases (it'll time out before it has output all test cases).
Using the given formula would be 32 bytes instead:
•¬òÃ,v₅aw°Üÿ∊•82в2ôε`Š/4.nî5*+}ß
Try it online or verify all test cases.
Explanation:
Uses recursive method:
$$f(n) = \begin{cases}
0, & \text{if $n\leq1$} \\
\min(f(\frac{n}{2})+3, f(\frac{n}{3})+4, f(\frac{n}{4})+5, f(\frac{n}{5})+6), & \text{if $n>1$}
\end{cases}$$
"..." # Define the recursive string explained below
© # Store it in variable `®` (without popping)
.V # Pop and evaluate it as 05AB1E code
# (after which the result is output implicitly)
D # Duplicate the current value n
# (which will use the implicit input in the first iteration)
1› # Pop and check whether it's larger than 1
D # Duplicate this check
i # Pop the copy, and if it's truthy:
4L # Push list [1,2,3,4]
+ # Add the truthy check that's still on the stack: [2,3,4,5]
D # Duplicate this list
Š # Tripleswap to [2,3,4,5],n,[2,3,4,5]
/ # Divide [n/2,n/3,n/4,n/5]
δ # Map over each value:
® .V # And do a recursive eval to `®`
+ # Then add the values in the two lists together:
# [2+f(n/2),3+f(n/3),4+f(n/4),5+f(n/5)]
> # Increase each by 1
# [3+f(n/2),4+f(n/3),5+f(n/4),6+f(n/5)]
ß # Pop and leave the minimum
# (implicit else: use the duplicated falsey check, aka 0)
•¬òÃ,v₅aw°Üÿ∊• # Push compressed integer 50972899172091152076282460330
82в # Convert it to base-82 as list:
# [1,0,2,3,3,4,5,6,6,7,9,8,27,12,81,16]
2ô # Split it into pairs:
# [[1,0],[2,3],[3,4],[5,6],[6,7],[9,8],[27,12],[81,16]]
ε # Map over each pair [u,c]:
` # Pop and push both values to the stack
Š # Triple-swap u,c to c,i,u, where i is the implicit input
/ # Divide the input by u
4.n # Take log_4 of it
î # Ceil it
5* # Multiply by 5
+ # Add c
}ß # After the map: pop and leave the minimum
# (which is output implicitly as result)
See this 05AB1E tip of mine (sections How to compress large integers? and How to compress integer lists?) to understand why •¬òÃ,v₅aw°Üÿ∊• is 50972899172091152076282460330 and •¬òÃ,v₅aw°Üÿ∊•82в is [1,0,2,3,3,4,5,6,6,7,9,8,27,12,81,16].
