General solution to sum multiples of multiple numbers below a limit 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 &lt; below; i++) {

        // Resetting dirty bit pattern
        isMultiple = false;

        // Every base
        for (int j = 0; j &lt; 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 &lt; 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
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.