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$.

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

Solution

Below is an explanation of how this script computes the partition numbers (the number of ways to write an integer as a sum of positive integers, disregarding order) using a known recurrence based on pentagonal numbers. The script applies a classic result from number theory sometimes referred to as the "pentagonal number theorem" or "Euler's pentagonal number formula." It then stores these partition values in a list, using modular arithmetic to keep values within the limits of $10^9 + 7 $. Finally, for each user query, it outputs the precomputed result.

Overview of the Pentagonal Number Formula

1. Pentagonal Numbers
   Euler observed that the generating function for the partition function can be used to derive a recurrence involving generalized pentagonal numbers, which are given by: $$ p_i = \frac{i(3i - 1)}{2} \quad \text{and} \quad \frac{i(3i + 1)}{2}, $$ for integers $i$. In this script, they appear in the form $p = \frac{i (3i - 1)}{2}$ and $p + i$, covering both positive and negative indices of $k$. These numbers are called pentagonal because of their shape in certain geometric constructions.
2. Signs in the Recurrence
   Because of the expansion of the generating function, the signs for these terms follow a repeated pattern of + + - - (or $1,\, 1,\, -1,\, -1$). This pattern ensures that we alternately add and subtract certain partition values, capturing the correct coefficients in the infinite product/series identity used by Euler.

Explanation of the solution

1. Initialization

   MOD = 10**9 + 7
   signs = [1, 1, -1, -1]
   partitions = [1] + [0]*60 000

   • MOD is set to $10^9 + 7$ for modular arithmetic.
   • signs contains the pattern [1, 1, -1, -1] that will be used repeatedly in the recurrence.
   • partitions is a list that will store the number of partitions for each integer $n$. We initialize partitions[0] to 1 (the number of ways to partition zero is 1, by convention) and the rest to 0 up to 60 000.
2. Generate Pentagonal Numbers

   pentagonals = []
   for i in range(1, 202):
       p = i * (3*i - 1) // 2
       pentagonals.extend([p, p+i])

   • We generate generalized pentagonal numbers up to a certain point (in this case, $i$ goes up to 201) to cover enough values for our needs up to n = 60000.
   • The pentagonal numbers p = i * (3*i - 1) // 2 and also p + i, which corresponds to the "negative" indices or the other branch of the formula, are store into the pentagonals[] list for each i.
3. 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.

4. Compute Partition Numbers

   for n in range(1, 60001):
       total = 0
       for idx, val in enumerate(pentagonals):
           if val <= n:
               total += partitions[n - val] * signs[idx % 4]
       partitions[n] = total % MOD

   • We iterate $n$ from 1 to 60,000.
   • For each $n$, we initialize total = 0.
   • We loop over each pentagonal number, val, in pentagonals[] and add or subtract the previously computed partition number partitions[n - val], depending on the sign derived from signs[idx % 4].
   • We then take the result modulo MOD to keep the value within integer limits. This final result is stored as partitions[n].
5. Handling Input Queries

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

   The script then reads the number of queries. For each query, it reads an integer $N$ and directly prints partitions[N], which is the partition number of N modulo $10^9 + 7$.

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$.

Last Word

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