Detailed mathematical approach

Problem Summary

For each integer \(m\) from 2 through 15, define

$P_m=\max \left\{x_1^1x_2^2\cdots x_m^m : x_1+x_2+\cdots+x_m=m,\ x_i \gt 0\right\}.$

The exponents \(1,2,\dots,m\) make the variables asymmetric: increasing a large-index variable matters much more than increasing a small-index one. The task is to determine the maximizing configuration for every \(m\), take \(\lfloor P_m\rfloor\), and add those integer parts.

Mathematical Approach

This problem looks like a many-variable nonlinear search, but the structure is very rigid. The maximizing point is forced to be proportional to the weight vector \((1,2,\dots,m)\), so the entire problem collapses to a closed formula.

Take logarithms and move to a concave objective

Because the logarithm is strictly increasing, maximizing \(P_m\) is equivalent to maximizing

$F(x_1,\dots,x_m)=\log P_m=\sum_{i=1}^{m} i\log x_i$

under the same linear constraint \(x_1+\cdots+x_m=m\).

This reformulation is useful for two reasons. First, it turns a product into a sum, so differentiation becomes straightforward. Second, the Hessian is diagonal:

$\frac{\partial^2 F}{\partial x_i^2}=-\frac{i}{x_i^2},\qquad \frac{\partial^2 F}{\partial x_i\partial x_j}=0 \quad (i\ne j).$

Every diagonal entry is negative on the feasible region \(x_i \gt 0\), so \(F\) is strictly concave. That means any interior critical point is automatically the unique global maximum. The boundary cannot maximize the product either, because if some \(x_i\to 0^+\), then \(i\log x_i\to -\infty\).

The maximizing point is proportional to \(1,2,\dots,m\)

Introduce a Lagrange multiplier \(\lambda\) for the constraint and consider

$\mathcal{L}(x_1,\dots,x_m,\lambda)=\sum_{i=1}^{m} i\log x_i-\lambda\left(\sum_{i=1}^{m}x_i-m\right).$

Differentiating with respect to each \(x_i\) gives

$\frac{\partial \mathcal{L}}{\partial x_i}=\frac{i}{x_i}-\lambda=0,$

so every optimal coordinate must satisfy

$x_i=\frac{i}{\lambda}.$

This is the decisive structural fact: the maximizing coordinates are not arbitrary; they must scale linearly with the exponents. A variable with weight \(i\) receives \(i\) times as much mass as the variable with weight 1.

Now impose the constraint:

$\sum_{i=1}^{m}x_i=\frac{1}{\lambda}\sum_{i=1}^{m}i=\frac{1}{\lambda}\cdot\frac{m(m+1)}{2}=m.$

Hence

$\lambda=\frac{m+1}{2},\qquad x_i^*=\frac{2i}{m+1}\quad (1\le i\le m).$

Closed form of the maximal product

Substituting the maximizing coordinates back into the product gives

$P_m=\prod_{i=1}^{m}\left(\frac{2i}{m+1}\right)^i.$

It is often convenient to separate the common denominator:

$P_m=\frac{2^{1+2+\cdots+m}\prod_{i=1}^{m} i^i}{(m+1)^{1+2+\cdots+m}}=\frac{2^{m(m+1)/2}\prod_{i=1}^{m} i^i}{(m+1)^{m(m+1)/2}}.$

The implementations do not multiply this expression directly. Instead they use the numerically safer identity

$\log P_m=\sum_{i=1}^{m} i\log\left(\frac{2i}{m+1}\right),$

and apply the exponential only once at the end.

Worked example: \(m=10\)

For \(m=10\), the maximizing point is

$\left(\frac{2}{11},\frac{4}{11},\frac{6}{11},\dots,\frac{20}{11}\right).$

The maximal product is therefore

$P_{10}=\prod_{i=1}^{10}\left(\frac{2i}{11}\right)^i.$

Evaluating the logarithmic form gives a value whose integer part is

$\lfloor P_{10}\rfloor=4112.$

This is a useful checkpoint because it validates both the derivation and the floating-point rounding behavior used by the implementation.

How the Code Works

The C++, Python, and Java implementations all use the closed-form optimizer above rather than performing any search. For each \(m\), they loop through \(i=1,2,\dots,m\), compute the optimal coordinate \(x_i=\frac{2i}{m+1}\), and accumulate the logarithmic contribution \(i\log x_i\). After the loop, one exponential reconstructs \(P_m\).

That log-domain evaluation is the central numerical idea. The direct product contains many powers and can lose accuracy if multiplied naively, while the sum of logarithms stays in a moderate range and preserves the exact maximizing formula derived from the mathematics.

Once the numerical value of \(P_m\) has been reconstructed, the implementation takes its floor. A tiny positive guard such as \(10^{-12}\) is added before converting to an integer so that a value that should be an integer, but is stored as something like \(4111.999999999999\), is not rounded down incorrectly.

The final answer is obtained by repeating this process for \(m=2,3,\dots,15\) and summing the floors. One implementation also checks the known intermediate value \(\lfloor P_{10}\rfloor=4112\) before performing the full accumulation.

Complexity Analysis

For a single value of \(m\), the computation uses one loop of length \(m\), so the running time is \(O(m)\) and the extra space usage is \(O(1)\).

For the actual Project Euler range \(m=2\) to \(15\), the total work is

$O\left(\sum_{m=2}^{15} m\right),$

which is effectively constant in practice. If the same method were generalized to all \(m\) from 2 through \(N\), the total time would be \(O(N^2)\) with the same \(O(1)\) extra space.

Footnotes and References

1. Project Euler problem page: Problem 190 - Maximising a weighted product
2. Lagrange multiplier: Wikipedia - Lagrange multiplier
3. Concave function: Wikipedia - Concave function
4. AM-GM inequality: Wikipedia - AM-GM inequality