Numbers which are not the sum of distinct squares: Difference between revisions
Content added Content deleted
No edit summary |
(New post.) |
||
Line 405: | Line 405: | ||
<syntaxhighlight lang=J> task'' |
<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> |
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}}== |
=={{header|jq}}== |