Project Euler Problem 105 Solution: Special Subset Sums: Testing - Python

Project Euler Problem 105 Statement

Let $N$ be a positive integer and let $N$ be split into $k$ equal parts, $r = N/k$, so that $N = r + r + \cdots + r$.
Let $P$ be the product of these parts, $P = r \times r \times \cdots \times 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_{\mathrm{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_{\mathrm{max}} = (11/4)^4$; that is, $M(11) = 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) = 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\limits_{N = 5}^{100} D(N)$ is $2438$.

Find $\sum\limits_{N = 5}^{10000} D(N)$.

Solution

Python Source Code

from math import e, gcd
s = 0
for n in range(5, 10001):
    k = int(n/e)
    k+= (k+1)*(1+1/k)**k <= n
    d = k//gcd(n,k)
    while gcd(d, 10) > 1: d//= gcd(d, 10)
    s+= n if d > 1 else -n
print(s)