28
\$\begingroup\$

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

\$\endgroup\$
  • 4
    \$\begingroup\$ OEIS A005245 \$\endgroup\$ – betseg Jan 28 '18 at 0:46
  • 9
    \$\begingroup\$ 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! \$\endgroup\$ – betseg Jan 28 '18 at 0:55
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – Shaggy Jan 28 '18 at 11:25
  • 2
    \$\begingroup\$ Are there examples where f(x) != x.primeFactorisation().sum() except 1? \$\endgroup\$ – jrtapsell Jan 28 '18 at 22:22
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Ross Millikan Jan 29 '18 at 2:29
17
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – xnor Jan 30 '18 at 20:45
  • \$\begingroup\$ 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. \$\endgroup\$ – Dennis Feb 1 '18 at 15:53
  • \$\begingroup\$ 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. \$\endgroup\$ – xnor Feb 1 '18 at 23:58
10
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Neil Feb 7 '18 at 10:20
  • \$\begingroup\$ Did you try a single walk on the a array? \$\endgroup\$ – edc65 Feb 19 '18 at 11:12
  • \$\begingroup\$ @edc65 Sorry, but I'm unclear as to what you're suggesting and why. \$\endgroup\$ – Neil Feb 19 '18 at 14:13
  • \$\begingroup\$ I see 2 maps, each one scanning the a array. Can't you merge the evaluations in the 2 lambdas and take the min? \$\endgroup\$ – edc65 Feb 19 '18 at 14:17
  • \$\begingroup\$ @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! \$\endgroup\$ – Neil Feb 19 '18 at 14:39
5
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ 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]])). \$\endgroup\$ – Jonathan Allan Jan 28 '18 at 15:59
4
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ @pizzapants184 The main function f must not be anonymous, as it calls itself recursively. \$\endgroup\$ – Jonathan Frech Jan 28 '18 at 23:56
  • \$\begingroup\$ Ah, sorry, I didn't see that. \$\endgroup\$ – pizzapants184 Jan 28 '18 at 23:57
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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