Project Euler 78

发表于 2022-05-02 更新于 2023-07-03 分类于 Project Euler 阅读次数： 40 本文字数： 710 阅读时长 ≈ 1 分钟

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

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.

解决方案

本题所使用的的状态转移方程和第 76 题完全一致。不过，由于本体求的是第一个 $p (n)$ 能被 $10^{6}$ 整除，因此需要更快的方法。

将 $p (n)$ 的前一些项放进 OEIS 查询，结果为 A000041。

在 FORMULA 一栏中可以发现以下信息：

a(n) - a(n-1) - a(n-2) + a(n-5) + a(n-7) - a(n-12) - a(n-15) + ... = 0, where the sum is over n-k and k is a generalized pentagonal number (A001318) <= n and the sign of the k-th term is (-1)^([(k+1)/2]). See A001318 for a good way to remember this!

其中，数列 A001318 是一种广义五边形数。

另外，符号位由确定广义五边形数的自变量的绝对值决定。

处理以上各种细节，最终可以得到 $p (n)$ 的式子为：

$p (n) = {\begin{aligned} 1 & if n = 0 \\ \sum_{| m | \geq 1, \frac{m (3 m - 1)}{2} \leq n} (- 1)^{m + 1} p (n - \frac{m (3 m - 1)}{2}) & else \end{aligned}$

由于广义五边形数增长是二次的，因此计算 $p (N)$ 的时间复杂度缩减到了 $O (N \sqrt{N})$ 。

代码

from itertools import count

mod = 10 ** 6


def gen_pentagonal():
    for i in count(1, 1):
        yield i * (3 * i - 1) // 2
        yield i * (3 * i + 1) // 2


p = [1]

for n in count(1, 1):
    i = 0
    val = 0
    for m in gen_pentagonal():
        if m > n:
            break
        sgn = i >> 1 & 1
        if sgn == 0:
            val = (val + p[n - m]) % mod
        else:
            val = (val - p[n - m] + mod) % mod
        i += 1
    if val == 0:
        ans = n
        break
    p.append(val)
print(ans)