I am trying to print n weird numbers where n is really big number (eg: 15000).
I found this site to check the algorithm for n 600 if I have some errors: http://www.numbersaplenty.com/set/weird_number/more.php
However, my algorithm is really slow in bigger numbers:
import java.util.ArrayList; import java.util.List; public class Test { public static void main(String[] args) { int n = 2; for ( int count = 1 ; count <= 15000 ; n += 2 ) { if (n % 6 == 0) { continue; } List<Integer> properDivisors = getProperDivisors(n); int divisorSum = properDivisors.stream().mapToInt(i > i.intValue()).sum(); if ( isDeficient(divisorSum, n) ) { continue; } if ( isWeird(n, properDivisors, divisorSum) ) { System.out.printf("w(%d) = %d%n", count, n); count++; } } } private static boolean isWeird(int n, List<Integer> divisors, int divisorSum) { return isAbundant(divisorSum, n) && ! isSemiPerfect(divisors, n); } private static boolean isDeficient(int divisorSum, int n) { return divisorSum < n; } private static boolean isAbundant(int divisorSum, int n) { return divisorSum > n; } private static boolean isSemiPerfect(List<Integer> divisors, int sum) { int size = divisors.size(); // The value of subset[i][j] will be true if there is a subset of divisors[0..j1] with sum equal to i boolean subset[][] = new boolean[sum+1][size+1]; // If sum is 0, then answer is true for (int i = 0; i <= size; i++) { subset[0][i] = true; } // If sum is not 0 and set is empty, then answer is false for (int i = 1; i <= sum; i++) { subset[i][0] = false; } // Fill the subset table in bottom up manner for ( int i = 1 ; i <= sum ; i++ ) { for ( int j = 1 ; j <= size ; j++ ) { subset[i][j] = subset[i][j1]; int test = divisors.get(j1); if ( i >= test ) { subset[i][j] = subset[i][j]  subset[i  test][j1]; } } } return subset[sum][size]; } private static final List<Integer> getProperDivisors(int number) { List<Integer> divisors = new ArrayList<Integer>(); long sqrt = (long) Math.sqrt(number); for ( int i = 1 ; i <= sqrt ; i++ ) { if ( number % i == 0 ) { divisors.add(i); int div = number / i; if ( div != i && div != number ) { divisors.add(div); } } } return divisors; } }
I have three easy breakouts:

If a number is divisable by 6 it is semiperfect which means it cannot be weird

If a number is deficient this means it cannot be weird
The above points are based on https://mathworld.wolfram.com/DeficientNumber.html
 If a a number is odd it cannot be weird at least for 10^21 numbers (which is good for the numbers I am trying to obtain).
The other optimization that I used is the optimization for finding all the dividers of a number. Instead of looping to n, we loop to SQRT(n).
However, I still need to optimize: 1. isSemiPerfect because it is really slow 2. If I can optimize further getProperDivisors it will be good too.
Any suggestions are welcome, since I cannot find any more optimizations to find 10000 weird numbers in reasonable time.
PS: Any code in Java, C#, PHP and JavaScript are OK for me.
EDIT: I found this topic and modified isSemiPerfect to look like this. However, it looks like it does not optimize but slow down the calculations:
private static boolean isSemiPerfect(List<Integer> divisors, int n) { BigInteger combinations = BigInteger.valueOf(2).pow(divisors.size()); for (BigInteger i = BigInteger.ZERO; i.compareTo(combinations) < 0; i = i.add(BigInteger.ONE)) { int sum = 0; for (int j = 0; j < i.bitLength(); j++) { sum += i.testBit(j) ? divisors.get(j) : 0; } if (sum == n) { return true; } } return false; }
The script is still running from 11 hours and I am only at 4800th number.