Project Euler : Probelm 78

The Project Euler : Problem 78 has been solved by comparatively less number of people than other problems on the same page. It is stated as

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.
Find the least value of n for which p(n) is divisible by one million.

This is exactly the same as integer partitions - which is the number of ways in which a given natural number can be written as sum of smaller natural numbers. You can find the proof of the formula in this discussion.

I previously described two algorithms to calculate the integer partitions. The recursive algorithm suffers from being very slow, to the point of being useless. The iterative algorithm has acceptable speed, but its memory requirements prohibit it from being used for solving this problem.

So we need a much better way to calculate integer partitions. Fortunately, we can use some mathematics. You can check Wikipedia article on integer partitions, which mentions the following formula.

P(n) = P(n-1) + P(n-2) - P(n-5) - P(n-7) + …

There 2 things to notice.

1. The sign of each term changes based on the formula mentioned below.
2. Every term on the right hand side is of the form N-x. This x has to be a “Pentagonal Number” and is also given by the same formula below.

More concisely,

P(n) = SUM of [ (-1)^k . P (n - k(3k-1)/2) ]
for both positive and negative values of k as it goes from 1 to N.
Of course P(m) = 0, for any m less than 0.

We can use it to solve the Project Euler Problem 78 in a straight-forward way.

We start with calculating P(n) from 1 onwards up to an arbitrary number, say 1 million. To calculate P(N) at any iteration we have a nested loop that goes from N down to 1, examining only those numbers given by N-x, where x is a pentagonal number. We must consider both negative and positive values of x at every iteration and use proper sign to either add or subtract P(N-x). We will stop when we find a value of P(n) which is divisible by 1 million.

One thing to keep in mind is, the values for P(N) can get fairly large. There is no need to use anything like BigInteger, as we are only interested in the divisibility test, hence we can use the modulo arithmetic.

Here is an outline of the algorithm.

public static long GetNWithModulo1MPartitions () {

    final int MOD = 1000000 ; // divisible by 1M, from problem description
    finat int MAX = 1000000 ; // arbitrarily choosing max value for N
    int [] NumPartitions = new int [MAX] ;

    NumPartitions [0] = 1 ;
    NumPartitions [1] = 1 ;
    NumPartitions [2] = 2 ;

    for (int i = 3 ; i <= MAX ; i++ ) {
   
    long pn = 0 ;

    int sign = 0 ;
    long m1val = 0 ;
    long m2val = 0 ;

    int j ;
    for (j = 1 ; j <= i ; j++) {
        int m1 = i - (j * (3*j - 1) / 2) ; // using positive j
        int m2 = i - ((-1*j) * (3*(-1*j) - 1) / 2) ; // using negative j
        sign = (j%2 == 0) ? -1 : 1 ; // do we add or subtract ?
        // NOTE : in the following
        // if m1 or m2 is negative, the number of partitions is 0 by definition
        // We will add both, as one of them will be zero.
        m1val = (m1 < 0) ? 0 : (NumPartitions[m1] % MOD) ;
        m2val = (m2 < 0) ? 0 : (NumPartitions[m2] % MOD) ;

        pn = (pn + (sign * m1val) + (sign * m2val) ) % MOD ; // the real equation

        if ( pn < 0 ) {
            pn += MOD ; // force positive values
        } //
    }

    NumPartitions[i] = pn ;

    if ( pn == 0 ) {
        System.out.println ("Found N where P(N) is divisible by " + MOD + " and N = " + i) ;
        return ;
    }
    }

} //

That's a bit complicated. It certainly is too much for an interview question, even after giving the formula. The previous article on a recursive, as well as an iterative algorithm,  is a much better choice for a programming interview.