CODEWITHSUNDEEP
javaarraysalgorithmmath
Matan
Matan

Reputation: 259

Possible multiplications of k distinct factors with largest possible factor n

Let M(n,k) be the sum of all possible multiplications of k distinct factors with largest possible factor n, where order is irrelevant.

For example, M(5,3) = 225 , because:

6+8+10+12+15+20+24+30+40+60 = 225.

One can easily notice that there are C(n,k) such multiplications, corresponding to the number of ways one can pick k objects out of n possible objects. In the example above, C(5,3) = 10 and there really are 10 such multiplications, stated above.

The question can also be visualized as possible n-sized sets containing exactly k 0's, where each cell that does not contain 0 inside it, has the value of its index+1 inside it. For example, one possible such set is {0,2,3,0,5}. From here on, one needs to multiply the values in the set that are different than 0.

My approach is a recursive algorithm. Similiarly to the above definition of M(n,k), I define M(n,j,k) to be the sum of all possible multiplications of exactly k distinct factors with largest possible factor n, AND SMALLEST possible factor j. Hence, my approach would yield the desired value if ran on M(n,1,k). So I start my recursion on M(n,1,k), with the following code, written in Java:

public static long M (long n, long j, long k)
{
    if (k==1)
        return usefulFunctions.sum(j, n);
    for (long i=j;i<=n-k+1+1;i++)
        return i*M(n,i+1,k-1);
}

Explanation to the code:

Starting with, for example, n=5 , j=1, k=3, the algorithm will continue to run as long as we need more factors, (k>=1), and it is made sure to run only distinct factors thanks to the for loop, which increases the minimal possible value j as more factors are added. The loop runs and decreases the number of needed factors as they are 'added', which is achieved through applying M(n,j+1,k-1). The j+1 assures that the factors will be distinct because the minimal value of the factor increases, and k-1 symbolizes that we need 1 less factor to add.

The function 'sum(j,n)' returns the value of the sum of all numbers starting from j untill n, so sum(1,10)=55. This is done with a proper, elegant and simple mathematical formula, with no loops: sum(j,n) = (n+1)*n/2 - (i-1)*i/2

public static long sum (long i, long n)
{
    final long s1 = n * (n + 1) / 2;
    final long s2 = i * (i - 1) / 2;
    return s1 - s2 ;
}

The reason to apply this sum when k=1, I will explain with an example: Say we have started with 1*2. Now we need a third factor, which can be either of 3,4,5. Because all multiplications: 1*2*3, 1*2*4, 1*2*5 are valid, we can return 1*2*(3+4+5) = 1*2*sum(3,5) = 24.

Similiar logic explains the coefficient "i" next to the M(n,j+1,k-1). say we have now the sole factor 2. Hence we need 2 more factors, so we multiply 2 by the next itterations, which should result in: 2*(3*sum(4,5) + 4*sum(5,5))

However, for a reason I can't explain yet, the code doesn't work. It returns wrong values and also has "return" issues that cause the function not to return anything, don't know why.

This is the reason i'm posting this question here, in hope someone will aid me. Either by fixing this code or sharing a code of his own. Explaining where I'm going wrong will be most appreciable.

Thanks a lot in advance, and sorry for this very long question, Matan.

-----------------------EDIT------------------------

Below is my fixed code, which solves this question. Posting it incase one should ever need it :) Have fun !

public static long  M(long n, long j, long k)
{
    if (k == 0)
        return 0;
    if (k == 1)
        return sum(j,n);
    else 
    {
        long summation = 0;
        for (long i=j; i<=n; i++)
            summation += i*M(n, i+1, k-1);
        return summation;
    }
}

Upvotes: 7

Views: 223

Answers (3)

sair
sair

Reputation: 832

I see that u got ur answer and i really like ur algorithm but i cant control myself posting a better algorithm . here is the idea

M(n,k) = coefficient of x^k in (1+x)(1+2*x)(1+3*x)...(1+n*x)

u can solve above expression by divide and conquer algorithm Click Here to find how to multiply above expression and get polynomial function in the form of ax^n + bx^(n-1)....+c

overall algorithm time complexity is O(n * log^2 n)

and best part of above algorithm is

in the attempt of finding solution for M(n,k) , u will find solution for M(n,x) where 1<=x<=n

i hope it will be useful to know :)

Upvotes: 2

yahya el fakir
yahya el fakir

Reputation: 562

You have a problem with your sum function : here is the correct formula:

public static long sum (long i, long n)
    {
        double s1 = n*(n+1)/2;
        double s2 = i*(i-1)/2;
        return (long)(s1-s2);
    }

Here the full solution : 

    static int n = 5; 
    static long k = 3;
// no need to add n and k them inside your M function cause they are fixed.
    public static long M (long start) // start = 1
    {
        if(start > k) // if start is superior to k : like your example going from 1..3 , then you return 0
            return 0;
        int res = 0; // res of your function
        for(long i=start+1;i<n;i++){
            res+=start*i*sum(i+1,n); // here you take for example 1*2*sum(3,5) + 1*3*sum(4,5).... ect

        }

        return res+M(start+1); // return res and start again from start+1 wich would be 2.

    }
    public static long sum (long i, long n)
    {
        if(i>n)
            return 0;
        double s1 = n*(n+1)/2;
        double s2 = i*(i-1)/2;
        return (long)(s1-s2);
    }
    public static void main(String[] args) {
        System.out.println(M(1));
    }

Hope it helped

Upvotes: 2

antonpp
antonpp

Reputation: 2383

I am not sure about your algorithm, but you certainly messed up with your sum function. The problem you have is connected to type casting and division of integer numbers. Try something like this:

public static long sum (long i, long n)
{
    final long s1 = n * (n + 1) / 2;
    final long s2 = (i * i - i) / 2;
    return s1 - s2 ;
}

Upvotes: 2

Related Questions