Numbers which are not the sum of distinct squares: Difference between revisions
Content added Content deleted
(Added Wren) |
|||
Line 75: | Line 75: | ||
{{out}} |
{{out}} |
||
<pre>2 3 6 7 8 11 12 15 18 19 22 23 24 27 28 31 32 33 43 44 47 48 60 67 72 76 92 96 108 112 128</pre> |
<pre>2 3 6 7 8 11 12 15 18 19 22 23 24 27 28 31 32 33 43 44 47 48 60 67 72 76 92 96 108 112 128</pre> |
||
=={{header|Wren}}== |
|||
Well I found a proof by induction [https://proofwiki.org/wiki/Numbers_not_Sum_of_Distinct_Squares here] that there are only a finite number of numbers satisfying this task but I don't see how we can prove it programatically without using a specialist language such as Agda or Coq. |
|||
So I've therefore used a brute force approach to generate the relevant numbers, similar to Julia, except using the same figures as the above proof. Still slow in Wren, around 20 seconds. |
|||
<lang ecmascript>var squares = (1..18).map { |i| i * i }.toList |
|||
var combs = [] |
|||
var results = [] |
|||
// generate combinations of the numbers 0 to n-1 taken m at a time |
|||
var combGen = Fn.new { |n, m| |
|||
var s = List.filled(m, 0) |
|||
var last = m - 1 |
|||
var rc // recursive closure |
|||
rc = Fn.new { |i, next| |
|||
var j = next |
|||
while (j < n) { |
|||
s[i] = j |
|||
if (i == last) { |
|||
combs.add(s.toList) |
|||
} else { |
|||
rc.call(i+1, j+1) |
|||
} |
|||
j = j + 1 |
|||
} |
|||
} |
|||
rc.call(0, 0) |
|||
} |
|||
for (n in 1..324) { |
|||
var all = true |
|||
for (m in 1..18) { |
|||
combGen.call(18, m) |
|||
for (comb in combs) { |
|||
var tot = (0...m).reduce(0) { |acc, i| acc + squares[comb[i]] } |
|||
if (tot == n) { |
|||
all = false |
|||
break |
|||
} |
|||
} |
|||
if (!all) break |
|||
combs.clear() |
|||
} |
|||
if (all) results.add(n) |
|||
} |
|||
System.print("Numbers which are not the sum of distinct squares:") |
|||
System.print(results)</lang> |
|||
{{out}} |
|||
<pre> |
|||
Numbers which are not the sum of distinct squares: |
|||
[2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128] |
|||
</pre> |