Project Euler 183

题目

Maximum product of parts

Let $N$ be a positive integer and let $N$ be split into $k$ equal parts, $r = \dfrac{N}{k}$, so that $N = r + r + \dots + r$.

Let $P$ be the product of these parts, $P = r × r × \dots × r = r^k$.

For example, if $11$ is split into five equal parts, $11 = 2.2 + 2.2 + 2.2 + 2.2 + 2.2$, then $P = 2.2^5 = 51.53632$.

Let $M(N) = P_max$ for a given value of $N$.

It turns out that the maximum for $N = 11$ is found by splitting eleven into four equal parts which leads to $P_{\max} = (\dfrac{11}{4})^4$; that is, $M(11) = \dfrac{14641}{256} = 57.19140625$, which is a terminating decimal.

However, for $N = 8$ the maximum is achieved by splitting it into three equal parts, so $M(8) = \dfrac{512}{27}$, which is a non-terminating decimal.

Let $D(N) = N$ if $M(N)$ is a non-terminating decimal and $D(N) = -N$ if $M(N)$ is a terminating decimal.

For example, $\sum D(N)$ for $5 \le N \le 100$ is $2438$.

Find $\sum D(N)$ for $5 \le N \le 10000$.

解决方案

令函数$y(k)=\left(\dfrac{N}{k}\right)^k$，其中$k\in \mathbb{N^+}$。

由于函数$y(k)$的定义域是在整数域上，不好通过求导求最大值，因此将整数域扩展到实数域。

令$z(x)=\left(\dfrac{N}{x}\right)^x$，其中$x\in \mathbb{R}$。

对$z(x)$求导，计算得$z$的导数$z’(x)=\left(\dfrac{N}{x}\right)^x\cdot \left(\ln\dfrac{N}{x}-1\right)$。

令$z’(x)=0$，那么可以计算得到$x=\dfrac{N}{e}$，$z(x)$在$x_0=\dfrac{N}{e}$时将会取到最大值。

回到函数$y(k)$，那么如果$y$要取到最大值，那么最大值点$k$为$\left\lfloor\dfrac{N}{e}\right\rfloor,\left\lceil\dfrac{N}{e}\right\rceil$两个值之一。

因此，直接将它们代入函数$y(k)$代入，这种做法是可行的，不过由于$x_0=\dfrac{N}{e}$是在指数上出现的，因此直接代入计算，可能会导致结果失真。这里取而代之的方法是，代入$y(k)$的对数函数$\ln y(k)=k(\ln N-\ln k)$进行比较计算。

最终找到最大值点$k_0$后，开始解决最大值是否为有限小数的问题。

而这个问题比较简单，只需要判断分数$\dfrac{N}{k_0}$是否为有限小数即可。

代码

from math import e, ceil, floor, log, gcd

N = 10000
ans = 0
for n in range(5, N + 1):
    val = n / e
    l, r = floor(val), ceil(val)
    logfl, logfr = l * log(n / l), r * log(n / r)
    if logfl > logfr:
        x = l
    else:
        x = r
    x //= gcd(x, n)
    while x % 5 == 0:
        x //= 5
    while (x & 1) == 0:
        x >>= 1
    if x == 1:
        ans -= n
    else:
        ans += n
print(ans)