# Minimum 1's to get 1-expression for n [duplicate]

### Background

Challenge is inspired by this question.

The 1-expression is a formula that in which you add and multiply the number 1 any number of times. Parenthesis is allowed, but concatenating 1's (e.g. 11) is not allowed.

Here is an example to get the 1-expression for $$\19\$$:

(1+1)*(1+1)*(1+1+1+1)+1+1+1 = 19


Total number of $$\1\$$'s is $$\11\$$ but there is shorter than this:

(1+1)*(1+1+1)*(1+1+1)+1 = 19


Total number of $$\1\$$'s is $$\9\$$.

### Program

Given a positive integer n output the minimum 1's to get the 1-expression for n.

Notes:

• For reference, the sequence is A005245.
• This is so shortest answer in each language wins!

### Test cases

Input -> Output | 1-Expression
1 -> 1 | 1
6 -> 5 | (1+1+1)*(1+1)
22 -> 10 | (1+1)*((1+1+1+1+1)*(1+1)+1)
77 -> 14 | (1+1)*(1+1)*((1+1+1)*(1+1+1)*(1+1)+1)+1
214 -> 18 | ((((1+1+1)*(1+1)*(1+1)+1)*(1+1)*(1+1)+1)*(1+1)+1)*(1+1)
2018 -> 23 | (((1+1+1)*(1+1)+1)*(1+1+1)*(1+1+1)*(1+1)*(1+1)*(1+1)*(1+1)+1)*(1+1)

• First time posting a challenge. Sandbox – u-ndefined Oct 27 '18 at 2:04
• Very well-written first challenge. Unfortunately, I believe it's an exact duplicate of this one from earlier this year (which happens to be that user's first challenge too). So sorry this wasn't caught in the Sandbox... – ETHproductions Oct 27 '18 at 2:59

# Wolfram Language (Mathematica), 76 71 bytes

If[#<2,1,Min[#+Reverse@#&/@{#0/@Range[#-1],#0/@Most@Rest@Divisors@#}]]&


Try it online!

The recursive approach: define f[n] to be the minimum of f[k]+f[n-k]over all k less than n, and f[d] + f[n/d]over all divisors of n (other than 1 and n itself).