# How to calculate wierd number in efficient way – optimization of algorithm needed 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..j-1] 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[i] = true;          }          //  If sum is not 0 and set is empty, then answer is false          for (int i = 1; i <= sum; i++) {             subset[i] = 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][j-1];                 int test = divisors.get(j-1);                 if ( i >= test ) {                     subset[i][j] = subset[i][j] || subset[i - test][j-1];                  }             }          }           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:

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

2. If a number is deficient this means it cannot be weird

The above points are based on https://mathworld.wolfram.com/DeficientNumber.html

1. 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. Posted on Categories proxies