29
3
Your task is to write a program that, on input n, outputs the minimal expression of each number 1 through n in order. The shortest program in bytes wins.
A minimal expression combines 1's with addition and multiplication to result in the given number, using as few 1's as possible. For example, 23
is expressed as 23=((1+1+1)(1+1)+1)(1+1+1)+1+1
with eleven ones, which is minimal.
Requirements:
- The program must take as input a positive natural number n.
- Output must be in this format:
20 = ((1+1+1)(1+1+1)+1)(1+1)
- Your output may not have needless parentheses, like
8 = ((1+1)(1+1))(1+1)
. - The multiplication sign
*
is optional. - Spaces are optional.
- You don't have to output all the possible equations for given value: For example, you have the choice to output
4=1+1+1+1
or4=(1+1)(1+1)
. You don't have to output both. - The shortest program (in bytes) in each language wins.
1=1 2=1+1 3=1+1+1 4=1+1+1+1 5=1+1+1+1+1 6=(1+1+1)(1+1) 7=(1+1+1)(1+1)+1 8=(1+1+1+1)(1+1) 9=(1+1+1)(1+1+1) 10=(1+1+1)(1+1+1)+1 11=(1+1+1)(1+1+1)+1+1 12=(1+1+1)(1+1)(1+1) 13=(1+1+1)(1+1)(1+1)+1 14=((1+1+1)(1+1)+1)(1+1) 15=(1+1+1+1+1)(1+1+1) 16=(1+1+1+1)(1+1)(1+1) 17=(1+1+1+1)(1+1)(1+1)+1 18=(1+1+1)(1+1+1)(1+1) 19=(1+1+1)(1+1+1)(1+1)+1 20=((1+1+1)(1+1+1)+1)(1+1)
Here are some more test cases: (remember, that other expressions with the same number of 1's are also allowed)
157=((1+1+1)(1+1)(1+1)+1)(1+1+1)(1+1)(1+1)+1
444=((1+1+1)(1+1+1)(1+1)(1+1)+1)(1+1+1)(1+1)(1+1)
1223=((1+1+1)(1+1+1)(1+1+1)(1+1+1)(1+1+1)+1)(1+1+1+1+1)+1+1+1
15535=((((1+1+1)(1+1+1)(1+1+1)(1+1+1)+1)((1+1+1)(1+1)+1)+1)(1+1+1)+1)(1+1+1)(1+1+1)+1
45197=((((1+1+1)(1+1)(1+1)(1+1)+1)(1+1+1+1+1)(1+1)+1)(1+1+1)(1+1)(1+1)+1)(1+1+1+1+1)(1+1+1)+1+1
Good Luck! - The Turtle
1>
n=20
) and 2) you say at the beginning that the integer complexity, which is distinct from the equation, has to be output, but you don't include that in any of the examples except the very first one.I'm still not clear. Do you just output the equation? – xnor – 2015-11-17T01:07:59.333
Yes. The integer complexity should not be outputted. I will also clarify that. Sorry for the mistakes. :( – The Turtle – 2015-11-17T01:08:36.630
Whoops, I said bullet #6 when I should've said bullet #5, in your requirements list. As for the other issue, thanks for fixing it. :) – El'endia Starman – 2015-11-17T01:14:42.897
1
Related: http://oeis.org/A005245 http://oeis.org/A061373 and finally http://oeis.org/A091333
– flawr – 2015-11-17T16:28:16.063