Numbers which are not the sum of distinct squares: Difference between revisions
Content added Content deleted
(Added XPL0 example.) |
(Created Nim solution.) |
||
| Line 309: | Line 309: | ||
{{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|Nim}}== |
|||
{{trans|Wren, C#, Go}} |
|||
<syntaxhighlight lang="Nim">import std/[algorithm, math, monotimes, strformat, strutils, times] |
|||
proc soms(n: int; f: seq[int]): bool = |
|||
## Recursively permutates the list of squares to seek a matching sum. |
|||
if n <= 0: return false |
|||
if n in f: return true |
|||
case cmp(n, sum(f)) |
|||
of 1: |
|||
result = false |
|||
of 0: |
|||
result = true |
|||
else: |
|||
let rf = reversed(f.toOpenArray(0, f.len - 2)) |
|||
result = soms(n - f[^1], rf) or soms(n, rf) |
|||
let start = getMonoTime() |
|||
var s, a: seq[int] |
|||
var i, g = 1 |
|||
while g >= i shr 1: |
|||
let r = sqrt(i.toFloat).int |
|||
if r * r == i: s.add i |
|||
if not soms(i, s): |
|||
g = i |
|||
a.add g |
|||
inc i |
|||
echo "Numbers which are not the sum of distinct squares:" |
|||
echo a.join(" ") |
|||
echo &"\nStopped checking after finding {i - g} sequential non-gaps after the final gap of {g}." |
|||
echo &"Found {a.len} total in {(getMonotime() - start).inMicroseconds} µs." |
|||
</syntaxhighlight> |
|||
{{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 1536 µs. |
|||
</pre> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||