Numbers which are not the sum of distinct squares: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: added a "stricter termination test" comment) |
(→{{header|Wren}}: Added a quicker version, C# translation.) |
||
Line 275: | 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. |
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=== |
|||
This uses 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 |
<lang ecmascript>var squares = (1..18).map { |i| i * i }.toList |
||
var combs = [] |
var combs = [] |
||
Line 324: | Line 325: | ||
Numbers which are not the sum of distinct squares: |
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] |
[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> |
</pre> |