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 22:53, 4 December 2021
, 2 years ago→{{header|jq}}
(→{{header|C#|CSharp}}: added Alternative version) |
|||
Line 116:
found 31 total in 9.9693 ms
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}}==
Line 141 ⟶ 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]
</pre>
=={{header|Pascal}}==
==={{header|Free Pascal}}===
| |||