Solution

Answer: 48861552

We seek

$$\sum_{N=5}^{10000} D(N),$$

where $D(N)=N$ if the maximizing product $M(N)$ is a non-terminating decimal, and $D(N)=-N$ otherwise.

The key is to determine, for each $N$, whether the optimal product

$$M(N)=\left(\frac Nk\right)^k$$

is terminating or not.

1. Mathematical analysis

For fixed $N$, define

$$f(k)=\left(\frac Nk\right)^k.$$

We maximize this over positive integers $k$.

Taking logs:

$$\log f(k)=k(\log N-\log k).$$

Treat $k$ as real and differentiate:

$$\frac{d}{dk}\bigl(k(\log N-\log k)\bigr) =\log N-\log k-1.$$

Setting this equal to zero:

$$\log\frac Nk=1 \quad\Longrightarrow\quad \frac Nk=e \quad\Longrightarrow\quad k=\frac Ne.$$

Hence the maximizing integer $k$ is the nearest integer to $N/e$.

More precisely:

$$k_1=\left\lfloor \frac Ne \right\rfloor,$$

then compare $f(k_1)$ and $f(k_1+1)$.

A standard fact for this problem is that the maximizing integer is always either

$$\left\lfloor \frac Ne \right\rfloor \quad\text{or}\quad \left\lfloor \frac Ne \right\rfloor+1.$$

When is $M(N)$ terminating?

Suppose the maximizing $k$ is chosen.

Then

$$M(N)=\left(\frac Nk\right)^k.$$

Reduce the fraction:

$$\frac Nk=\frac ab$$

in lowest terms.

Then

$$M(N)=\left(\frac ab\right)^k.$$

A rational number has a terminating decimal iff its reduced denominator has no prime factors other than $2$ and $5$.

So we only need to know whether the reduced denominator $b$ contains primes besides $2,5$.

But

$$b=\frac{k}{\gcd(N,k)}.$$

Therefore:

compute

$$d=\frac{k}{\gcd(N,k)};$$

repeatedly divide out factors of $2$ and $5$;
if the result is $1$, then $M(N)$ terminates;
otherwise it does not.

Thus:

$$D(N)= \begin{cases} -N & \text{if } d \text{ has only factors }2,5,\ +N & \text{otherwise.} \end{cases}$$

2. Determining the optimal $k$

We compare

$$\left(\frac N{k}\right)^k$$

for consecutive integers.

Instead of huge powers, compare logarithms:

$$k\log\frac Nk.$$

Define

$$g(k)=k\log\frac Nk.$$

Then the maximizing integer is:

k = floor(N/e)
if g(k+1) > g(k):
    k += 1

3. Python implementation

import math
from math import gcd

def optimal_k(N):
    """
    Return the integer k maximizing (N/k)^k.
    """
    k = int(N / math.e)

    # Compare logarithms to avoid huge numbers
    g1 = k * math.log(N / k)
    g2 = (k + 1) * math.log(N / (k + 1))

    if g2 > g1:
        k += 1

    return k

def terminating_decimal(N):
    """
    Return True iff M(N) is a terminating decimal.
    """
    k = optimal_k(N)

    # Reduced denominator of N/k
    d = k // gcd(N, k)

    # Remove all factors of 2
    while d % 2 == 0:
        d //= 2

    # Remove all factors of 5
    while d % 5 == 0:
        d //= 5

    return d == 1

def compute(limit):
    total = 0

    for N in range(5, limit + 1):
        if terminating_decimal(N):
            total -= N
        else:
            total += N

    return total

# Verify the example
print(compute(100))      # should be 2438

# Final answer
print(compute(10000))

4. Code walkthrough

`optimal_k(N)`

k = int(N / math.e)

The continuous optimum occurs at $N/e$, so the best integer is near this value.

g1 = k * math.log(N / k)
g2 = (k + 1) * math.log(N / (k + 1))

We compare logarithms instead of the products themselves.

Since logarithm is increasing,

$$f(k+1)>f(k) \iff \log f(k+1)>\log f(k).$$

if g2 > g1:
    k += 1

Choose whichever integer gives the larger product.

`terminating_decimal(N)`

d = k // gcd(N, k)

This is exactly the denominator of $N/k$ in lowest terms.

while d % 2 == 0:
    d //= 2

while d % 5 == 0:
    d //= 5

A terminating decimal can only have denominator factors $2$ and $5$.

return d == 1

If nothing remains, the decimal terminates.

Example checks

$N=11$

Optimal $k=4$.

$$M(11)=\left(\frac{11}{4}\right)^4.$$

Reduced denominator is $4=2^2$, so terminating.

Hence

$$D(11)=-11.$$

$N=8$

Optimal $k=3$.

$$M(8)=\left(\frac83\right)^3=\frac{512}{27}.$$

Denominator contains factor $3$, so non-terminating.

Hence

$$D(8)=+8.$$

The program also reproduces the given check:

$$\sum_{N=5}^{100} D(N)=2438.$$

5. Final verification

The computation is efficient:

only $10^4$ values,
each requiring a few arithmetic operations and gcd,
overall essentially instantaneous.

The example sum matches the problem statement, strongly confirming correctness.

The final computed value is:

Answer: 48861552

Project Euler Problem 183