Find number of ones to get a number using + and *

Question

Introduction

Your goal is to find the least number of ones you need to add or multiply together to get the input value, this is A005245.

Input

One positive integer N.

Output

The smallest number of ones that must be added/multiplied to get N.

Sample Input

7

Sample Output

6

Explanation

(1 + 1 + 1) * (1 + 1) + 1 = 7

Because this requires 6 ones, the output is 6

Test cases

 1  1
 2  2
 3  3
 5  5
10  7
20  9
50 12

As this is a code-golf challenge, lowest number of bytes wins.

Answer 1

Python 2, 74 70 bytes

f=lambda n:min([n]+[f(j)+min(n%j*n+f(n/j),f(n-j))for j in range(2,n)])

Try it online!

Alternate version, 59 bytes (unverified)

f=lambda n:min([n]+[f(j)+f(n/j)+f(n%j)for j in range(2,n)])

This works at least up to n = 1,000,000, but I have yet to prove that it works for all positive n.

Try it online!

Answer 2

Jelly, 16 14 bytes

Thanks Dennis for saving 2 bytes!

ÆḌḊ,Ṗ߀€+U$FṂo

Try it online!

---

Logic explanation

Given a number n:

• If it's 1, the answer is 1. Otherwise:

The representation is either a + b or a × b, where a and b are expressions.

Consider all possible values of a and b:

• If the representation is a + b, then a and b are in range [1 .. n-1].
• If the representation is a × b, a and b are proper divisors of n larger than 1.

In both cases, the list [[<proper divisors of n larger than 1>], [1, 2, ..., n-1]] is computed (ÆḌḊ,Ṗ), map the current link over each number ߀€, add the correct pairs together (+U$) and get the minimum value (FṂo).

Code explanation

ÆḌḊ,Ṗ߀€+U$FṂo   Main link. Assume n = 10.
ÆḌ       Proper divisors. [1,2,5]
  Ḋ      Ḋequeue, remove the first element. [2,5]
   ,Ṗ    Pair with Ṗop. Auto convert n = 10 to range 
         [1,2,3,4,5,6,7,8,9,10] and remove the last element
         10, get [1,2,3,4,5,6,7,8,9].

߀€      Apply this link over each element.
   +U$   Add with the Upend of itself.

FṂ       Flatten and get the Ṃinimum element.
  o      Logical or with n.
         If the list is empty, minimum returns 0 (falsy), so logical or
         convert it to n.

Answer 3

Pari/GP, 66 bytes

A port of Dennis's Python answer:

f(n)=vecmin(concat(n,[f(j)+min(n%j*j+f(n\j),f(n-j))|j<-[2..n-1]]))

Try it online!

---

Pari/GP, 72 bytes

Longer, but more efficient:

f(n)=if(n<6,n,vecmin([if(d>1,f(d)+f(n/d),1+f(n-1))|d<-divisors(n),d<n]))

Try it online!

Answer 4

JavaScript (ES6), 108 96 bytes

f=n=>n<6?n:Math.min(...[...Array(n-2)].map((_,i)=>Math.min(f(++i)+f(n-i),n%++i/0||f(i)+f(n/i))))

Very inefficient; Array(n>>1) speeds it up slightly at a cost of a byte. Explanation: n%++i is non-zero if i is not a factor, so n%++i/0 is Infinity (and therefore truthy, and also definitely not minimal) if i is not a factor, but NaN (and therefore falsy) if i is a factor. Edit: Saved 12 bytes with inspiration from @edc65.

Answer 5

Pari/GP, 213 bytes

Edit: I've been severely beaten.

f(n)={d;n<6&return(n);if(n<=#a,a[n]&return(a[n]),a=vector(n));for(i=1,n-1,a[i]||a[i]=f(i));a[n]=min(vecmin(vector(n\2,k,a[k]+a[n-k])),if(isprime(n),n,vecmin(vector((-1+#d=divisors(n))\2,i,a[d[i+1]]+a[d[#d-i]]))))}

Try it online!

Answer 6

Python 2, 181 bytes

def F(N,n,s="",r=""):
 try:
	if n<1:return(eval(s)==N)*0**(`11`in s or"**"in s)*s
	for c in"()+*1":r=F(N,~-n,s+c)or r
 except:r
 return r
f=lambda N,n=1:F(N,n).count(`1`)or f(N,-~n)

Try it online!

Answer 7

Wolfram Language (Mathematica), 59 bytes

Saved 3 bytes thanks to Martin Ender. Using CP-1252 encoding, where ± is one byte.

±1=1;±n_:=Min[1+±(n-1),±#+±(n/#)&/@Divisors[n][[2;;-2]]]

Try it online!

Answer 8

Perl 5, -p 78 bytes

79 bytes in old style counting (+1 for -p)

The fact that perl must use an extra $ for all scalar access really hurts the length of golfs that do a lot of arithmetic...

This method is mostly like the others already posted (try multiplication and addition to build a target number, take the cheapest). It however doesn't repeatedly recurse down so it can be used for relatively large inputs.

It also doesn't try to minimize the cost of building a number by addition or multip[lication because perl 5 has no builtin min and numeric sort is looooooong (as seen from the sort still in the code). Instead I just assume if a number is a factor of the target that I will use multiplication. That is safe since if e.g. 3 is a factor of 12 (so it sums the cost of 3 and 12/3) later in the loop it will consider 9=12-3 which will not be a factor, so 9+3 with the same cost as 3+9 will get tried anyways. However that may fail for targets <= 4 (it only does for 1 and 2). Adding $_ to the list to minimize fixes that. Which is unfortunate since I don't actually need that for the base cases because I already initialize @; with the proper starting values so it costs 3 bytes.

#!/usr/bin/perl -p
($_)=sort{$a-$b}$_,map{$;[$_]+$;[$'%$_?$'-$_:$'/$_]}//..$_ for@;=0..$_;$_=pop@

Try it online!