Coin Partitions

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.

The function $p(n)$ that you’ve asked about represents the partition function in number theory. This function is quite complex to calculate and requires understanding of concepts beyond basic mathematics, including combinatorics and series. Nonetheless, there is a simple way to calculate $p(n)$ using pentagonal number theorem.

The problem at hand, however, asks when the value $p(n)$ becomes divisible by one million. To solve this, we have to generate partition values for increasing $n$ until we find one that is divisible by one million. Unfortunately, computing the partition function directly is inefficient because the number of partitions grows very rapidly.

However, there are programming algorithms designed specifically for generating partitions of a number, and these algorithms are designed in such a way that they can quickly and efficiently generate the number of partitions of $n$.

Therefore, the most efficient way to solve this problem would likely be to use a computer program designed specifically for generating partitions of a number, especially if we are looking for a relatively high value of $n$.

Such a problem can be solved by writing a simple Python script, using dynamic programming concept.

“`python
def find_least_n():
partitions = [1]
n = 1
while partitions[-1] % 1000000 != 0:
i = 0
pentagonal = 1
partitions.append(0)

while pentagonal <= n: sign = -1 if i % 4 > 1 else 1
partitions[n] += partitions[n – pentagonal] * sign
partitions[n] %= 1000000 # We only need to track the last 6 digits
i += 1

j = i // 2 + 1 if i % 2 == 0 else -(i // 2 + 1)
pentagonal = j * (3 * j – 1) // 2

n += 1

return n – 1

print(find_least_n())
“`

Unfortunately, this is quite an intensive computation. The correct answer turns out to be $n=55374$.

More Answers: