Decompose integer into sum of squares

Submit

Your name:
File:
Open code-statistics:

Language is selected by the extension of the file. See the list of supported languages to know the extension of your language.

Problem

Express each integer from 1 to 300 as the sum of at most 4 squares.

Format:
n: a b c d
where n = a^2+b^2+c^2+d^2

Note:
It is possible to express some numbers as the sum of squares more than one way. In this case, use the one that uses less squares. ex:

"18: 3 3" instead of "18: 4 1 1"
(2 squares instead of 3)

If there is more than one way with the same amount of squares, use the one where a+b+c+d is least. ex:

"28: 5 1 1 1" instead of "28: 4 2 2 2"
(5+1+1+1 < 4+2+2+2)

Options

exec is denied

now post-mortem time, all source codes will be revealed

Sample input:_

*NOTHING*

Sample output:

1: 1
2: 1 1
3: 1 1 1
4: 2
5: 2 1
6: 2 1 1
7: 2 1 1 1
8: 2 2
9: 3
10: 3 1
11: 3 1 1
12: 2 2 2
13: 3 2
14: 3 2 1
15: 3 2 1 1
16: 4
17: 4 1
18: 3 3
19: 3 3 1
20: 4 2
21: 4 2 1
22: 3 3 2
23: 3 3 2 1
24: 4 2 2
25: 5
26: 5 1
27: 5 1 1
28: 5 1 1 1
29: 5 2
30: 5 2 1
31: 5 2 1 1
32: 4 4
33: 4 4 1
34: 5 3
35: 5 3 1
36: 6
37: 6 1
38: 6 1 1
39: 6 1 1 1
40: 6 2
41: 5 4
42: 5 4 1
43: 5 3 3
44: 6 2 2
45: 6 3
46: 6 3 1
47: 6 3 1 1
48: 4 4 4
49: 7
50: 7 1
51: 7 1 1
52: 6 4
53: 7 2
54: 7 2 1
55: 7 2 1 1
56: 6 4 2
57: 7 2 2
58: 7 3
59: 7 3 1
60: 7 3 1 1
61: 6 5
62: 6 5 1
63: 6 5 1 1
64: 8
65: 8 1
66: 8 1 1
67: 7 3 3
68: 8 2
69: 8 2 1
70: 6 5 3
71: 6 5 3 1
72: 6 6
73: 8 3
74: 7 5
75: 7 5 1
76: 6 6 2
77: 8 3 2
78: 7 5 2
79: 7 5 2 1
80: 8 4
81: 9
82: 9 1
83: 9 1 1
84: 8 4 2
85: 9 2
86: 9 2 1
87: 9 2 1 1
88: 6 6 4
89: 8 5
90: 9 3
91: 9 3 1
92: 9 3 1 1
93: 8 5 2
94: 9 3 2
95: 9 3 2 1
96: 8 4 4
97: 9 4
98: 7 7
99: 7 7 1
100: 10
101: 10 1
102: 10 1 1
103: 10 1 1 1
104: 10 2
105: 10 2 1
106: 9 5
107: 9 5 1
108: 10 2 2
109: 10 3
110: 10 3 1
111: 10 3 1 1
112: 10 2 2 2
113: 8 7
114: 8 7 1
115: 9 5 3
116: 10 4
117: 9 6
118: 9 6 1
119: 9 6 1 1
120: 10 4 2
121: 11
122: 11 1
123: 11 1 1
124: 11 1 1 1
125: 11 2
126: 11 2 1
127: 11 2 1 1
128: 8 8
129: 8 8 1
130: 11 3
131: 11 3 1
132: 8 8 2
133: 9 6 4
134: 11 3 2
135: 11 3 2 1
136: 10 6
137: 11 4
138: 11 4 1
139: 11 3 3
140: 10 6 2
141: 11 4 2
142: 9 6 5
143: 9 6 5 1
144: 12
145: 12 1
146: 11 5
147: 11 5 1
148: 12 2
149: 10 7
150: 10 7 1
151: 10 7 1 1
152: 12 2 2
153: 12 3
154: 12 3 1
155: 11 5 3
156: 11 5 3 1
157: 11 6
158: 11 6 1
159: 11 6 1 1
160: 12 4
161: 12 4 1
162: 9 9
163: 9 9 1
164: 10 8
165: 10 8 1
166: 9 9 2
167: 9 9 2 1
168: 10 8 2
169: 13
170: 13 1
171: 13 1 1
172: 10 6 6
173: 13 2
174: 13 2 1
175: 13 2 1 1
176: 12 4 4
177: 13 2 2
178: 13 3
179: 13 3 1
180: 12 6
181: 10 9
182: 10 9 1
183: 10 9 1 1
184: 12 6 2
185: 13 4
186: 13 4 1
187: 13 3 3
188: 13 3 3 1
189: 13 4 2
190: 10 9 3
191: 10 9 3 1
192: 8 8 8
193: 12 7
194: 13 5
195: 13 5 1
196: 14
197: 14 1
198: 14 1 1
199: 14 1 1 1
200: 14 2
201: 14 2 1
202: 11 9
203: 11 9 1
204: 14 2 2
205: 14 3
206: 14 3 1
207: 14 3 1 1
208: 12 8
209: 12 8 1
210: 13 5 4
211: 11 9 3
212: 14 4
213: 14 4 1
214: 14 3 3
215: 14 3 3 1
216: 14 4 2
217: 12 8 3
218: 13 7
219: 13 7 1
220: 13 7 1 1
221: 14 5
222: 14 5 1
223: 14 5 1 1
224: 12 8 4
225: 15
226: 15 1
227: 15 1 1
228: 14 4 4
229: 15 2
230: 15 2 1
231: 15 2 1 1
232: 14 6
233: 13 8
234: 15 3
235: 15 3 1
236: 14 6 2
237: 13 8 2
238: 15 3 2
239: 15 3 2 1
240: 14 6 2 2
241: 15 4
242: 11 11
243: 11 11 1
244: 12 10
245: 14 7
246: 14 7 1
247: 14 7 1 1
248: 12 10 2
249: 14 7 2
250: 15 5
251: 15 5 1
252: 15 5 1 1
253: 12 10 3
254: 15 5 2
255: 15 5 2 1
256: 16
257: 16 1
258: 16 1 1
259: 15 5 3
260: 16 2
261: 15 6
262: 15 6 1
263: 15 6 1 1
264: 16 2 2
265: 16 3
266: 16 3 1
267: 11 11 5
268: 14 6 6
269: 13 10
270: 13 10 1
271: 13 10 1 1
272: 16 4
273: 16 4 1
274: 15 7
275: 15 7 1
276: 16 4 2
277: 14 9
278: 14 9 1
279: 14 9 1 1
280: 12 10 6
281: 16 5
282: 16 5 1
283: 15 7 3
284: 15 7 3 1
285: 16 5 2
286: 14 9 3
287: 14 9 3 1
288: 12 12
289: 17
290: 17 1
291: 17 1 1
292: 16 6
293: 17 2
294: 17 2 1
295: 17 2 1 1
296: 14 10
297: 14 10 1
298: 17 3
299: 17 3 1
300: 14 10 2

Ranking

Ruby _

RankUserSizeTimeDateStatistics
1samuil1120.85792009/07/21 21:29:500B / 43B / 62B
2wrong output?("129: 11 2 2" is better, etc.)4580.22922009/07/12 16:43:1724B / 169B / 168B

Perl _

RankUserSizeTimeDateStatistics
1sugyan1810.44992009/07/17 07:38:030B / 77B / 97B
2Songmu2830.29882009/07/24 00:31:190B / 110B / 162B
3hobbs1530.43812009/10/21 19:44:250B / ?B / ?B

Python _

RankUserSizeTimeDateStatistics
1Seth Troisi slower1950.02482010/01/11 14:22:150B / ?B / ?B
2Seth Troisi2200.01962010/01/11 13:55:550B / ?B / ?B

Common LISP _

RankUserSizeTimeDateStatistics
1kozima1732.06032010/01/12 09:28:080B / 82B / 73B

JavaScript _

RankUserSizeTimeDateStatistics
1nn1170.71522009/07/22 08:33:460B / 52B / 63B

J _

RankUserSizeTimeDateStatistics
1I., S.(brute force)750.66162011/05/19 22:13:520B / 13B / 61B

C _

RankUserSizeTimeDateStatistics
1su1660.00022009/07/15 23:17:520B / 78B / 86B
251b1670.01542009/07/21 23:09:120B / 78B / 88B
3sa2250.15982009/07/12 14:50:120B / ?B / ?B

C++ _

RankUserSizeTimeDateStatistics
1sa2420.20972009/07/12 14:45:420B / ?B / ?B

D _

RankUserSizeTimeDateStatistics
151b1670.05062009/07/26 00:50:340B / 92B / 71B

OCaml _

RankUserSizeTimeDateStatistics
1ksk(wrong)1750.37792009/10/09 00:52:310B / 89B / 81B
2xsd1821.06252009/10/08 23:33:370B / 100B / 70B

AWK _

RankUserSizeTimeDateStatistics
1nn1090.26522009/07/21 20:10:070B / 54B / 53B

Postscript _

RankUserSizeTimeDateStatistics
1yshl(bin)1220.48982009/07/22 02:19:2954B / 47B / 20B
2yshl2280.46982009/07/22 02:19:220B / 165B / 24B

goruby _

RankUserSizeTimeDateStatistics
1samuil1021.25952009/07/21 22:19:310B / 33B / 62B

Groovy _

RankUserSizeTimeDateStatistics
1nn1212.06052009/11/20 10:53:060B / 47B / 70B

Language Ranking_

RankLangUserSizeScore
1JI., S.(brute force)7510000
2gorubysamuil1027352
3AWKnn1096880
4Rubysamuil1126696
5JavaScriptnn1176410
6Groovynn1216198
7Postscriptyshl(bin)1226147
8Perlhobbs1534901
9Csu1664518
10D51b1674491
11Common LISPkozima1734335
12OCamlksk(wrong)1754285
13PythonSeth Troisi slower1953846
14C++sa2423099

return top