Project Euler Problem 78 Solution

Project Euler Problem 78 Statement

Let $p(n)$ represent the number of different ways in which $n$ coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so $p(5)=7$.

OOOOO
OOOO O
OOO OO
OOO O O
OO OO O
OO O O O
O O O O O

Find the least value of $n$ for which $p(n)$ is divisible by one million.

Solution

HackerRank Project Euler Problem 78 overview:

HackerRank’s version of Project Euler Problem 78 focuses on the partition function $p(n)$: the number of ways $n$ can be written as a sum of positive integers, disregarding order.

Solution Detail

Modulus Setup:
We define $ \text{MOD} = 10^9 + 7 $. All arithmetic on the partition function will be done modulo this value.
Array Initialization:
p = [1] + [0]*60000
The list p will hold our partition values $ p(0), p(1), p(2), \dots, p(60000) $, each reduced modulo $ 10^9 + 7 $. By convention, $ p(0) = 1 $ because there is exactly one way to partition 0 (using no parts).
Generalized Pentagonal Numbers:
We generate them with the formula $ \frac{k(3k \pm 1)}{2} $, where $ k $ runs from 1 to 201. This is done by:
```
g = lambda k,s: k*(3*k + s)//2
pent = [g(k,s) for k in range(1,202) for s in (-1,1)]
```
Each $ k $ produces two values: $ \frac{k(3k - 1)}{2} $ and $ \frac{k(3k + 1)}{2} $. These are used in Euler's pentagonal number theorem.
How we determine the number of pentagonals needed
Let's solve the inequality:
\[ \frac{i(3i - 1)}{2} \ge 60{,}000. \]
Multiplying both sides by 2 gives:
\[ i(3i - 1) \ge 120{,}000, \]
or
\[ 3i^2 - i - 120{,}000 \ge 0. \]
Solving this approximately via the quadratic formula,
\[ i = \frac{1 \pm \sqrt{1 + 4 \times 3 \times 120{,}000}}{2 \times 3} = \frac{1 \pm \sqrt{1 + 1{,}440{,}000}}{6} = \frac{1 \pm \sqrt{1{,}440{,}001}}{6}. \]
Since $\sqrt{1{,}440{,}001} \approx 1200$ , we have
\[ i \approx \frac{1 + 1200}{6} \approx 200.166\ldots \]
Hence $i \approx 201$ would make $p_i$ exceed 60,000.
Computing $ p(n) $ via Euler’s Recurrence:
\[ p(n) \;=\; \sum_{k=1}^{\infty} \Bigl[\,(-1)^{k+1} p\bigl(n - \tfrac{k(3k-1)}{2}\bigr)\;+\;(-1)^{k+1} p\bigl(n - \tfrac{k(3k+1)}{2}\bigr)\Bigr]. \] In the code, this appears as:
```
for n in range(1, 60001):
    p[n] = sum(
        p[n - v] * (1 - (k & 2))
        for k, v in enumerate(pent)
        if v <= n
    ) % MOD
```
Here's what happens:
- We iterate n from 1 to 60000.
- For each n, we sum contributions from terms p[n-v] where v is a generalized pentagonal number $ \le n $.
- The factor (1 - (k & 2)) produces the sign pattern $ +, +, -, -, +, +, \dots $, matching Euler's identity.
- We take the result modulo $ 10^9 + 7 $ and store it in p[n].
Answering Queries:
Finally, for each test query $ N $, we simply print p[N]:
```
for _ in range(int(input())):
    print(p[int(input())])
```
Because p was precomputed, each query runs in constant time.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 78

HackerRank Project Euler 78: How many different ways can $N$, $(2\le N\le 6\times 10^4)$ coins be separated into piles?. Mod answers by $10^9+7$.

Python Source Code

MOD = 10**9 + 7
p = [1]+[0]*60000
g = lambda k,s: k*(3*k+s)//2
pent = [g(k,s)for k in range(1,202) for s in(-1,1)]

for n in range(1,60001):
    p[n] = sum(p[n-v] * (1-(k&2)) for k,v in enumerate(pent) if v<=n) % MOD

for _ in range(int(input())):
    print(p[int(input())])

Last Word

To solve the Project Euler version, remove the mod and just find the first index in p[] where the value in ends in '000000', i.e. %1000000 == 0. Hint: It's less than 60,000.