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\$
9
  • 4
    \$\begingroup\$ OEIS A005245 \$\endgroup\$
    – betseg
    Jan 28, 2018 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, 2018 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, 2018 at 11:25
  • 2
    \$\begingroup\$ Are there examples where f(x) != x.primeFactorisation().sum() except 1? \$\endgroup\$
    – jrtapsell
    Jan 28, 2018 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\$ Jan 29, 2018 at 2:29

8 Answers 8

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\$
3
  • \$\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, 2018 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, 2018 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, 2018 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\$
0
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\$
5
  • \$\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, 2018 at 10:20
  • \$\begingroup\$ Did you try a single walk on the a array? \$\endgroup\$
    – edc65
    Feb 19, 2018 at 11:12
  • \$\begingroup\$ @edc65 Sorry, but I'm unclear as to what you're suggesting and why. \$\endgroup\$
    – Neil
    Feb 19, 2018 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, 2018 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, 2018 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
  • 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\$ Jan 28, 2018 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\$
0
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\$
2
  • \$\begingroup\$ @pizzapants184 The main function f must not be anonymous, as it calls itself recursively. \$\endgroup\$ Jan 28, 2018 at 23:56
  • \$\begingroup\$ Ah, sorry, I didn't see that. \$\endgroup\$ Jan 28, 2018 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\$
2
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 and acknowledge you have read our privacy policy.

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