| 1 |
/*** |
| 2 |
!Test |
| 3 |
expected: |
| 4 |
- !Result |
| 5 |
solution: !Solution |
| 6 |
objective: 337561 |
| 7 |
***/ |
| 8 |
|
| 9 |
% perfsq2.mzn |
| 10 |
% vim: ft=zinc ts=4 sw=4 et |
| 11 |
% |
| 12 |
% Perfect squares: find a square equal to the sum of smaller, distinct squares. |
| 13 |
|
| 14 |
int: n = 100; |
| 15 |
|
| 16 |
% x[k] = 1 iff k^2 is part of the sum. |
| 17 |
% |
| 18 |
array [1..n] of var 0..1: x; |
| 19 |
|
| 20 |
% t is the sum of the first n squares, the largest value our sum can have. |
| 21 |
% |
| 22 |
int: t = ((n * (n + 1) * (2 * n + 1)) div 6); |
| 23 |
|
| 24 |
% squares is the set of square numbers less than t. |
| 25 |
% |
| 26 |
set of int: squares = {i * i | i in 1..(n * n) where i * i <= t}; |
| 27 |
|
| 28 |
% k is the sum of the squares selected by the x[i]. |
| 29 |
% |
| 30 |
var squares: k = sum (i in 1..n) (i * i * x[i]); |
| 31 |
|
| 32 |
solve maximize(k); |
| 33 |
|
| 34 |
output [show(k), "\n"]; |
| 35 |
|
| 36 |
% output |
| 37 |
% [ show(k), " = sum of " |
| 38 |
% ] ++ |
| 39 |
% [ if fix(x[i]) = 1 then show(i * i) ++ " " else "" endif |
| 40 |
% | i in 1..n |
| 41 |
% ] ++ |
| 42 |
% [ "\n" |
| 43 |
% ]; |