题目

Problem 614: Special partitions 2

An integer partition of a number n is a way of writing n as a sum of positive integers. Partitions that differ only by the order of their summands are considered the same.

We call an integer partition special if 1) all its summands are distinct, and 2) all its even summands are also divisible by 4.
For example, the special partitions of 10 are:
10 = 1+4+5 = 3+7 = 1+9
The number 10 admits many more integer partitions (a total of 42), but only those three are special.

Let be P(n) the number of special integer partitions of n. You are given that P(1) = 1, P(2) = 0, P(3) = 1, P(6) = 1, P(10) = 3, P(100) = 37076 and P(1000) = 3699177285485660336.

Find . Give the result modulo 109+7.

整数分拆的生成函数

《整数分拆》第 42 页(其中的“部分”就是题目中的“summands”):

根据上面的第 1 个公式,P(n) 的生成函数是:

因此,我们有以下 Julia 程序:

using Nemo
n = 10^4; m = 10^9+7
R,x = PowerSeriesRing(ResidueRing(ZZ,m),n+1,"x")
G = prod([1 + x^k for k = 1 : n if k % 4 != 2])
println(sum([coeff(G,i) for i = 1 : n]))

在我的 4GB 内存的计算机上,这个程序运行 5 秒,计算到 104。如果要计算到 105,就内存溢出了。

Euler 五角数定理

根据《整数分拆》第 46 页的公式(5.13):

利用 ,我们可以把生成函数 G(x) 从连乘积转化为求和的形式:

因此,我们有以下 Julia 程序:

using Nemo
n = 10^7; m = 10^9+7
z = div(1 + floor(Int64, sqrt(24*n + 1)), 6)
R,x = PowerSeriesRing(ResidueRing(ZZ,m), n+1, "x")
ϕ(a) = sum([(-1)^i*x^div(a*i*(3*i-1),2) for i = -z:z])
G = ϕ(2)^2*ϕ(8)*inv(ϕ(1)*ϕ(4)^2)
println(sum([coeff(G,i) for i = 1:n]))

这个程序第 3 行的 z 是方程 z(3z-1)/2 = n 的正根。运行时间是 9 分 39 秒。

参考资料

  1. 《整数分拆》,George E. Andrews, Kimmo Eriksson 著,傅士硕、杨子辰译,科学出版社,2017年9月第1版
  2. Wikipedia: Partition (number theory)
  3. Wikipedia: Euler function
  4. Wikipedia: Pentagonal number theorem