Project Euler 831

题目

Triple Product

Let \(g(m)\) be the integer defined by the following double sum of products of binomial coefficients:

\[\sum_{j=0}^m\sum_{i = 0}^j (-1)^{j-i}\binom mj \binom ji \binom{j+5+6i}{j+5} \]

You are given that \(g(10) = 127278262644918\).

Its first (most significant) five digits are \(12727\).

Find the first ten digits of \(g(142857)\) when written in base \(7\).

解决方案

假设\(c[p(x),k]\)是多项式\(p(x)\)中，项\(x^k\)的系数。可以知道，这个定义有如下性质：

\[c[p(x),k]=c\left[\dfrac{p(x)}{x^k},0\right]\]

令\(\displaystyle{h(j)=\sum_{i=0}^j(-1)^{j-i}\binom ji \binom{j+5+6i}{j+5}}\)，那么有\(\displaystyle{g(m)=\sum_{j=0}^m} \dbinom{m}{j} h(j)\)。

首先考虑\(h(j)\)。可以知道

\(\begin{aligned} h(j)&=\sum_{i=0}^j(-1)^{j-i}\binom ji \cdot c[(x+1)^{j+5+6i},j+5]\\ &=c\left[(x+1)^{j+5}\cdot\sum_{i=0}^j\left(\dbinom {j}{i}\cdot(-1)^{j-i}\cdot(x+1)^{6i}\right),j+5\right]\\ &=c\left[(x+1)^{j+5}\cdot((x+1)^6-1)^j,j+5\right]\\ &=c[(x+1)^5\cdot((x+1)^7-x-1)^j,j+5]\\ &=c\left[(x+1)^5\cdot\left(\dfrac{(x+1)^7-x-1}{x}\right)^j,5\right] \end{aligned}\)

那么最终得出\(g(m)\)有

\(\begin{aligned} g(m)&=\sum_{j=0}^m \dbinom{m}{j} h(j)\\ &=c\left[(x+1)^5\cdot\sum_{j=0}^m \dbinom{m}{j}\left(\dfrac{(x+1)^7-x-1}{x}\right)^j,5\right]\\ &=c\left[(x+1)^5\cdot\left(\dfrac{(x+1)^7-x-1}{x}+1\right)^m,5\right]\\ &=c\left[(x+1)^5\cdot\left(\dfrac{(x+1)^7-1}{x}\right)^m,5\right]\\ &=c[(x+1)^5\cdot(7x^5+21x^4+35x^3+25x^2+21x+7)^m,5]&\qquad(1)\\ &=7^m\cdot c[(x+1)^5\cdot(x^5+3x^4+5x^3+5x^2+3x+1)^m,5]\\ \end{aligned}\)

其中，步骤\((1)\)说明我们只关心次数为\(0\sim 5\)中产生的结果，且并不关心更高次项的结果。

接下来的问题只剩下求\(c[(x+1)^5\cdot(x^5+3x^4+5x^3+5x^2+3x+1)^m,5]\)的值。方法也很简单，令\(f(x)=(x+1)^5\cdot(x^5+3x^4+5x^3+5x^2+3x+1)^m\)，那么相当于计算\(\dfrac{f^{(5)}(0)}{5!}\)的值。

使用Mathematica的如下命令计算\(\dfrac{f^{(5)}(0)}{5!}\)的值，并得到结果为\(\dfrac{40+474m+1835m^2+2085m^3+765m^4+81m^5}{40}\)。

f[x_] = (x+1)^5 (x^5+3x^4+5x^3+5x^2+3x+1)^m
f'''''[x] / 120

也就是说，最终得到

\[g(m)=7^m\cdot \dfrac{40+474m+1835m^2+2085m^3+765m^4+81m^5}{40}\]

在\(7\)进制下，对一个数乘以\(7^m\)相当于仅仅是将这个数左移了\(m\)位，对最高位数值没有影响，因此计算中不会考虑\(7^m\)这个项。

代码

N = 142857


def base10ToBase7(x):
    s = ""
    while x:
        s, x = str(x % 7) + s, x // 7
    return s


def g(n):
    return (81 * n ** 5 + 765 * n ** 4 + 2085 * n ** 3 + 1835 * n ** 2 + 474 * n + 40) // 40  # * 7 ** n


x = base10ToBase7(g(N))
ans = str(x)[:10]
print(ans)