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 19:54, 24 November 2021
, 2 years ago→{{header|Phix}}
(Added Wren) |
|||
Line 55:
<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|Phix}}==
As per Raku (but this is using a simple flag array), if we find a block of n<sup><small>2</small></sup> summables,
that is guaranteed to become at least twice that length in the next step, and it will (eventually) overwrite any
subsequent holes, since it is longer than and overlaps the 2*n+1 gap between squares, at least that's my thinking...
You can run this online [http://phix.x10.mx/p2js/nsods.htm here].
<!--<lang Phix>(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">summable</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #004600;">true</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- (1 can be expressed as 1*1)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">sq</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span>
<span style="color: #000000;">summable</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sq</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- (process backwards to avoid adding sq more than once)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">summable</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">sq</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">summable</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">summable</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">sq</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">summable</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sq</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">match</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)*(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">summable</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- -- (next works too, but I'm not sure that's "proof")
-- integer r = match(repeat(true,sq),summable)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">summable</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">summable</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">r</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">nwansods</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"numbers which are not the sum of distinct squares"</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">find_all</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">summable</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">),</span><span style="color: #000000;">nwansods</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">))})</span>
<!--</lang>-->
{{out}}
<pre>
2 3 6 7 8 ... 92 96 108 112 128 (31 numbers which are not the sum of distinct squares)
</pre>
| |||