Detailed mathematical approach

Problem Summary

For each integer \(n\ge 5\), we split \(n\) into \(k\) equal real parts, so each part is \(n/k\), and we consider the product

$M(n,k)=\left(\frac{n}{k}\right)^k.$

Among all positive integers \(k\), we choose the value that maximizes this expression and call the resulting maximum \(M(n)\). The function \(D(n)\) is then defined by the decimal expansion of \(M(n)\): if \(M(n)\) is a terminating decimal, we take \(D(n)=-n\); otherwise we take \(D(n)=+n\).

The task is to evaluate \(D(n)\) for every \(n\) from 5 through 10000 and add the results. The challenge is not large-number arithmetic; it is identifying the maximizing \(k\) and deciding the terminating-decimal condition without ever expanding huge powers explicitly.

Mathematical Approach

The whole solution rests on two independent facts. First, the maximizing number of equal parts is always extremely close to \(n/e\). Second, after we reduce \(n/k\) to lowest terms, only the prime factors of its denominator matter for decimal termination.

Locating the maximizing number of parts

For fixed \(n\), define

$f_n(k)=\left(\frac{n}{k}\right)^k.$

Comparing such values directly is inconvenient, so we take logarithms and study

$\phi_n(x)=\log f_n(x)=x(\log n-\log x)$

for real \(x>0\). Differentiating gives

$\phi_n'(x)=\log\!\left(\frac{n}{x}\right)-1,\qquad \phi_n''(x)=-\frac{1}{x} \lt 0.$

Because the second derivative is always negative, \(\phi_n\) is strictly concave, so it has a unique real maximum. Setting \(\phi_n'(x)=0\) yields

$x=\frac{n}{e}.$

Therefore the maximizing integer \(k\) must be one of the integers nearest to \(n/e\). In practice this means either rounding \(n/e\) to the nearest integer, or comparing the two neighbors \(\left\lfloor n/e\right\rfloor\) and \(\left\lfloor n/e\right\rfloor+1\) with logarithms.

Why the denominator test is enough

Let \(k_n\) be the maximizing integer for \(n\). Reduce the fraction \(n/k_n\) to lowest terms:

$\frac{n}{k_n}=\frac{a}{q},\qquad \gcd(a,q)=1.$

Then

$M(n)=\left(\frac{n}{k_n}\right)^{k_n}=\left(\frac{a}{q}\right)^{k_n}=\frac{a^{k_n}}{q^{k_n}}.$

Since \(\gcd(a,q)=1\), we also have \(\gcd(a^{k_n},q^{k_n})=1\), so this fraction is already reduced. That means the reduced denominator of \(M(n)\) is exactly \(q^{k_n}\).

A rational number has a terminating decimal expansion if and only if its reduced denominator has no prime factors other than 2 and 5. Therefore \(M(n)\) terminates exactly when \(q\) itself has the form

$q=2^\alpha 5^\beta$

for some integers \(\alpha,\beta\ge 0\). This is why the implementations only compute

$q=\frac{k_n}{\gcd(n,k_n)}$

and then repeatedly divide out factors of 2 and 5.

Worked examples

Take \(n=11\). Since \(11/e\approx 4.046\), the only serious integer candidates are \(k=4\) and \(k=5\). Their products are

$\left(\frac{11}{4}\right)^4=57.19140625,\qquad \left(\frac{11}{5}\right)^5=51.53632,$

so the maximum occurs at \(k_{11}=4\). The reduced fraction is \(11/4\), hence \(q=4=2^2\). Therefore

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

has a terminating decimal expansion, and \(D(11)=-11\).

For contrast, take \(n=8\). Here \(8/e\approx 2.943\), so the maximizing integer is \(k_8=3\). Then

$\frac{8}{3}$

is already reduced, so \(q=3\). Because 3 is neither 2 nor 5, the denominator of \(M(8)=(8/3)^3=512/27\) contains a forbidden prime factor, so the decimal expansion does not terminate and \(D(8)=+8\).

The final summation

Once the sign rule is understood, the rest of the problem is completely separable by \(n\). For each integer \(n\in[5,10000]\), we find the maximizing \(k_n\), form \(q=k_n/\gcd(n,k_n)\), test whether \(q\) contains primes other than 2 and 5, and contribute either \(-n\) or \(+n\). Symbolically,

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

is computed as a simple loop with no interaction between different values of \(n\).

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical pipeline, with a small difference in how they choose the optimal number of parts. The C++ implementation computes the two neighboring integers around \(n/e\) and compares their logarithmic scores \(k(\log n-\log k)\), which avoids constructing the power itself. The Python and Java implementations take the nearest integer to \(n/e\), which matches the same concavity argument.

After choosing that maximizing integer, the implementation reduces the fraction \(n/k\) indirectly by computing \(k/\gcd(n,k)\). This is the reduced denominator \(q\). It then removes every factor of 2 and every factor of 5 from \(q\). If nothing remains, the maximal product has a terminating decimal expansion, so the running total is decreased by \(n\). Otherwise the running total is increased by \(n\).

No big-integer exponentiation is needed anywhere. The code never forms \(M(n)\) itself, because the logarithmic comparison is enough to find the maximizing \(k\), and the denominator criterion is enough to decide the sign of \(D(n)\).

Complexity Analysis

Each value of \(n\) is processed independently. The work consists of one constant-size floating-point optimization step, one greatest-common-divisor computation, and a short loop that strips factors of 2 and 5 from the reduced denominator. The gcd step costs \(O(\log n)\), and the factor stripping is also \(O(\log n)\) in the worst case.

If the upper limit is \(U\), the total running time is \(O(U\log U)\); for the specific range \(5\le n\le 10000\), this is effectively a linear scan with very small constant factors. The auxiliary memory usage is \(O(1)\).

Footnotes and References

1. Project Euler problem page: Problem 183 - Maximum Product of Parts
2. Natural logarithm and the constant \(e\): Wikipedia - Natural logarithm
3. Terminating decimal criterion: Wikipedia - Terminating decimals
4. Greatest common divisor: Wikipedia - Greatest common divisor