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:09, 19 August 2023
, 9 months agoNew post.
No edit summary |
(New post.) |
||
Line 405:
<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>
=={{header|jq}}==
| |||