Numbers which are not the sum of distinct squares: Difference between revisions
Numbers which are not the sum of distinct squares (view source)
Revision as of 15:10, 24 November 2021
, 2 years agoAdded Wren
(Added Wren) |
|||
Line 75:
{{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>
=={{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>
| |||