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 11:03, 11 May 2023
, 1 year agoAdded solution for Modula-2
m (→{{header|J}}: document) |
(Added solution for Modula-2) |
||
Line 328:
{{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|Modula-2}}==
{{works with|XDS Modula-2}}
Mathematical justification is provided in part by the ProofWiki article "Numbers not Sum of Distinct Squares" linked from the Wren solution. It's shown that if
(1) every integer in the range 129..324 (= 18^2) can be expressed as a sum of distinct squares, then
(2) every integer from 129 onwards can be so expressed.
However, the author leaves the reader to complete the proof of (2) by verifying (1). The program therefore needs to do that, but needn't consider integers greater than 324.
<syntaxhighlight lang="modula2">
MODULE NotSumDistinctSq;
FROM InOut IMPORT WriteString, WriteLn, WriteCard;
VAR
sds : ARRAY [0..324] OF BOOLEAN; (* sum of distinct squares? *)
j, k, r, rsq, max_true, start, nr_in_line : CARDINAL;
BEGIN
sds[0] := TRUE;
FOR j := 1 TO 324 DO sds[j] := FALSE; END;
max_true := 0; (* maximum index for which sds is TRUE *)
FOR r := 1 TO 18 DO
rsq := r*r;
(* NB Work backwards, so that the only TRUE values found
are those set up by previous values of r. *)
start := 324 - rsq;
IF start > max_true THEN start := max_true; END;
FOR j := start TO 0 BY -1 DO
IF sds[j] THEN
k := j + rsq;
sds[k] := TRUE;
IF k > max_true THEN max_true := k; END;
END;
END;
END;
(* Verify that all integers 129..324 are sums of distinct squares *)
j := 129;
WHILE (j <= 324) AND sds[j] DO INC(j); END;
IF j <= 324 THEN
WriteString( "*** Verification failed ***");
RETURN;
END;
(* Print the result *)
WriteString( "Positive integers not the sum of distinct squares");
WriteLn;
nr_in_line := 0;
FOR j := 0 TO 128 DO
IF NOT sds[j] THEN
IF nr_in_line = 12 THEN
WriteLn; nr_in_line := 0;
END;
WriteCard(j, 4);
INC( nr_in_line);
END;
END;
END NotSumDistinctSq.
</syntaxhighlight>
{{out}}
<pre>
Positive integers 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|Nim}}==
| |||