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 20:27, 26 November 2021
, 2 years ago→{{header|Phix}}: added a "stricter termination test" comment
m (→{{header|Phix}}: clarified my thinking) |
m (→{{header|Phix}}: added a "stricter termination test" comment) |
||
Line 222:
As per Raku (but possibly using slightly different logic, and this is using a simple flag array), if we find there will be a block of n<sup><small>2</small></sup> summables,
and we are going to mark every one of those entries plus n<sup><small>2</small></sup> as summable, those regions will marry up or overlap and it is guaranteed to become at least twice that length in the next step, and all subsequent steps since 2*n<sup><small>2</small></sup> is also going to be longer than (n+1)<sup><small>2</small></sup> for all n>1, hence it will (eventually) mark everything beyond that point as summable. You can run this online [http://phix.x10.mx/p2js/nsods.htm here].
Strictly speaking the termination test should probably be <code>if r and sq>r then</code>, not that shaving off two pointless iterations makes any difference at all.
<!--<lang Phix>(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
| |||