Sum of combinations of numbers

Question

I want to solve a mathematical problem in a fastest possible way. I have a set of natural numbers between 1 to n, for example {1,2,3,4,n=5} and I want to calculate a formula like this:

s = 1*2*3*4+1*2*3*5+1*2*4*5+1*3*4*5+2*3*4*5

as you can see, each element in the sum is a multiplications of n-1 numbers in the set. For example in (1*2*3*4), 5 is excluded and in (1*2*3*5), 4 is excluded. I know some of the multiplications are repeated, for example (1*2) is repeated in 3 of the multiplications. How can I solve this problem with least number of multiplications.

Sorry for bad English. Thanks.

Answer 1

Here is a way that does not "cheat" by replacing multiplication with repeated addition or by using division. The idea is to replace your expression with

1*2*3*4 + 5*(1*2*3 + 4*(1*2 + 3*(1 + 2)))

This used 9 multiplications for the numbers 1 through 5. In general I think the multiplication count would be one less than the (n-1)th triangular number, n * (n - 1) / 2 - 1. Here is Python code that stores intermediate factorial values to reduce the number of multiplications to just 6, or in general 2 * n - 4, and the addition count to the same (but half of them are just adding 1):

def f(n):
    fact = 1
    term = 2
    sum = 3
    for j in range(2, n):
        fact *= j
        term = (j + 1) * sum
        sum = fact + term
    return sum

The only way to find which algorithm is the fastest is to code all of them in one language, and run each using a timer.

Answer 2

The following would be the most straightforward answer.

def f(n):
    result = 0
    nList = [i+1 for i in range(n)]
    for i in range(len(nList)):
        result += reduce(lambda x, y: x*y,(nList[:i]+nList[i+1:]))
return result

Walkthrough - use the reduce function to multiply all list's of length n-1 and add to the variable result.

Answer 3

If you just want to minimise the number of multiplications, you can replace all the multiplications by additions, like this:

// Compute 1*2*…*n
mult_all(n):
    if n = 1
        return 1
    res = 0
    // by adding 1*2*…*(n-1) an entirety of n times
    for i = 1 to n do
        res += mult_all(n-1)
    return res

// Compute sum of 1*2*…*(i-1)*(i+1)*…*n
sum_of_mult_all_but_one(n):
    if n = 1
        return 0
    // by computing 1*2*…*(n-1) + (sum 1*2*…*(i-1)*(i+1)*…*(n-1))*n
    res = mult_all(n-1)
    for i = 1 to n do
        res += sum_of_mult_all_but_one(n-1)
    return res

Answer 4

Here is an answer that would work with javascript. It is not the fastest way because it is not optimized, but it should work if you want to just find the answer.

function combo(n){
var mult = 1;
var sum = 0;
for (var i = 1; i <= n; i++){
    mult = 1;
    for (var j = 1; j<= n; j++){
        if(j != i){
            mult = mult*j;
        }
    }
    sum += mult;
}
return (sum);
}

alert(combo(n));