Project Euler Problem 183

Statement

et N be a positive integer and let N be split into k equal parts, r = N/k, so that N = r + r + … + r.
Let P be the product of these parts, P = r r … r = rk.

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

Let M(N) = Pmax 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 Pmax = (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, ΣD(N) for 5 N 100 is 2438.

Find ΣD(N) for 5 N 10000.

Solution

To get the solution for this I used the help from Wolfram Alpha. I entered the formula 8^n / n^n and it says the maximum is located in 8 / $e$. That applies to any value so we translate that easily into code to determine the denominator.

Now, that we know the denominator we need to determine whether it is a terminating or non-terminating decimal. A terminating decimal is a fraction whose denominator's prime factors are only 2 and 5, this is easily verified.

from math import ceil, e, floor
from fractions import gcd
 
if __name__ == '__main__':
    result = 0
    print(e)
    for n in range(5, 10001):
 
        denom = round(n / e)
        n_2 = n
        d = gcd(n_2, denom)
        while d > 1:
            n_2 /= d
            denom /= d
            d = gcd(n_2, denom)
        while denom % 2 == 0:
            denom /= 2
        while denom % 5 == 0:
            denom /= 5
        if denom == 1:
            result -= n
        else:
            result += n
    print("The result is:", result)

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License