Numbers which are not the sum of distinct squares: Difference between revisions

Content added Content deleted
Line 36: Line 36:
Recursive brute force (tempting though it is to use 9 nested loops... :) ), using the proof that if 129-324 can be expressed as the sum of distinct squares, then all integers greater than 128 can be so expressed - see the link in the Wren sample.
Recursive brute force (tempting though it is to use 9 nested loops... :) ), using the proof that if 129-324 can be expressed as the sum of distinct squares, then all integers greater than 128 can be so expressed - see the link in the Wren sample.
<syntaxhighlight lang="algol68">
<syntaxhighlight lang="algol68">
BEGIN # find the integers that can't be expressed as the sum of distinct squares #
CO find the integers that can't be expressed as the sum of distinct squares
# it can be proved that if 120-324 can be expressed as the sum of distinct #
it can be proved that if 120-324 can be expressed as the sum of distinct
# then all integers greater than 129 can be so expressed (see the link in #
squares then all integers greater than 129 can be so expressed
# the Wren sample) so we need to check that 129-324 can be so expressed #
(see the link in the Wren sample) so we need to check that 129-324 can
# and find the numbers below 129 that can't be so expressed #
be so expressed and find the numbers below 129 that can't be so expressed
CO
BEGIN
INT max number = 324;
INT max number = 324;
[ 0 : max number ]BOOL is sum; FOR i FROM LWB is sum TO UPB is sum DO is sum[ i ] := FALSE OD;
[ 0 : max number ]BOOL is sum; FOR i FROM LWB is sum TO UPB is sum DO is sum[ i ] := FALSE OD;
Retrieved from "https://rosettacode.org/wiki/Numbers_which_are_not_the_sum_of_distinct_squares"