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


## marked as duplicate by ETHproductions code-golf StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Oct 27 '18 at 3:01

• 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

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