2
\$\begingroup\$

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

I used this as an excuse to play around with Java 8 Streams. It's my first time actually working with streams, so I'd like reviews covering my use of the Streams.

Any comments on code style, stream usage, potential optimizations (though it still runs in less than a second on my machine) of the basic logic are appreciated.

package complete;

import java.util.HashSet;
import java.util.stream.IntStream;

public class pe023 {
    public static final int MAX_POTENTIAL_NON_ABUNDANT_SUM = 28213;

    public static void main(String[] args) {
        int result = IntStream
                .rangeClosed(1, MAX_POTENTIAL_NON_ABUNDANT_SUM)
                .parallel()
                .filter(pe023::isNonAbundantSum)
            //  .peek(System.out::println)
                .sum();

        System.out.println(result);
    }

    /**
     * A number is a Non-abundant sum if it cannot be written as the sum of two abundant numbers.
     * 
     * @param num the number to check
     * @return if the number is a non-abundant sum
     */
    public static boolean isNonAbundantSum(int num) {
        for (int low=1,high=num-1; low<=high; low++,high--) {
            if (isAbundant(low) && isAbundant(high)) {
                return false;
            }
        }
        return true;
    }

    static HashSet<Integer> isAbundantCache = new HashSet<>();
    static HashSet<Integer> notAbundantCache = new HashSet<>();

    /**
     * A number is abundant if the sum of its proper divisors is greater than the number.
     * 
     * @param num the number to check
     * @return if the number is abundant
     */
    public static boolean isAbundant(int num) {
        if (isAbundantCache.contains(num)) {
            return true;
        }
        if (notAbundantCache.contains(num)) {
            return false;
        }

        if (properDivisors(num).sum() > num) {
            isAbundantCache.add(num);
            return true;
        } else {
            notAbundantCache.add(num);
            return false;
        }
    }

    public static IntStream properDivisors(int num) {
        IntStream stream = IntStream.of(1);
        for (int i=2; i<=num/2; i++) {
            if (num%i == 0) {
                stream = IntStream.concat(stream, IntStream.of(i));
            }
        }
        return stream;
    }
}

// 4179871
\$\endgroup\$
3
\$\begingroup\$

Wrapping individual values in single-value streams and concatenating the streams is very inefficient. You'd be better off using IntStream.Builder to build your IntStream, like this:

public static IntStream properDivisors(int num) {
    IntStream.Builder builder = IntStream.builder();
    for (int i=2; i<=num/2; i++) {
        if (num%i == 0) {
            builder.accept(i);
        }
    }
    return builder.build();
}

Better yet, since you're experimenting with Streams, convert your for loop to an IntStream using IntStream.range(), like this:

public static IntStream properDivisors(int num) {
    return IntStream.range(2, num/2 + 1).filter(i -> num % i == 0);
}
\$\endgroup\$
  • \$\begingroup\$ It's a matter of changing the way I think about it, isn't it. Streams are a different way of thinking than the traditional. \$\endgroup\$ – CAD97 Apr 17 '16 at 17:50
  • \$\begingroup\$ I should have commented that the range end is + 1 because the end value in range is exclusive (1 after the last value in the stream) which is analogous to the behavior of i < size in a for loop. However, your for loop contained <= so the end of the range had to have 1 added to it. \$\endgroup\$ – Hank D Apr 17 '16 at 20:29
  • 1
    \$\begingroup\$ or I can just use rangeClosed like I did for the main logic. I really don't know at this point why I didn't think to filter down a stream for properDivisors instead of building it. That's just old logic sticking around. \$\endgroup\$ – CAD97 Apr 17 '16 at 21:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.