General solution to sum multiples of multiple numbers below a limit

Question

sumMultiples() is a working general solution to Project Euler's first problem. Don't read it if you want to try it yourself.

This question is about preserving this general nature while improving performance, perhaps using math tricks like sumSkip() and sumIndetity(). Unfortunately everything I find that takes advantage of these tricks sacrifices the ability to have a general solution that works with any number of multiples and any limit. Notice how using sumSkip() and sumIdentity() require hand tuning to work. I'd like to use the same interface sumMultiples() uses and allow any number of base numbers with any values. Well, short of causing overflows anyway.

In main sumSkip() and sumIdentity() are being used with the inclusion–exclusion principle in a rigid hand tuned form. I'm suspecting there is a general way to apply this principle to this problem but frankly I can't see it. I'll accept solutions that don't use it so long as they truly improve this solutions Big O Complexity.

I believe sumMultiples() is O(below x base) complexity. I'm looking to improve on that.

Before linking possible duplicates or solutions please ensure they deal with the general requirement.

public static void main(String[] args) {
 int below = 1000;
 int[] base = {3, 5};
 System.out.println( sumMultiples(below, base) );
 // Making names shorter to help readability
 int b0 = base[0];
 int b1 = base[1];
 // Hand tuned to number and values. Something I'd like to avoid.
 System.out.println( sumSkip(b0, below) + sumSkip(b1, below) - sumSkip(b0*b1, below) );
 System.out.println( b0*sumIdentity(below/b0) +
 b1*sumIdentity(below/b1-1) -
 b0*b1*sumIdentity( below / (b0*b1) ) );
}
// General solution - any sized base with any values - uses brute force approach
private static int sumMultiples(int below, int... base) {
 int result = 0;
 boolean isMultiple;
 // Every integer below limit
 for(int i = 1; i < below; i++) {
 // Resetting dirty bit pattern
 isMultiple = false;
 // Every base
 for (int j = 0; j < base.length; j++) {
 // Stays false until a multiple is found. Then stays true.
 isMultiple |= i % base[j] == 0;
 }
 // Sum if i is a multiple of an integer in multiples
 if (isMultiple) {
 result += i;
 }
 }
 return result;
}
// Skip non multiples - still fairly brute force - less general
public static int sumSkip(int base, int below) {
 int result = 0;
 int multiple = base;
 while (multiple < below) {
 result += multiple;
 multiple += base; 
 }
 return result;
}
// Sum using math
public static int sumIdentity(int n) {
 return n*(n+1)/2;
}

Output:

233168
233168
233168

• Jamal: The note about duplicates isn't needed, considering the nature of the site. The mathematics tag is also not needed with Project Euler posts that already use programming-challenge.

Answer 1

After I provided a quick-glance alternative implementation yesterday, here comes a full review now. It's so different in approach I chose to add another answer for it. That said, let's get started:

I see in the comments to a now deleted answer that you don't want comments on the code you provided as main. I'll do it anyways, because you're doing some things that make me shiver:

System.out.println( sumMultiples(below, base) );

This is definitely nitpickish, but I personally prefer to not add additional spaces inside the braces of a method-call:

System.out.println(sumMultiples(below, base));

// Making names shorter to help readability
int b0 = base[0];
int b1 = base[1];

Don't do that. Shorter names are not readable. A readable name can be easily read out loud. That makes your comment a blatant lie in my eyes. Usually this would be the point where you'd have lost my respect as fellow programmer... I understand that you may sometimes want variable names shorter, and they are nice in the rest of your code. But the resoning is something ...

Oh and... Don't number your variables! This makes it difficult to process them in their mental context, and makes the code harder to understand.

// Hand tuned to number and values. Something I'd like to avoid
System.out.println( sumSkip(b0, below) + sumSkip(b1, below) - sumSkip(b0*b1, below) );
System.out.println( b0*sumIdentity(below/b0) +
 b1*sumIdentity(below/b1-1) -
 b0*b1*sumIdentity( below/ (b0*b1) ) );

Why are you doing this? There is some relatively complicated problematic and it's slammed into the reader's face in the main-method.

The main-method is supposed to be a place of high-level abstraction. I think reading a main-method should be just like reading English. A simple English sentence. Consider the following (as example):

public static void main(String[] args) {
 new Program().start();
}

Extract the complexity into methods. I figure it's fine to have this hand-tuned and doubt there is a way to avoid this when not working with an already generalized formula.

// General solution - any sited base with any values - uses brute force approach

This wants to be javadoc:

/**
 * General solution. Calculates the result using a brute-force approach
 *
 * @parameter below 
 * An integer representing the non-inclusive upper border of the problem.
 * @parameter base 
 * At least one integer representing the divisors for leftover-free division of numbers that are to be summed.
 */

For the sumMultiples, see my other answer. There's not really much else to say about that. Nice naming, simple and straightforward approach... Actually this goes for the rest of your code (aside from the non-javadoc javadocs) with one small exception:

How the **** does sumIdentity work? //Sum using math doesn't help me all that much ;)

Alas, that's it for now.

Answer 2

Your sumMultiples could benefit strongly from using Streams. But that aside you have a grave mistake...

If below is negative, your program enters an infinite loop ;(

That stated here's how this looks as a twoliner:

public static int sumMultiples(int below, int... bases) {
 if (below <= 0) throw new IllegalArgumentException();
 return IntStream.rangeClosed(0, below - 1)
 .filter(candidate -> Arrays.stream(bases)
 .filter(base -> candidate % base == 0).findFirst().isPresent())
 .sum();
}

• candied_orange: Indeed all the input could stand some validation, base values included. I appreciate the 2 line java 8 treatment but fail to see how it offers a complexity improvement. If there is one would you explain it?
• Vogel612: The flag is removed ;) on a related note all unecessary interim variables (result) have been cleared in that oneliner. It also might perform faster since the findFirst may terminate early when a fitting divisor is found

Answer 3

Bug

• The combination of the sumIdentity() method calls does not return the expected results.

  For the given parameter

  int below = 20;
  int[] base = {3, 7}; 
  

  the output is

  84
  84
  70

• The combination of the sumSkip() method calls does not return the expected results.

  For the given parameter

  int below = 20;
  int[] base = {3, 6}; 
  

  which are valid IMHO the output is

  63
  81
  63

• candied_orange: Well yes, this is what I meant by "hand tuned". The methods only do what they claim to do. They only end up being useful solving this problem for a very narrow case. I'm failing to see how they can be useful to a general solution. Thats why the "hand tuning" is happening in main. I don't want that confusion down in a method until it is generalized. Can you help me generalize them and make a method that competes with sumMultiples() or find another approach?