Integer Complexity

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:

  1. The program must take as input a positive natural number n.
  2. Output must be in this format: 20 = ((1+1+1)(1+1+1)+1)(1+1)
  3. Your output may not have needless parentheses, like 8 = ((1+1)(1+1))(1+1).
  4. The multiplication sign * is optional.
  5. Spaces are optional.
  6. 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 or 4=(1+1)(1+1). You don't have to output both.
  7. 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

The Turtle

Posted 2015-11-17T00:31:40.497

Reputation: 858

1>

  • Your bullet #6 is not finished (it's missing the example output for 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.
    • < – El'endia Starman – 2015-11-17T00:56:50.003

    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

    Answers

    10

    Pyth, 60 bytes

    LjWqeb\1b`()L?tbho/N\1++'tb"+1"m+y'/bdy'df!%bTr2b1VSQ++N\='N

    Demonstration

    The online compiler can reach 1223 before the time out, thanks to Pyth's automatic function memoization.

    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

    In abbrieviated notaion,

    1223=(3^5+1)*5+3

    This uses a recursive function ', which calculates all possbile products and sums which could give the desired output, finds the shortest string with each final operation, then compares them by 1 count and returns the first one.

    It uses a helper function, y, which parenthesizes an expression only if it needs to be parenthesized.

    Offline, I am running the program with the input 15535, and it is nearly complete. Results are printed incrementally, so it is easy to see the progress.

    Final lines of the output:

    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

real    7m8.430s
user    7m7.158s
sys 0m0.945s

    In abbreviated notation,

    15535=(((3^4+1)*(3*2+1)+1)*3+1)*3^2+1

    isaacg

    Posted 2015-11-17T00:31:40.497

    Reputation: 39 268

    7

    CJam, 105 102 98 96 bytes

    q~{)'=1$2,{:I{I1$-'+}%3/1>Imf'*+aImp!*+{)\{j}%\+}:F%{e_"+*"-:+}$0=}j2,{F)_'*={;{'(\')}%1}&*}jN}/

    Try it online in the CJam interpreter.

    Test run

    The online interpreter is too slow for the larger test cases. Even with the Java interpreter, the larger test cases will take a long time and require a significant amount of memory.

    $ time cjam integer-complexity.cjam <<< 157
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)
21=(1+1+1)(1+(1+1)(1+1+1))
22=1+(1+1+1)(1+(1+1)(1+1+1))
23=1+1+(1+1+1)(1+(1+1)(1+1+1))
24=(1+1)(1+1)(1+1)(1+1+1)
25=1+(1+1)(1+1)(1+1)(1+1+1)
26=(1+1)(1+(1+1)(1+1)(1+1+1))
27=(1+1+1)(1+1+1)(1+1+1)
28=1+(1+1+1)(1+1+1)(1+1+1)
29=1+1+(1+1+1)(1+1+1)(1+1+1)
30=(1+1)(1+1+1)(1+1+1+1+1)
31=1+(1+1)(1+1+1)(1+1+1+1+1)
32=(1+1)(1+1)(1+1)(1+1)(1+1)
33=1+(1+1)(1+1)(1+1)(1+1)(1+1)
34=(1+1)(1+(1+1)(1+1)(1+1)(1+1))
35=(1+1+1+1+1)(1+(1+1)(1+1+1))
36=(1+1)(1+1)(1+1+1)(1+1+1)
37=1+(1+1)(1+1)(1+1+1)(1+1+1)
38=(1+1)(1+(1+1)(1+1+1)(1+1+1))
39=(1+1+1)(1+(1+1)(1+1)(1+1+1))
40=(1+1)(1+1)(1+1)(1+1+1+1+1)
41=1+(1+1)(1+1)(1+1)(1+1+1+1+1)
42=(1+1)(1+1+1)(1+(1+1)(1+1+1))
43=1+(1+1)(1+1+1)(1+(1+1)(1+1+1))
44=(1+1)(1+1)(1+1+(1+1+1)(1+1+1))
45=(1+1+1)(1+1+1)(1+1+1+1+1)
46=1+(1+1+1)(1+1+1)(1+1+1+1+1)
47=1+1+(1+1+1)(1+1+1)(1+1+1+1+1)
48=(1+1)(1+1)(1+1)(1+1)(1+1+1)
49=1+(1+1)(1+1)(1+1)(1+1)(1+1+1)
50=(1+1)(1+1+1+1+1)(1+1+1+1+1)
51=(1+1+1)(1+(1+1)(1+1)(1+1)(1+1))
52=(1+1)(1+1)(1+(1+1)(1+1)(1+1+1))
53=1+(1+1)(1+1)(1+(1+1)(1+1)(1+1+1))
54=(1+1)(1+1+1)(1+1+1)(1+1+1)
55=1+(1+1)(1+1+1)(1+1+1)(1+1+1)
56=(1+1)(1+1)(1+1)(1+(1+1)(1+1+1))
57=(1+1+1)(1+(1+1)(1+1+1)(1+1+1))
58=1+(1+1+1)(1+(1+1)(1+1+1)(1+1+1))
59=1+1+(1+1+1)(1+(1+1)(1+1+1)(1+1+1))
60=(1+1)(1+1)(1+1+1)(1+1+1+1+1)
61=1+(1+1)(1+1)(1+1+1)(1+1+1+1+1)
62=(1+1)(1+(1+1)(1+1+1)(1+1+1+1+1))
63=(1+1+1)(1+1+1)(1+(1+1)(1+1+1))
64=(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)
65=1+(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)
66=(1+1)(1+1+1)(1+1+(1+1+1)(1+1+1))
67=1+(1+1)(1+1+1)(1+1+(1+1+1)(1+1+1))
68=(1+1)(1+1)(1+(1+1)(1+1)(1+1)(1+1))
69=1+(1+1)(1+1)(1+(1+1)(1+1)(1+1)(1+1))
70=(1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
71=1+(1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
72=(1+1)(1+1)(1+1)(1+1+1)(1+1+1)
73=1+(1+1)(1+1)(1+1)(1+1+1)(1+1+1)
74=(1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1))
75=(1+1+1)(1+1+1+1+1)(1+1+1+1+1)
76=(1+1)(1+1)(1+(1+1)(1+1+1)(1+1+1))
77=1+(1+1)(1+1)(1+(1+1)(1+1+1)(1+1+1))
78=(1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))
79=1+(1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))
80=(1+1)(1+1)(1+1)(1+1)(1+1+1+1+1)
81=(1+1+1)(1+1+1)(1+1+1)(1+1+1)
82=1+(1+1+1)(1+1+1)(1+1+1)(1+1+1)
83=1+1+(1+1+1)(1+1+1)(1+1+1)(1+1+1)
84=(1+1)(1+1)(1+1+1)(1+(1+1)(1+1+1))
85=1+(1+1)(1+1)(1+1+1)(1+(1+1)(1+1+1))
86=(1+1)(1+(1+1)(1+1+1)(1+(1+1)(1+1+1)))
87=(1+1+1)(1+1+(1+1+1)(1+1+1)(1+1+1))
88=(1+1)(1+1)(1+1)(1+1+(1+1+1)(1+1+1))
89=1+(1+1)(1+1)(1+1)(1+1+(1+1+1)(1+1+1))
90=(1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
91=1+(1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
92=1+1+(1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
93=(1+1+1)(1+(1+1)(1+1+1)(1+1+1+1+1))
94=1+(1+1+1)(1+(1+1)(1+1+1)(1+1+1+1+1))
95=(1+1+1+1+1)(1+(1+1)(1+1+1)(1+1+1))
96=(1+1)(1+1)(1+1)(1+1)(1+1)(1+1+1)
97=1+(1+1)(1+1)(1+1)(1+1)(1+1)(1+1+1)
98=(1+1)(1+(1+1)(1+1+1))(1+(1+1)(1+1+1))
99=(1+1+1)(1+1+1)(1+1+(1+1+1)(1+1+1))
100=(1+1)(1+1)(1+1+1+1+1)(1+1+1+1+1)
101=1+(1+1)(1+1)(1+1+1+1+1)(1+1+1+1+1)
102=(1+1)(1+1+1)(1+(1+1)(1+1)(1+1)(1+1))
103=1+(1+1)(1+1+1)(1+(1+1)(1+1)(1+1)(1+1))
104=(1+1)(1+1)(1+1)(1+(1+1)(1+1)(1+1+1))
105=(1+1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
106=1+(1+1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
107=1+1+(1+1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
108=(1+1)(1+1)(1+1+1)(1+1+1)(1+1+1)
109=1+(1+1)(1+1)(1+1+1)(1+1+1)(1+1+1)
110=1+1+(1+1)(1+1)(1+1+1)(1+1+1)(1+1+1)
111=(1+1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1))
112=(1+1)(1+1)(1+1)(1+1)(1+(1+1)(1+1+1))
113=1+(1+1)(1+1)(1+1)(1+1)(1+(1+1)(1+1+1))
114=(1+1)(1+1+1)(1+(1+1)(1+1+1)(1+1+1))
115=1+(1+1)(1+1+1)(1+(1+1)(1+1+1)(1+1+1))
116=(1+1)(1+1)(1+1+(1+1+1)(1+1+1)(1+1+1))
117=(1+1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))
118=1+(1+1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))
119=(1+(1+1)(1+1+1))(1+(1+1)(1+1)(1+1)(1+1))
120=(1+1)(1+1)(1+1)(1+1+1)(1+1+1+1+1)
121=1+(1+1)(1+1)(1+1)(1+1+1)(1+1+1+1+1)
122=(1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1+1+1))
123=(1+1+1)(1+(1+1)(1+1)(1+1)(1+1+1+1+1))
124=(1+1)(1+1)(1+(1+1)(1+1+1)(1+1+1+1+1))
125=(1+1+1+1+1)(1+1+1+1+1)(1+1+1+1+1)
126=(1+1)(1+1+1)(1+1+1)(1+(1+1)(1+1+1))
127=1+(1+1)(1+1+1)(1+1+1)(1+(1+1)(1+1+1))
128=(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)
129=1+(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)
130=(1+1)(1+1+1+1+1)(1+(1+1)(1+1)(1+1+1))
131=1+(1+1)(1+1+1+1+1)(1+(1+1)(1+1)(1+1+1))
132=(1+1)(1+1)(1+1+1)(1+1+(1+1+1)(1+1+1))
133=(1+(1+1)(1+1+1))(1+(1+1)(1+1+1)(1+1+1))
134=1+(1+(1+1)(1+1+1))(1+(1+1)(1+1+1)(1+1+1))
135=(1+1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
136=1+(1+1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
137=1+1+(1+1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
138=(1+1)(1+1+1)(1+1+(1+1+1)(1+(1+1)(1+1+1)))
139=1+(1+1)(1+1+1)(1+1+(1+1+1)(1+(1+1)(1+1+1)))
140=(1+1)(1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
141=1+(1+1)(1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
142=(1+1)(1+(1+1)(1+1+1+1+1)(1+(1+1)(1+1+1)))
143=(1+1+(1+1+1)(1+1+1))(1+(1+1)(1+1)(1+1+1))
144=(1+1)(1+1)(1+1)(1+1)(1+1+1)(1+1+1)
145=1+(1+1)(1+1)(1+1)(1+1)(1+1+1)(1+1+1)
146=(1+1)(1+(1+1)(1+1)(1+1)(1+1+1)(1+1+1))
147=(1+1+1)(1+(1+1)(1+1+1))(1+(1+1)(1+1+1))
148=(1+1)(1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1))
149=1+(1+1)(1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1))
150=(1+1)(1+1+1)(1+1+1+1+1)(1+1+1+1+1)
151=1+(1+1)(1+1+1)(1+1+1+1+1)(1+1+1+1+1)
152=(1+1)(1+1)(1+1)(1+(1+1)(1+1+1)(1+1+1))
153=(1+1+1)(1+1+1)(1+(1+1)(1+1)(1+1)(1+1))
154=1+(1+1+1)(1+1+1)(1+(1+1)(1+1)(1+1)(1+1))
155=(1+1+1+1+1)(1+(1+1)(1+1+1)(1+1+1+1+1))
156=(1+1)(1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))
157=1+(1+1)(1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))

real    0m3.896s
user    0m4.892s
sys     0m0.066s

    Given enough time, it would produce these solutions for the next test cases:

    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))

    Dennis

    Posted 2015-11-17T00:31:40.497

    Reputation: 196 637

    How does it work? – flawr – 2015-11-17T10:35:35.483

    @flawr I'm still hoping to golf this a bit more. I'll add an explanation when I am done/give up. – Dennis – 2015-11-17T16:11:55.987

    4

    Julia, 229 bytes

    n->(F=i->K[i]>0?E[i]:"("E[i]")";C=[1;3:n+1];K=0C;E=fill("1",n);for s=1:n for i=1:s÷2 (D=C[i]+C[s-i])<C[s]?(C[s]=D;E[s]=E[i]"+"E[s-i];K[s]=0):s%i>0||(D=C[i]+C[j=s÷i])<C[s]&&(C[s]=D;E[s]=F(i)F(j);K[s]=1)end;println("$s="E[s])end)

    This is actually pretty fast. Assigning the function to f and running @time f(15535) gives the output (last two lines only)

    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))))
32.211583 seconds (263.30 M allocations: 4.839 GB, 4.81% gc time)

    and for @time f(45197), it gives

    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))))
289.749564 seconds (2.42 G allocations: 43.660 GB, 4.91% gc time)

    So, what's the code doing? Simple - C holds the current one-Count for the number, K is an indicator array keeping track of whether the expression is, fundamentally, a sum or a product, for the purposes of dealing with bracketing, and E holds the Expression itself. Working its way up from s=1 through to n, the code searches for the minimal representation of number s in terms of lower values, by looking for either a sum or a product. If it's a product, then it checks the two components and puts brackets around them if they're sums. That check is done in function F, to save bytes (because it has to be done twice, for the two factors).

    Glen O

    Posted 2015-11-17T00:31:40.497

    Reputation: 2 548

    Asked: 2015-11-17T00:31:40.497

    Viewed: 1 248 times

    Active: 2015-11-17T16:33:52.303