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 16:52, 7 January 2024
, 4 months ago→{{header|Wren}}: Changed to Wren S/H
m (→{{header|Wren}}: Changed to Wren S/H) |
|||
| (22 intermediate revisions by 12 users not shown) | |||
Line 32:
* [[oeis:A001422|OEIS: A001422 Numbers which are not the sum of distinct squares]]
=={{header|ALGOL 68}}==
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">
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
squares then all integers greater than 129 can be so expressed
(see the link in the Wren sample) so we need to check that 129-324 can
be so expressed and find the numbers below 129 that can't be so expressed
CO
BEGIN
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;
INT max square = ENTIER sqrt( 324 );
[ 0 : max square ]INT square; FOR i FROM LWB square TO UPB square DO square[ i ] := i * i OD;
PROC flag sum = ( INT curr sum, sq pos )VOID:
IF INT next sum = curr sum + square[ sq pos ];
next sum <= UPB is sum
THEN
is sum[ next sum ] := TRUE;
FOR i FROM sq pos + 1 TO UPB square DO
flag sum( next sum, i )
OD
FI # flag sum # ;
FOR i FROM LWB square TO UPB square DO
flag sum( 0, i )
OD;
# show the numbers that can't be formed from a sum of distinct squares #
# and check 129-324 can be so formed #
INT unformable := 0;
FOR i FROM LWB is sum TO UPB is sum DO
IF NOT is sum[ i ] THEN
print( ( whole( i, -4 ) ) );
IF ( unformable +:= 1 ) MOD 12 = 0 THEN print( ( newline ) ) FI;
IF i > 128 THEN
print( ( newline, "**** unexpected unformable number: ", whole( i, 0 ), newline ) )
FI
FI
OD
END
</syntaxhighlight>
{{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|ALGOL W}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="algolw">
begin comment 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
squares then all integers greater than 129 can be so expressed
(see the link in the Wren sample) so we need to check that 129-324 can
be so expressed and find the numbers below 129 that can't be so expressed
;
integer MAX_NUMBER, MAX_SQUARE;
MAX_NUMBER := 324;
MAX_SQUARE := entier( sqrt( MAX_NUMBER ) );
begin
logical array isSum ( 0 :: MAX_NUMBER );
integer array square ( 0 :: MAX_SQUARE );
integer unformable;
procedure flagSum ( integer value currSum, sqPos ) ; begin
integer nextSum;
nextSum := currSum + square( sqPos );
if nextSum <= MAX_NUMBER then begin
isSum( nextSum ) := true;
for i := sqPos + 1 until MAX_SQUARE do flagSum( nextSum, i )
end of_nextSum_le_MAX_NUMBER
end flagSum ;
for i := 0 until MAX_NUMBER do isSum( i ) := false;
for i := 0 until MAX_SQUARE do square( i ) := i * i;
for i := 0 until MAX_SQUARE do flagSum( 0, i );
% show the numbers that can't be formed from a sum of distinct squares %
% and check 129-324 can be so formed %
unformable := 0;
for i := 0 until MAX_NUMBER do
if not isSum( i ) then begin
writeon( i_w := 4, s_w := 0, i );
unformable := unformable + 1;
if unformable rem 12 = 0 then write();
if i > 128 then write( i_w := 1, s_w := 0, "**** unexpected unformable number: ", i )
end if_not_isSum__i
end
end.
</syntaxhighlight>
{{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|C#|CSharp}}==
Following in the example set by the '''Free Pascal''' entry for this task, this C# code is re-purposed from [[Practical_numbers#C#]].<br>
It seems that finding as many (or more) contiguous numbers-that-''are''-the-sum-of-distinct-squares as the highest found gap demonstrates that there is no higher gap, since there is enough overlap among the permutations of the sums of possible squares (once the numbers are large enough).
<
using System.Collections.Generic;
using System.Linq;
Line 71 ⟶ 170:
a.Count, sw.Elapsed.TotalMilliseconds);
}
}</
{{out|Output @Tio.run}}
<pre>Numbers which are not the sum of distinct squares:
Line 80 ⟶ 179:
===Alternate Version===
A little quicker, seeks between squares.
<
using System.Collections.Generic;
using System.Linq;
Line 110 ⟶ 209:
Console.Write(sf, s.Last()-y.Last(),y.Last());
}
}</
{{out|Output @Tio.run}}
<pre>Numbers which are not the sum of distinct squares:
Line 116 ⟶ 215:
found 31 total in 9.9693 ms
stopped checking after finding 128 sequential non-gaps after the final gap of 128</pre>
=={{header|BASIC}}==
==={{header|FreeBASIC}}===
{{trans|XPL0}}
<syntaxhighlight lang="vb">Function SumSq(num As Integer) As Integer 'Return sum of squares specified by bits in num
Dim As Integer n = 1, suma = 0, Sq
While num
If num And 1 Then
Sq = n*n
suma += Sq
End If
num Shr= 1
n += 1
Wend
Return suma
End Function
Dim As Integer limite = 1e6, cant = 0, i
Dim As Boolean flags(limite)
For i = 0 To limite-1
flags(i) = True
Next
For i = 0 To limite-1
If i < limite Then flags(SumSq(i)) = False
Next
For i = 0 To Sqr(limite)-1
If flags(i) Then cant += 1: Print i;
Next
Print Chr(10); cant; " numbers which are not the sum of distinct squares."
Sleep</syntaxhighlight>
{{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
31 numbers which are not the sum of distinct squares.</pre>
==={{header|Gambas}}===
<syntaxhighlight lang="vbnet">Public flags[1000000] As Boolean
Public Sub Main()
Dim limite As Integer = 1e6, cant As Integer = 0, i As Integer
For i = 0 To limite - 1
flags[i] = True
Next
For i = 0 To limite - 1
If i < limite Then flags[SumSq(i)] = False
Next
For i = 0 To Sqr(limite) - 1
If flags[i] Then
cant += 1
Print i; " ";
End If
Next
Print Chr(10); cant; " numbers which are not the sum of distinct squares."
End
Function SumSq(num As Integer) As Integer
Dim n As Integer = 1, suma As Integer = 0, Sq As Integer
While num
If num And 1 Then
Sq = n * n
suma += Sq
End If
num = num Shr 1
n += 1
Wend
Return suma
End Function</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
void print_vector(const std::vector<int32_t>& list) {
std::cout << "[";
for ( uint64_t i = 0; i < list.size() - 1; ++i ) {
std::cout << list[i] <<", ";
}
std::cout << list.back() << "]" << std::endl;
}
bool sum_of_distinct_squares(const int32_t& n, const std::vector<int32_t>& squares) {
if ( n <= 0 ) {
return false;
}
if ( find(squares.begin(), squares.end(), n) != squares.end() ) {
return true;
}
const int32_t sum = std::accumulate(squares.begin(), squares.end(), 0);
if ( n > sum ) {
return false;
}
if ( n == sum ) {
return true;
}
std::vector<int32_t> reversed_squares(squares);
reversed_squares.erase(reversed_squares.end() - 1);
std::reverse(reversed_squares.begin(), reversed_squares.end());
return sum_of_distinct_squares(n - squares[squares.size() - 1], reversed_squares)
|| sum_of_distinct_squares(n, reversed_squares);
}
int main() {
std::vector<int32_t> squares;
std::vector<int32_t> result;
int32_t test_number = 1;
int32_t previous_test_number = 1;
while ( previous_test_number >= ( test_number >> 1 ) ) {
const int32_t square_root = static_cast<int32_t>(std::sqrt(test_number));
if ( square_root * square_root == test_number ) {
squares.emplace_back(test_number);
}
if ( ! sum_of_distinct_squares(test_number, squares) ) {
result.emplace_back(test_number);
previous_test_number = test_number;
}
test_number++;
}
std::cout << "Numbers which are not the sum of distinct squares:" << std::endl;
print_vector(result);
std::cout << "\n" << "Stopped checking after finding " << ( test_number - previous_test_number )
<< " sequential non-gaps after the final gap of " << previous_test_number << std::endl;
std::cout << "Found " << result.size() << " numbers in total" << std::endl;
}
</syntaxhighlight>
{{ out }}
<pre>
Numbers which are 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]
Stopped checking after finding 130 sequential non-gaps after the final gap of 128
Found 31 numbers in total
</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
Testing number beyond 128, show no values greater than this value.
<syntaxhighlight lang="Delphi">
{This code would normally be a separate library but is present her for clarity}
{Iterater object to step through all the indices
{ corresponding to the bits in "N". This is used }
{ step through all the combinations of items }
type TBitIterator = class(TObject)
private
FNumber,FIndex: integer;
public
procedure Start(StartNumber: integer);
function Next(var Index: integer): boolean;
end;
procedure TBitIterator.Start(StartNumber: integer);
{Set the starting value of the number }
begin
FNumber:=StartNumber;
end;
function TBitIterator.Next(var Index: integer): boolean;
{Return the next available index}
begin
Result:=False;
while FNumber>0 do
begin
Result:=(FNumber and 1)=1;
if Result then Index:=FIndex;
FNumber:=FNumber shr 1;
Inc(FIndex);
if Result then break;
end;
end;
{------------------------------------------------------------------------------}
procedure NonSquareSums(Memo: TMemo);
var Squares: TCardinalDynArray;
var I,N,Cnt: integer;
var S: string;
function GetSum(N: integer): integer;
{Iterate through all indices corresponding to N}
{Get get the sum of their values}
var Inx: integer;
var BI: TBitIterator;
begin
BI:=TBitIterator.Create;
try
BI.Start(N);
Result:=0;
while BI.Next(Inx) do
Result:=Result+Squares[Inx];
finally BI.Free; end;
end;
function HasSquareSum(N: integer): boolean;
{See if N is sum of squares}
var I: integer;
begin
Result:=True;
for I:=0 to High(Squares) do
if GetSum(I)=N then exit;
Result:=False;
end;
begin
{build array of squares for speed}
{64K^2 max 32-bit integer value}
SetLength(Squares,65536);
for I:=1 to High(Squares) do Squares[I-1]:=I*I;
S:=''; Cnt:=0;
{Test numbers up to sqrt(64K) = 64}
for I:=1 to trunc(sqrt(Length(Squares))) do
if not HasSquareSum(I) then
begin
{display number that aren't sum of squares}
Inc(Cnt);
S:=S+Format('%4d',[I]);
if (Cnt mod 10)=0 then S:=S+CRLF;
end;
Memo.Lines.Add('Numbers which are not the sum of distinct squares');
Memo.Lines.Add('Count = '+IntToStr(Cnt));
Memo.Lines.Add(S);
end;
</syntaxhighlight>
{{out}}
<pre>
Numbers which are not the sum of distinct squares
Count = 31
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
Elapsed Time: 333.278 ms.
</pre>
=={{header|EasyLang}}==
{{trans|Lua}}
<syntaxhighlight lang=easylang>
maxNumber = 324
len isSum[] maxNumber
maxSquare = floor sqrt maxNumber
#
proc flagSum currSum sqPos . .
nextSum = currSum + sqPos * sqPos
if nextSum <= maxNumber
isSum[nextSum] = 1
for i = sqPos + 1 to maxSquare
flagSum nextSum i
.
.
.
for i = 1 to maxSquare
flagSum 0 i
.
for i = 1 to maxNumber
if isSum[i] = 0
write i & " "
.
.
</syntaxhighlight>
=={{header|Go}}==
Line 121 ⟶ 513:
{{libheader|Go-rcu}}
The quicker version and hence (indirectly) a translation of C#.
<
import (
Line 183 ⟶ 575:
}
var r int</
{{out}}
Line 192 ⟶ 584:
Stopped checking after finding 130 sequential non-gaps after the final gap of 128
Found 31 in total
</pre>
=={{header|J}}==
Code:
<syntaxhighlight lang=J>task=: {{
r=. 'invalid'
lim=. 1
whilst. -.r -: have do.
have=. r
lim=. lim+1
r=. (i.*:lim) -. (#:i.2^lim)+/ .**:i.lim
end.
}}</syntaxhighlight>
In other words, find all integers up to the square of our limit, and remove from that sequence all corresponding sums of squares. Keep increasing the limit until we stop finding new values which are not sums of squares.
Result:
<syntaxhighlight lang=J> task''
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</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public final class NumbersNotSumDistinctSquares {
public static void main(String[] aArgs) {
List<Integer> squares = new ArrayList<Integer>();
List<Integer> result = new ArrayList<Integer>();
int testNumber = 1;
int previousTestNumber = 1;
while ( previousTestNumber >= ( testNumber >> 1 ) ) {
final int squareRoot = (int) Math.sqrt(testNumber);
if ( squareRoot * squareRoot == testNumber ) {
squares.add(testNumber);
}
if ( ! sumOfDistinctSquares(testNumber, squares) ) {
result.add(testNumber);
previousTestNumber = testNumber;
}
testNumber += 1;
}
System.out.println("Numbers which are not the sum of distinct squares:");
System.out.println(result);
System.out.println();
System.out.println("Stopped checking after finding " + ( testNumber - previousTestNumber )
+ " sequential non-gaps after the final gap of " + previousTestNumber);
System.out.println("Found " + result.size() + " numbers in total");
}
private static boolean sumOfDistinctSquares(int aN, List<Integer> aSquares) {
if ( aN <= 0 ) {
return false;
}
if ( aSquares.contains(aN) ) {
return true;
}
final int sum = aSquares.stream().mapToInt(Integer::intValue).sum();
if ( aN > sum ) {
return false;
}
if ( aN == sum ) {
return true;
}
List<Integer> reversedSquares = new ArrayList<Integer>(aSquares);
reversedSquares.remove(reversedSquares.size() - 1);
Collections.reverse(reversedSquares);
return sumOfDistinctSquares(aN - aSquares.get(aSquares.size() - 1), reversedSquares)
|| sumOfDistinctSquares(aN, reversedSquares);
}
}
</syntaxhighlight>
{{ out }}
<pre>
Numbers which are 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]
Stopped checking after finding 130 sequential non-gaps after the final gap of 128
Found 31 numbers in total
</pre>
Line 204 ⟶ 683:
Since the implementation is based on generic concepts (such as runs), the
helper functions are potentially independently useful.
<
# sums of distinct squares (sods)
Line 256 ⟶ 735:
| [range(2; $ix+2|sq)] - $sods;
not_sum_of_distinct_squares</
{{out}}
<pre>
Line 264 ⟶ 743:
=={{header|Julia}}==
A true proof of the sketch below would require formal mathematical induction.
<
Here we show all the 128 < numbers < 400 can be expressed as a sum of distinct squares. Now
11 * 11 < 128 < 12 * 12. It is also true that we need no square less than 144 (12 * 12) to
Line 282 ⟶ 761:
println(possibles)
</
<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|Lua}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="lua">
do --[[ 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 squares
then all integers greater than 129 can be so expressed (see the link in
the Wren sample) so we need to check that 129-324 can be so expressed
and find the numbers below 129 that can't be so expressed
--]]
local maxNumber = 324
local isSum = {}
local maxSquare = math.floor( math.sqrt( 324 ) )
local square = {} for i = 0,maxSquare do square[ i ] = i * i end
local function flagSum ( currSum, sqPos )
local nextSum = currSum + square[ sqPos ]
if nextSum <= maxNumber then
isSum[ nextSum ] = true
for i = sqPos + 1, maxSquare do
flagSum( nextSum, i )
end
end
end
for i = 0,maxSquare do
flagSum( 0, i )
end
--[[ show the numbers that can't be formed from a sum of distinct squares
and check 129-324 can be so formed
--]]
local unformable = 0
for i = 0, maxNumber do
if not isSum[ i ] then
io.write( string.format( "%4d", i ) )
unformable = unformable + 1
if unformable % 12 == 0 then io.write( "\n" ) end
if i > 128 then
io.write( "\n", "**** unexpected unformable number: ", i, "\n" )
end
end
end
end
</syntaxhighlight>
{{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|Mathematica}}/{{header|Wolfram Language}}==
<
SumOfSquareable[n_Integer] := MemberQ[Total /@ Subsets[Range[1, Floor[Sqrt[n]]]^2, {1, \[Infinity]}], n]
notsummable = {};
Line 306 ⟶ 835:
{\[Infinity]}
]
notsummable</
{{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}}==
{{trans|Wren, C#, Go}}
<syntaxhighlight lang="Nim">import std/[algorithm, math, monotimes, strformat, strutils, times]
proc soms(n: int; f: seq[int]): bool =
## Recursively permutates the list of squares to seek a matching sum.
if n <= 0: return false
if n in f: return true
case cmp(n, sum(f))
of 1:
result = false
of 0:
result = true
else:
let rf = reversed(f.toOpenArray(0, f.len - 2))
result = soms(n - f[^1], rf) or soms(n, rf)
let start = getMonoTime()
var s, a: seq[int]
var i, g = 1
while g >= i shr 1:
let r = sqrt(i.toFloat).int
if r * r == i: s.add i
if not soms(i, s):
g = i
a.add g
inc i
echo "Numbers which are not the sum of distinct squares:"
echo a.join(" ")
echo &"\nStopped checking after finding {i - g} sequential non-gaps after the final gap of {g}."
echo &"Found {a.len} total in {(getMonotime() - start).inMicroseconds} µs."
</syntaxhighlight>
{{out}}
<pre>Numbers which are 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
Stopped checking after finding 130 sequential non-gaps after the final gap of 128.
Found 31 total in 1536 µs.
</pre>
=={{header|Pascal}}==
Line 318 ⟶ 954:
are not reachably nor<br>
SumOfSquare-2, SumOfSquare-3,SumOfSquare-6,...SumOfSquare-108,SumOfSquare-112,SumOfSquare-128<br>
<
{$IFDEF Windows} {$APPTYPE CONSOLE} {$ENDIF}
var
Line 404 ⟶ 1,040:
{$IFNDEF UNIX} readln; {$ENDIF}
end.
</syntaxhighlight>
{{out}}
<pre>
Line 426 ⟶ 1,062:
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|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl" line>use v5.36;
use List::Util <sum uniq none>;
use Algorithm::Combinatorics 'combinations';
my @squares = map { $_**2 } 0..100;
my $sq;
while (++$sq) {
my(@sums, @run);
for (1..$sq) {
push @sums, sum @squares[@$_] for combinations [1..$sq+1], $_
}
@sums = uniq sort { $a <=> $b } @sums;
for (@sums) {
push(@run, $_) and next unless @run;
if ($_ == $run[-1] + 1) { push @run, $_ } else { last if @run > $squares[$sq]; @run = () }
}
next unless @run;
for my $i (1..$run[-1]) {
push @res, $i if none { $i eq $_ } @sums
}
last if @run > $squares[$sq];
}</syntaxhighlight>
{{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|Phix}}==
Line 432 ⟶ 1,096:
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.
<!--<
<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>
Line 455 ⟶ 1,119:
<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>
<!--</
{{out}}
<pre>
2 3 6 7 8 ... 92 96 108 112 128 (31 numbers which are not the sum of distinct squares)
</pre>
=={{header|Quackery}}==
<code>from</code>, <code>index</code>, <code>end</code>, and <code>incr</code> are defined at [[Loops/Increment loop index within loop body#Quackery]].
'''Method'''
We generate numbers which are the Sum Of Distinct Squares (SODS) up to N<sup>2</sup> by generating a list of the SODS up to (N-1)<sup>2</sup>, then adding each of those numbers + N<sup>2</sup> to the list. For N=0 the list is [0]. This method produces some duplicates along the way so after each iteration we remove any duplicates using <code>sort unique</code>. (<code>unique</code> requires a sorted list.)
As noted in other solutions, once there is a run longer than (N+1)<sup>2</sup>, all the subsequent numbers will be SODS. <code>missing</code> returns the length and position of the longest run. (After the last iteration, some SODS will be missing from the list after the longest run, but we can be confident that they will be found in further iterations as noted in other task solutions.) The length is used to test for when we can stop iterating, and the position tells us where we can trim the list.
Finally, <code>missing</code> generates a list of the numbers which are not SODS from the list of SODS. (This is why we need to trim the list; so it does not include the numbers which are SODS but had not yet been added to the list.)
<syntaxhighlight lang="Quackery"> [ [] swap
behead swap
witheach
[ 2dup = iff
drop done
dip join ]
join ] is unique ( [ --> [ )
[ stack ] is cut ( --> s )
[ -1 cut put
1 temp put
1 swap
behead swap
witheach
[ tuck - -1 = iff
[ dip 1+
over temp share
> if
[ over temp replace
i^ cut replace ] ]
else
[ nip 1 swap ] ]
2drop
temp take cut take ] is maxrun ( [ --> n n )
[ [] swap 0 over
witheach [ bit | ]
swap -1 peek times
[ dup i^ bit & not if
[ dip [ i^ join ] ] ]
drop ] is missing ( [ --> [ )
1 temp put
' [ 0 ]
1 from
[ dup witheach
[ temp share +
join ]
sort unique
dup maxrun drop
index 2 + temp tally
temp share > iff
end done
2 incr ]
temp release
dup maxrun
nip split
drop missing
say "Numbers that are not the sum of distinct squares:"
cr echo</syntaxhighlight>
{{out}}
<pre>Numbers that are 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|Raku}}==
Line 466 ⟶ 1,199:
'''Spoiler:''' ''(highlight to read)''<br>
<span style="foreground-color:black;background-color:black;">Once the longest run of consecutive generated sums is longer the the next square, every number after can be generated by adding the next square to every number in the run. Find the ''new'' longest run, add the ''next'' square, etc.<span>
<syntaxhighlight lang="raku"
for 1..∞ -> $sq { # for every combination of all squares
Line 476 ⟶ 1,209:
}
put grep * ∉ @sums, 1..@run.tail and last if @run.elems > @squares[$sq];
}</
{{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>
Line 485 ⟶ 1,218:
===Brute force===
This uses a brute force approach to generate the relevant numbers, similar to Julia, except using the same figures as the above proof. Still slow in Wren, around 20 seconds.
<
var combs = []
var results = []
Line 527 ⟶ 1,260:
System.print("Numbers which are not the sum of distinct squares:")
System.print(results)</
{{out}}
Line 540 ⟶ 1,273:
{{libheader|Wren-fmt}}
Hugely quicker in fact - only 24 ms, the same as C# itself.
<
import "./fmt" for Fmt
Line 570 ⟶ 1,303:
System.print(a.join(", "))
Fmt.print(sf, i - g, g)
Fmt.print("Found $d total in $d ms.", a.count, ((System.clock - start)*1000).round)</
{{out}}
Line 580 ⟶ 1,313:
Found 31 total in 24 ms.
</pre>
=={{header|XPL0}}==
This generates all combinations of sums of N squared up to a Limit. For
a Limit = 1000 = $3E8 = %11_1110_1000 this sums 100+81+64+49+36+16. A Limit of one million
shows that there is a huge gap following 128 of values that cannot be
generated by any combination of sums of squares. The mathematical
argument why none exist beyond 128 is provided by the Julia example.
<syntaxhighlight lang "XPL0">func SumSq(B); \Return sum of squares specified by bits in B
int B, N, Sq, Sum;
[N:= 1; Sum:= 0;
while B do
[if B & 1 then
[Sq:= N*N;
Sum:= Sum + Sq;
];
B:= B>>1;
N:= N+1;
];
return Sum;
];
def Limit = 1_000_000;
char Flags(Limit);
int I;
[for I:= 0 to Limit-1 do
Flags(I):= true;
for I:= 0 to Limit-1 do
if I < Limit then
Flags(SumSq(I)):= false;
for I:= 0 to sqrt(Limit)-1 do
if Flags(I) then
[IntOut(0, I); ChOut(0, ^ )];
]</syntaxhighlight>
{{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>
| |||