0%

Problem 78


Problem 78


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 separated into piles in exactly seven different ways, so $p(5)=7$.

$$
\begin{aligned}
&\text{OOOOO}\\
&\text{OOOO O}\\
&\text{OOO OO}\\
&\text{OOO O O}\\
&\text{OO OO O}\\
&\text{OO O O O}\\
&\text{O O O O O}
\end{aligned}
$$

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


硬币分拆

记$p(n)$是将$n$枚硬币分拆成堆的不同方式数。例如,$5$枚硬币分拆成堆有$7$种的不同方式,因此$p(5)=7$。

$$
\begin{aligned}
&\text{OOOOO}\\
&\text{OOOO O}\\
&\text{OOO OO}\\
&\text{OOO O O}\\
&\text{OO OO O}\\
&\text{OO O O O}\\
&\text{O O O O O}
\end{aligned}
$$

求最小的使$p(n)$能被一百万整除的$n$。