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

A positive integer $N$ is split into $k$ equal parts of size $r=N/k$, where $k$ is a positive integer, and $P=r^k$ is the product of the parts; splitting $11$ into five parts, for example, gives $P=2.2^5=51.53632$. Let $M(N)$ be the largest of these products over all $k$, and let $D(N)=N$ if $M(N)$ is a non-terminating decimal and $D(N)=-N$ if it is a terminating decimal. The statement shows that the best split of $11$ has four parts, so that $M(11)=(11/4)^4=14641/256$ is the terminating decimal $57.19140625$, while $8$ is best split into three parts and $M(8)=512/27$ does not terminate. It gives $\sum_{N=5}^{100}D(N)=2438$ and asks for $\sum_{N=5}^{10000}D(N)$. ^[1]

The whole solution in one sentence: the best number of parts is one of the two whole numbers next to $N/e$, an exact comparison of $N$ with the threshold $(k+1)^{k+1}/k^k$ tells which one, and $M(N)$ is a terminating decimal exactly when the denominator of $N/k$ in lowest terms has no prime factors other than $2$ and $5$.

Mathematical Approach

We first find the best number of parts, then decide when the largest product is a terminating decimal, and finally check both steps against the numbers of the statement.

1. Small cases and the number e

For $N=8$ the products for $k=1,2,3,4,5$ are $8$, $16$, $512/27\approx18.96$, $16$ and $32768/3125\approx10.49$; for $N=11$ the products for $k=2,3,4,5$ are about $30.25$, $49.30$, $57.19$ and $51.54$. In both cases the products first rise and then fall, and the best part size, $8/3\approx2.67$ or $11/4=2.75$, is close to $e\approx2.718$. This is no accident. A split into parts of size $r$ has $N/r$ parts, so

$$P=r^{N/r}=\left(r^{1/r}\right)^N,$$

and the best allowed part size is the one that makes $r^{1/r}$ largest. Among all real $r\gt0$ this happens at $r=e$, a fact known as Steiner's problem. ^[2] Indeed, the natural logarithm $\ln$ is increasing, so $r^{1/r}$ is largest where its logarithm $(\ln r)/r$ is largest, and this function has the derivative $(1-\ln r)/r^2$, which is positive for $r\lt e$ and negative for $r\gt e$. So the best $k$ is close to $N/e$, but "close" does not decide between two neighbouring whole numbers; the next sections give an exact rule.

2. One more part: the thresholds

Write $P_k=(N/k)^k$. Going from $k$ to $k+1$ parts multiplies the product by

$$\frac{P_{k+1}}{P_k}=\frac{N\,k^k}{(k+1)^{k+1}}=\frac{N}{t_k},$$

where

$$t_k=\frac{(k+1)^{k+1}}{k^k}.$$

So $k+1$ parts are better than $k$ parts exactly when $N\gt t_k$, and worse exactly when $N\lt t_k$. The first thresholds are $t_1=4$, $t_2=27/4=6.75$, $t_3=256/27\approx9.48$, $t_4=3125/256\approx12.21$, $t_5\approx14.93$, $t_6\approx17.65$ and $t_7\approx20.37$. For $N=11$ we have $t_3\lt11\lt t_4$: four parts beat three, and five parts lose against four, as in the statement.

3. The thresholds increase

Since the derivative of $x\ln x$ is $1+\ln x$,

$$\begin{aligned}\ln t_k&=(k+1)\ln(k+1)-k\ln k\\&=1+\int_k^{k+1}\ln x\,dx.\end{aligned}$$

The integral over $[k+1,k+2]$ is larger than the one over $[k,k+1]$, because $\ln x$ increases, so $t_1\lt t_2\lt t_3\lt\cdots$. Hence the products $P_1,P_2,\dots$ increase as long as $t_k\lt N$ and decrease once $t_k\gt N$, and the largest product can be shared only by two neighbours $k$ and $k+1$ with $N=t_k$. Because $k$ and $k+1$ have no common prime factor, neither do $k^k$ and $(k+1)^{k+1}$, ^[4] so $t_k$ is a fraction in lowest terms and a whole number only for $k=1$. The only tie is therefore $N=t_1=4$, where one part and two parts both give $4$. For every $N\ge5$ the best $k$ is unique: it is the $k$ with $t_{k-1}\lt N\lt t_k$.

4. Where the thresholds lie

The logarithm is concave: its graph lies below its tangent at the midpoint $u=k+\tfrac12$ and above its chord between $x=k$ and $x=k+1$, except at the points where they touch. Over $[k,k+1]$ the tangent $\ln u+(x-u)/u$ has the integral $\ln u$, because $x-u$ averages to zero, and the chord has the integral $(\ln k+\ln(k+1))/2$. This is the Hermite–Hadamard inequality for the convex function $-\ln x$. ^[3] With Section 3 it gives

$$e\sqrt{k(k+1)}\lt t_k\lt e\left(k+\tfrac12\right).$$

For example, $3.844\lt t_1\lt4.077$ and $9.416\lt t_3\lt9.514$. Since $(k+\tfrac12)^2-k(k+1)=\tfrac14$, the two bounds differ by $e/4$ divided by $k+\tfrac12+\sqrt{k(k+1)}\gt2k$, that is, by less than $e/(8k)$, so $t_k$ lies just below $e(k+\tfrac12)$. Two consequences follow.

Two candidates. For the best $k$ we have $N\lt t_k\lt e(k+\tfrac12)$ and $N\gt t_{k-1}\gt e\sqrt{(k-1)k}$, which is at least $e(k-1)$, so $N/e-\tfrac12\lt k\lt N/e+1$: the best $k$ is $\lfloor N/e\rfloor$ or $\lfloor N/e\rfloor+1$.
Rounding is almost always right. Let $j=\lfloor N/e\rfloor$. If $N/e\gt j+\tfrac12$, rounding $N/e$ gives $j+1$, and indeed $N\gt e(j+\tfrac12)\gt t_j$. If $N/e\lt j+\tfrac12$, rounding gives $j$, and this is wrong exactly when $t_j\lt N\lt e(j+\tfrac12)$, that is, when $N$ falls into a window shorter than $e/(8j)$.

The width bound alone does not decide whether a window contains a whole number. A computation in interval arithmetic, which encloses every rounding error, shows that no window with $j\le10^6$ contains one, so rounding gives the best $k$ for every $N$ from $5$ to beyond $2.7$ million. Measured by the distance from $N$ to the nearest threshold, the closest call in the range of the problem is $N=632$: here $632/e\approx232.4998$, and $632$ lies only about $0.00004$ below $t_{232}$, so $232$ parts beat $233$ parts by a factor of just $1+6\cdot10^{-8}$. Such near misses come from very good approximations $2N/(2j+1)$ of $e$: $1264/465$ for $N=632$, $106/39$ for $N=53$, which lies $0.0007$ below $t_{19}$, and $8/3$ for the tie $N=4$ are convergents of the continued fraction $e=[2;1,2,1,1,4,1,1,6,\dots]$, the fractions obtained by cutting it short. ^[6]

5. Terminating decimals

A decimal terminates when it has finitely many digits after the point; a whole number, with none, counts as terminating. Claim. A fraction $a/b$ in lowest terms has a terminating decimal expansion exactly when $b=2^\alpha5^\beta$ for some whole numbers $\alpha,\beta\ge0$. ^[5]

Proof. If the expansion stops after $m$ digits, then $a/b=c/10^m$ for a whole number $c$, so $b$ divides $a\cdot10^m$. Since $b$ has no prime factor in common with $a$, it divides $10^m=2^m5^m$ ^[4] and has no prime factors other than $2$ and $5$. Conversely, if $b=2^\alpha5^\beta$ and $m=\max(\alpha,\beta)$, multiplying the numerator and the denominator by $2^{m-\alpha}5^{m-\beta}$ gives a fraction with the denominator $10^m$, which has at most $m$ digits after the point. $\square$

For example, $M(11)=14641/256$ has $256=2^8$ and needs $8$ digits, $57.19140625$, while $M(8)=512/27$ has $27=3^3$ and is the endless decimal $18.962962\ldots$

6. The denominator of the largest product

For $N=15$ the best split has $k=6$ parts, but $15/6=5/2$: the common factor $3$ cancels and leaves only the prime $2$ in the denominator, while $16/6=8/3$ keeps the factor $3$. In general, let $k$ be the best number of parts and $g=\gcd(N,k)$ the greatest common divisor of $N$ and $k$. Then $N/k=a/q$ in lowest terms, with $a=N/g$ and $q=k/g$, and

$$M(N)=\left(\frac{a}{q}\right)^k=\frac{a^k}{q^k}.$$

Since $a$ and $q$ have no common prime factor, neither do $a^k$ and $q^k$, ^[4] so $q^k$ is the denominator of $M(N)$ in lowest terms, and it has the same prime factors as $q$. By Section 5, $M(N)$ terminates exactly when

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

has no prime factors other than $2$ and $5$. The huge number $M(N)$ itself is never needed. An equivalent form is often handy: let $k'$ be the number left when all factors $2$ and $5$ are divided out of $k$; then $M(N)$ terminates exactly when $k'$ divides $N$, because a prime $p$ other than $2$ and $5$ survives in $q$ exactly when $N$ contains fewer factors $p$ than $k$. In particular, if $k$ has no prime factors other than $2$ and $5$, such as $k=4$, $8$ or $10$, then $k'=1$ and $M(N)$ terminates for every $N$ whose best number of parts is $k$.

7. Worked example: N from 5 to 20

By Section 3 each $k$ is the best number of parts for the $N$ between $t_{k-1}$ and $t_k$. By Section 4, $t_k$ lies between $e(k+\tfrac12)-e/(8k)$ and $e(k+\tfrac12)$, so consecutive thresholds are more than $e-e/(8k)\gt2$ apart and, for $k\ge3$, less than $e+e/16\lt3$; together with $t_2-t_1=2.75$, every $k\ge2$ is the best number of parts for two or three consecutive values of $N$. For $N=5,\dots,20$, with $q=k/\gcd(N,k)$:

$k=2$ for $N=5,6$: $q=2,1$, both terminating, since $M(5)=6.25$ and $M(6)=9$;
$k=3$ for $N=7,8,9$: $q=3,3,1$, so only $M(9)=27$ terminates;
$k=4$ for $N=10,11,12$: $q=2,4,1$, all terminating;
$k=5$ for $N=13,14$: $q=5$, both terminating, for example $M(13)=118.81376$;
$k=6$ for $N=15,16,17$: $q=2,3,6$, so only $M(15)=244.140625$ terminates;
$k=7$ for $N=18,19,20$: $q=7$, none terminating.

The nine terminating cases $N=5,6,9,10,\dots,15$ add up to $95$ and the seven others to $105$, so $\sum_{N=5}^{20}D(N)=105-95=10$.

8. The checkpoint of the statement

The sum of $D(N)$ is the sum of all $N$ minus twice the sum of the $N$ whose $M(N)$ terminates. Between $5$ and $100$ there are $31$ such values: $5$, $6$, $9$–$15$, $21$–$23$, $26$–$28$, $33$, $42$–$44$, $54$, $55$, $66$–$69$, $77$, $81$, $86$–$88$ and $99$. They add up to $1301$, and all $96$ values of $N$ add up to $5040$, so the sum is $5040-2\cdot1301=2438$, the value given in the statement. Some terminating cases need many digits: $M(87)=(87/32)^{32}$ has the denominator $2^{160}$ and $160$ digits after the point.

How the Code Works

The C++ program ^[7] keeps its settings in Options: the range of $N$, by default $5$ to $10000$, and the flag run_checkpoints. parse_arguments accepts --from= and --to=, each followed by decimal digits that parse_int_after_prefix reads, and --skip-checkpoints; an unknown argument, a lower limit below $2$ or an upper limit below the lower one ends the program with exit code $1$. Neither the parsing of the digits nor the int loop counter of solve is protected against overflow, which matters only for limits near $2^{31}$.

best_k implements Section 4. It sets $k=\lfloor n/e\rfloor$ with std::floor and std::exp(1.0), raises it to $1$ if it is $0$, and compares the candidates $k$ and $k+1$ with the lambda score, which returns $x(\ln n-\ln x)=\ln P_x$. Since $\ln P_{k+1}-\ln P_k=\ln n-\ln t_k$, the test score(k2) > score(k) is the comparison $n\gt t_k$ of Section 2 in logarithms, and no power is ever formed. In exact arithmetic this choice is right for every $n$, but the computed scores carry rounding errors that grow with $n$. The smallest $n$ where this matters is $307999$: the exact difference of the two scores is $1.5\cdot10^{-11}$, the computed one $-1.5\cdot10^{-11}$, and best_k returns $113306$ instead of the better $113307$. Both give the same $D(n)$ there, but for $n=3562905$ the program takes $1310719$ parts instead of $1310720=2^{18}\cdot5$ and reports as non-terminating an $M(n)$ that terminates. For $n=4$, where one and two parts tie, both choices give $q=1$. D implements Section 6: it computes q = k / std::gcd(n, k), divides out all factors $2$ and then all factors $5$ in two loops, and returns $-n$ if $1$ remains and $n$ otherwise. solve adds $D(n)$ over the range in the 64-bit type i64; since $|D(n)|=n$, the sum for the default range stays below $5.1\cdot10^7$ in absolute value. run_checkpoints requires solve(5, 100) to be $2438$ and otherwise stops the program with exit code $2$, and main then prints the sum for the range.

The Python program loops over $N=5,\dots,10000$ inside solve, takes k = round(n / math.e), the nearest integer, and applies the same test with math.gcd; it has no options and no checkpoint. Python's round returns an integer and sends halves to the even neighbour. ^[8] The Java program does the same with its own Euclidean gcd and Math.round, which returns a long, sends halves upwards and is cast to int; ^[8] a guard raises $k$ to at least $1$, and the total is a long. Halves never occur here, as the next section shows, and Python's integers have no fixed size. Rounding is the more robust choice for large $N$: in double precision it agrees with the exact rounding of $N/e$, and so by Section 4 with the best $k$, for every $N$ from $5$ to $2.7$ million, and it gives the right $113307$ for $N=307999$ and $1310720$ for $N=3562905$.

Complexity and Verification

For each $N$ the programs do a fixed amount of floating-point work, one greatest common divisor and $O(\log N)$ divisions to remove the factors $2$ and $5$. The greatest common divisor costs $O(\log N)$ steps as well: the Euclidean algorithm, which the Java program uses, needs at most five times as many steps as the smaller number has decimal digits, ^[9] here at most $20$. For the upper limit $U=10000$ this is $O(U\log U)$ arithmetic operations on machine words and a fixed number of variables; in a test run each program, including its start-up, finished within a few hundredths of a second.

Floating point is used only to choose $k$, and with a wide margin. The C++ test decides the sign of $\ln N-\ln t_k$; over the range its absolute value is at least $3.1\cdot10^{-8}$, reached at $N=7531$, which exceeds $t_{2770}$ by only $0.0002$, while a double-precision recomputation of the difference of the two scores never deviates from the exact value by more than $6.4\cdot10^{-12}$. For the rounding in Python and Java, $N/e$ stays at least $7.1\cdot10^{-5}$ away from every half-integer, again at $N=7531$, where $N/e\approx2770.50007$, while the computed quotient is off by less than $5\cdot10^{-13}$.

The C++ program checks the value $2438$ before its main run. All three programs print the same value, equal to the sum of the exact values $D(N)$, and the following checks, not part of the published solutions, agree with them. A brute force with exact fractions tries every $k$ from $1$ to $N$ for every $N\le500$, which suffices because for $k\gt N$ the parts are smaller than $1$ and $P_k\lt1\le P_1$: the best $k$ is unique for $N\ge5$, equals the nearest integer to $N/e$, and the test of Section 6 gives the same verdict as the denominator of the fraction $M(N)$ itself. Exact integer comparisons of $N\,k^k$ with $(k+1)^{k+1}$ confirm for every $N$ from $5$ to $10000$ that the best $k$ is $\lfloor N/e\rfloor$ or $\lfloor N/e\rfloor+1$ and that the choices of all three programs, recomputed in double precision, are the best $k$; the C++ program run on each single $N$ returns the exact $D(N)$. Long division of $M(N)$ for $N\le100$ stops within $160$ digits exactly for the $31$ terminating values and runs on for $200$ digits for the others. The windows of Section 4 were checked in interval arithmetic for every $j\le10^6$. The C++ choice was recomputed in double precision for every $N\le2\cdot10^7$ and compared with $40$-digit values near ties; its failures at $307999$ and $3562905$ were confirmed with exact integer comparisons and a compiled copy of best_k.

Footnotes and References

The references below supply the background facts used above. The thresholds $t_k$ and their bounds, the windows in which rounding would fail and the denominator test are derived explicitly in this article.

Project Euler 183 — Maximum Product of Parts. The official statement splits N into k equal parts of size r = N/k, defines M(N) as the largest product rᵏ, sets D(N) = N if M(N) is a non-terminating decimal and D(N) = −N if it is a terminating one, shows M(11) = 14641/256 and M(8) = 512/27, gives the sum of D(N) for 5 ≤ N ≤ 100 as 2438 and asks for the sum for 5 ≤ N ≤ 10000.
Wikipedia — Steiner's calculus problem. The function x^(1/x) has its unique maximum at x = e. Jakob Steiner posed and solved the problem in 1850, in a paper in the Journal für die reine und angewandte Mathematik whose title, Über das größte Product der Theile oder Summanden jeder Zahl, speaks of the greatest product of the parts of a number.
Wikipedia — Hermite–Hadamard inequality. For a convex function on [a, b], the value at the midpoint is at most the mean value of the function over the interval, which in turn is at most the mean of the two values at the endpoints. Section 4 applies it to −ln x on [k, k + 1].
Wikipedia — Coprime integers. If a and b are coprime, then so are any of their powers; and if a and b are coprime and a divides a product bc, then a divides c, a generalisation of Euclid's lemma.
Wikipedia — Repeating decimal. In base 10 a fraction has a repeating, non-terminating decimal if and only if, in lowest terms, its denominator has a prime factor different from 2 and 5, that is, cannot be written as 2ᵐ5ⁿ; every terminating decimal can be written as a fraction whose denominator is a power of 10.
OEIS A003417 — Continued fraction for e, with the terms 2, 1, 2, 1, 1, 4, 1, 1, 6, …, and the numerators A007676 (2, 3, 8, 11, 19, 87, 106, 193, 1264, …) and denominators A007677 (1, 1, 3, 4, 7, 32, 39, 71, 465, …) of the convergents to e, which contain 8/3, 106/39 and 1264/465.
C++ — Euler183.cpp. The linked immutable C++ revision contains parse_arguments, best_k, D, solve and run_checkpoints. It is the implementation record for this article.
Python — round: without a number of digits it returns the nearest integer, and of two equally close multiples it chooses the even one. Java — Math.round(double): it returns the closest long, with ties rounding to positive infinity, and Math.E is the double closest to e.
Wikipedia — Euclidean algorithm. By Lamé's theorem of 1844, the algorithm never requires more steps than five times the number of decimal digits of the smaller integer.

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);
    }
}