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 00:56, 6 October 2023
, 8 months agoAdded Quackery.
(New post.) |
(Added Quackery.) |
||
Line 949:
2 3 6 7 8 ... 92 96 108 112 128 (31 numbers which are not the sum of distinct squares)
</pre>
=={{header|Quackery}}==
<code>from</code>, <code>end</code>, and <code>incr</code> are defined at [[Loops/Increment loop index within loop body#Quackery]].
'''Method'''
We generate numbers which are the Sum Of Distinct Squares (SODS) up to N<sup>2</sup> by generating a list of the SODS up to (N-1)<sup>2</sup>, then adding each of those numbers + N<sup>2</sup> to the list. For N=0 the list is [0]. This method produces some duplicates along the way so after each iteration we remove any duplicates using <code>sort unique</code>. (<code>unique</code> requires a sorted list.)
As noted in other solutions, once there is a run longer than (N+1)<sup>2</sup>, all the subsequent numbers will be SODS. <code>missing</code> returns the length and position of the longest run. (After the last iteration, some SODS will be missing from the list after the longest run, but we can be confident that they will be found in further iterations as noted in other task solutions.) The length is used to test for when we can stop iterating, and the position tells us where we can trim the list.
Finally, <code>missing</code> generates a list of the numbers which are not SODS from the list of SODS. (This is why we need to trim the list; so it does not include the numbers which are SODS but had not yet been added to the list.)
<syntaxhighlight lang="Quackery"> [ stack ] is cut
[ -1 cut put
1 temp put
1 swap
behead swap
witheach
[ tuck - -1 =
iff
[ dip 1+
over temp share
> if [ over temp replace
i^ cut replace ] ]
else
[ nip 1 swap ] ]
2drop
temp take cut take ] is maxrun ( [ --> n n )
[ [] swap 0 over
witheach [ bit | ]
swap -1 peek times
[ dup i^ bit & not if
[ dip [ i^ join ] ] ]
drop ] is missing ( [ --> [ )
1 temp put
' [ 0 ]
1 from
[ dup witheach
[ temp share +
join ]
sort unique
dup maxrun drop
index 2 + temp tally
temp share > iff
end done
2 incr ]
temp release
dup maxrun
nip split
drop missing
say "Numbers that are not the sum of distinct squares:"
cr echo</syntaxhighlight>
{{out}}
<pre>Numbers that 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>
=={{header|Raku}}==
| |||