Numbers which are not the sum of distinct squares: Difference between revisions
Content added Content deleted
(Added Wren) |
|||
Line 55: | Line 55: | ||
<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] |
[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> |
</pre> |
||