Numbers which are not the sum of distinct squares: Difference between revisions
Content added Content deleted
m (→{{header|J}}: document) |
(Added solution for Modula-2) |
||
Line 328: | Line 328: | ||
{{out}} |
{{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> |
<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}}== |
=={{header|Nim}}== |