Problem 183: Maximum Product of Parts

Project Euler Problem 183 Solution

EulerSolve provides an optimized solution for Project Euler Problem 183, Maximum Product of Parts, with C++, Python, Java, and a step-by-step mathematical explanation.

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$....

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

Project Euler problem page: Problem 183 - Maximum Product of Parts
Natural logarithm and the constant $e$: Wikipedia - Natural logarithm
Terminating decimal criterion: Wikipedia - Terminating decimals
Greatest common divisor: Wikipedia - Greatest common divisor

Problem 183 source code

C++

#include <cmath>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>

namespace {

using i64 = std::int64_t;

struct Options {
    int from = 5;
    int to = 10000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }

    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--from=", options.from) ||
            parse_int_after_prefix(arg, "--to=", options.to)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.from >= 2 && options.to >= options.from;
}

int best_k(const int n) {
    int k = static_cast<int>(std::floor(static_cast<double>(n) / std::exp(1.0)));
    if (k < 1) {
        k = 1;
    }

    auto score = [&](const int x) {
        return static_cast<double>(x) * (std::log(static_cast<double>(n)) - std::log(static_cast<double>(x)));
    };

    const int k2 = k + 1;
    return (score(k2) > score(k)) ? k2 : k;
}

int D(const int n) {
    const int k = best_k(n);
    int q = k / std::gcd(n, k);

    while ((q % 2) == 0) {
        q /= 2;
    }
    while ((q % 5) == 0) {
        q /= 5;
    }

    return (q == 1) ? -n : n;
}

i64 solve(const int from, const int to) {
    i64 sum = 0;
    for (int n = from; n <= to; ++n) {
        sum += D(n);
    }
    return sum;
}

bool run_checkpoints() {
    if (solve(5, 100) != 2438) {
        std::cerr << "Checkpoint failed for [5,100]" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.from, options.to) << '\n';
    return 0;
}

Python

# Problem 183: Maximum product from partitions.
# D(N) = -N if N/k has terminating decimal, +N otherwise.
import math

def solve():
    total = 0
    for n in range(5, 10001):
        k = round(n / math.e)
        q = k // math.gcd(n, k)
        while q % 2 == 0: q //= 2
        while q % 5 == 0: q //= 5
        total += -n if q == 1 else n
    print(total)

solve()

Java

public class Euler183 {
    static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    public static void main(String[] args) {
        long total = 0;
        for (int n = 5; n <= 10000; n++) {
            int k = (int) Math.round((double) n / Math.E);
            if (k < 1)
                k = 1;
            int q = k / gcd(n, k);
            while (q % 2 == 0)
                q /= 2;
            while (q % 5 == 0)
                q /= 5;
            total += q == 1 ? -n : n;
        }
        System.out.println(total);
    }
}