1
\$\begingroup\$

I've tried to make something optimized for the Project Euler problem 23, named "Non-abundant sums".

I've fine-tuned my solution to the following:

  • I added divisors to the slots of each number to compute all the sums instead of checking if a number is abundant without using the modulo definition. This was my first big win.
  • I tried to minimize the number of loops, especially the outer loops (which I could reduce to 1).
  • Since the number of candidates is rather small (28123), I decided to work with arrays indexed by the candidates. This means that I compute the sum of divisors (div in the code) and I keep each encountered sum of abundants directly based on the index.
  • Since I have abundant numbers, it's easy to compute the sum of sum of (intended) abundant numbers, it's much less easy to compute non-abundant numbers, so I compute the absolute max value and subtract sum of abundant numbers from it.

This code is already running very fast (under 60 ms), but I'm wondering if its performance can still be drastically improved. More likely by using other lateral thinkings rather than small optimizations.

Now, here's my implementation of it.

public class Problem23 extends AbstractProblem {
  @Override public Object solve() {

    // Limit as defined by the problem.
    final int N = 28123;

    // [n] -> sum of the proper divisors of n
    int[] sumsOfDivisors = new int[N + 1];

    // A list of abundant numbers.
    int[] abundants = new int[N + 1];
    int abundantsSize = 0;

    // [n] -> is n sum of two abundants
    boolean[] sumsOfAbundants = new boolean[N + 1];

    // Total from which we're gonna subtract abundants to get the sum of non-abudant numbers.
    int totalSumOfAbundants = (N * (N + 1)) / 2;


    for (int i = 1; i <= N; i++) { // main loop

      // Build the sums of divisors by adding i to all of its multiples.
      // This avoids performing costly division/modulos.
      for (int j = i << 1; j < N; j += i) {
        sumsOfDivisors[j] += i;
      }

      // Since we're increasing i, sumsOfDivisors[i] won't change anymore and we check in the same big loop if it's an abundant number
      if (sumsOfDivisors[i] > i) { // i is abundant

        // Add i to the list of abundants.
        abundants[abundantsSize++] = i;

        // For each previously found abundant number.
        for (int j = 0, soa; j < abundantsSize && (soa = i + abundants[j]) <= N; j++) {

          // If their sum isn't already marked as a sum of abundants, mark it as such and subtract it from the total.
          if (!sumsOfAbundants[soa]) {
            sumsOfAbundants[soa] = true;
            totalSumOfAbundants -= soa;
          }
        }
      }
    }
    return totalSumOfAbundants;
  }
}
\$\endgroup\$
  • \$\begingroup\$ Very nice solution! Can't think of any obvious improvements... \$\endgroup\$ – Jaime May 20 '16 at 4:38
  • \$\begingroup\$ Thanks. I know I can optimize some things like starting the outer loop from 2 and change to sumsOfDivisors[i] >= i but that's huge in the cost of understandability of the code. \$\endgroup\$ – Olivier Grégoire May 20 '16 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.