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.
4OEIS A005245 – betseg – 2018-01-28T00:46:00.527
9
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!
– betseg – 2018-01-28T00:55:18.2504I'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. – Shaggy – 2018-01-28T11:25:03.180
To clarify, you meant "using + and * ". Exponentiation would allow fewer, e.g. 9 = (1 + 1 + 1) ^ (1 + 1) ; uses 5 ones, not 6. – smci – 2018-01-28T21:27:59.893
2Are there examples where
f(x) != x.primeFactorisation().sum()
except 1? – jrtapsell – 2018-01-28T22:22:23.6931@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. – Ross Millikan – 2018-01-29T02:29:05.230
@Ross Fun fact (taken from the oeis page): the smallest prime number p such that f(p) doesn't equal f(p-1)+1 is p=353942783 – Carmeister – 2018-01-29T03:43:46.453
1@jrtapsell: Yes, many primes or pseudoprimes, esp. near multiples of a large power of 2 or 3 might be more compactly written as that power + a small offset. Examples: a) 13 = 223+1 (requires 8) and b) 129 = 2222222 + 1 (requires 15, not 129). Intuitively, the "optimal" factorization will generally involve powers of 2 and 3 such that we are approximating e^x. – smci – 2018-01-29T06:30:27.160
Bonus points if solutions work up to known counterexamples n = 353942783 and n = 516743639 ? – smci – 2018-01-29T06:35:28.617