# 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 Oct 27, 2018 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... Oct 27, 2018 at 2:59

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

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