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 21:20, 26 November 2021
, 2 years ago→{{header|Wren}}: Added a quicker version, C# translation.
m (→{{header|Phix}}: added a "stricter termination test" comment) |
(→{{header|Wren}}: Added a quicker version, C# translation.) |
||
Line 275:
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.
===Brute force===
<lang ecmascript>var squares = (1..18).map { |i| i * i }.toList
var combs = []
Line 324 ⟶ 325:
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>
<br>
===Quicker===
{{trans|C#}}
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
Hugely quicker in fact - only 24 ms, the same as C# itself.
<lang ecmascript>import "./math" for Nums
import "./fmt" for Fmt
// recursively permutates the list of squares to seek a matching sum
var soms
soms = Fn.new { |n, f|
if (n <= 0) return false
if (f.contains(n)) return true
var sum = Nums.sum(f)
if (n > sum) return false
if (n == sum) return true
var rf = f[-1..0].skip(1).toList
return soms.call(n - f[-1], rf) || soms.call(n, rf)
}
var start = System.clock
var c = 0
var s = []
var a = []
var sf = "\nStopped checking after finding $d sequential non-gaps after the final gap of $d"
var i = 1
var g = 1
var r
while (g >= (i >> 1)) {
if ((r = i.sqrt.floor) * r == i) s.add(i)
if (!soms.call(i, s)) a.add(g = i)
i = i + 1
}
System.print("Numbers which are not the sum of distinct squares:")
System.print(a.join(", "))
Fmt.print(sf, i - g, g)
Fmt.print("Found $d total in $d ms.", a.count, ((System.clock - start)*1000).round)</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
Stopped checking after finding 130 sequential non-gaps after the final gap of 128
Found 31 total in 24 ms.
</pre>
| |||