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.

7

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 challenge, lowest number of bytes wins.

• OEIS A005245 Jan 28, 2018 at 0:46
• Welcome to Programming Puzzles and Code Golf! As a first challenge this is OK, but next time please use the Sandbox before posting challenges so you can get feedback! Jan 28, 2018 at 0:55
• I'd suggest modifying this to explicitly state that you're looking for the minimum number of ones required. Otherwise, simply outputting the original number and claiming that it's the number of ones you need to add together would be a valid solution. Jan 28, 2018 at 11:25
• Are there examples where f(x) != x.primeFactorisation().sum() except 1? Jan 28, 2018 at 22:22
• @jrtapsell: yes. The given example of $f(7)=6$ is one. For any (large enough) prime $p$ you can factor $p-1$ and add one. You may be able to do better yet. Jan 29, 2018 at 2:29

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!

• Sorry if I'm missing something simple, but it's not obvious to be that this tries every viable expression tree. In particular, we have outer layer n=a*j+b with b<j, but might we need b>=j?
– xnor
Jan 30, 2018 at 20:45
• Hm, it would only fail if both b>=j and b>=a. But you're right, it's not obvious that this won't happen. Feb 1, 2018 at 15:53
• Interesting that there's no counterexamples up to 1,000,000, I wonder if it actually just always works. My best thought for a counterexample would be something of form a*b+c*d with a,b,c,d all summation expressions and are very efficient.
– xnor
Feb 1, 2018 at 23:58

Jelly, 16 14 bytes

Thanks Dennis for saving 2 bytes!

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.


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.

• I tried running this in the background to see whether it was in fact capable of calculating f(50) but unfortunately Windows Update rebooted my PC before it could finish.
– Neil
Feb 7, 2018 at 10:20
• Did you try a single walk on the a array? Feb 19, 2018 at 11:12
• @edc65 Sorry, but I'm unclear as to what you're suggesting and why.
– Neil
Feb 19, 2018 at 14:13
• I see 2 maps, each one scanning the a array. Can't you merge the evaluations in the 2 lambdas and take the min? Feb 19, 2018 at 14:17
• @edc65 Ah yes, for some reason I thought nesting the min wouldn't be cheaper but I get to replace (i+=2) with another ++i so I'm saving 12 bytes in total, thanks!
– Neil
Feb 19, 2018 at 14:39

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!

• Dennis improved his method and using that can save you 11 bytes: f(n)=vecmin(concat(n,[f(j)+f(n\j)+f(n%j)|j<-[2..n-1]])). Jan 28, 2018 at 15:59

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!

Python 2, 181 bytes

def F(N,n,s="",r=""):
try:
if n<1:return(eval(s)==N)*0**(11in 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!

• @pizzapants184 The main function f must not be anonymous, as it calls itself recursively. Jan 28, 2018 at 23:56
• Ah, sorry, I didn't see that. Jan 28, 2018 at 23:57

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!

• Using ± instead of f saves 3 bytes assuming the source is encoded in CP 1252: tio.run/##y00syUjNTSzJTE78///QRkNbQ@tDG/PirWx9M/… Jan 28, 2018 at 22:37
• Does not work correctly for input 353942783. Oct 27, 2018 at 3:00

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!