5
\$\begingroup\$

This question already has an answer here:

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)
\$\endgroup\$

marked as duplicate by ETHproductions code-golf Oct 27 '18 at 3:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ First time posting a challenge. Sandbox \$\endgroup\$ – u_ndefined Oct 27 '18 at 2:04
  • 8
    \$\begingroup\$ 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... \$\endgroup\$ – ETHproductions Oct 27 '18 at 2:59
1
\$\begingroup\$

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

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.