Numbers which are not the sum of distinct squares: Difference between revisions
Content added Content deleted
(→{{header|C#|CSharp}}: added Alternative version) |
|||
Line 116: | Line 116: | ||
found 31 total in 9.9693 ms |
found 31 total in 9.9693 ms |
||
stopped checking after finding 128 sequential non-gaps after the final gap of 128</pre> |
stopped checking after finding 128 sequential non-gaps after the final gap of 128</pre> |
||
=={{header|jq}}== |
|||
{{works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
The following program is directly based on the "Spoiler" observation at [[#Raku|Raku]]. |
|||
In effect, therefore, it computes the "magic number". |
|||
It is nevertheless quite fast: on a 3GHz machine, u+s ~ 32ms using either the C or Go implementation of jq. |
|||
Since the implementation is based on generic concepts (such as runs), the |
|||
helper functions are potentially independently useful. |
|||
<lang jq>#def squares: range(1; infinite) | . * .; |
|||
# sums of distinct squares (sods) |
|||
# Output: a stream of [$n, $sums] where $sums is the array of sods based on $n |
|||
def sods: |
|||
# input: [$n, $sums] |
|||
def next: |
|||
. as [$n, $sums] |
|||
| (($n+1)*($n+1)) as $next |
|||
| reduce $sums[] as $s ($sums + [$next]; |
|||
if index($s + $next) then . else . + [$s + $next] end) |
|||
| [$n + 1, unique]; |
|||
[1, [1]] |
|||
| recurse(next); |
|||
# Input: an array |
|||
# Output: the length of the run beginning at $n |
|||
def length_of_run($n): |
|||
label $out |
|||
| (range($n+1; length),null) as $i |
|||
| if $i == null then (length-$n) |
|||
elif .[$i] == .[$i-1] + 1 then empty |
|||
else $i-$n, break $out |
|||
end; |
|||
# Input: an array |
|||
def length_of_longest_run: |
|||
. as $in |
|||
| first( |
|||
foreach (range(0; length),null) as $i (0; |
|||
if $i == null then . |
|||
else ($in|length_of_run($i)) as $n |
|||
| if $n > . then $n else . end |
|||
end; |
|||
if $i == null or (($in|length) - $i) < . then . else empty end) ); |
|||
def sq: .*.; |
|||
# Output: [$ix, $length] |
|||
def relevant_sods: |
|||
first( |
|||
sods |
|||
| . as [$n, $s] |
|||
| ($s|length_of_longest_run) as $length |
|||
| if $length > ($n+1|sq) then . else empty end ); |
|||
def not_sum_of_distinct_squares: |
|||
relevant_sods |
|||
| . as [$ix, $sods] |
|||
| [range(2; $ix+2|sq)] - $sods; |
|||
not_sum_of_distinct_squares</lang> |
|||
{{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|Julia}}== |
=={{header|Julia}}== |
||
Line 141: | Line 209: | ||
[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> |
</pre> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
==={{header|Free Pascal}}=== |
==={{header|Free Pascal}}=== |