EP Ethan Pham AI/ML engineer publishing Project Euler proofs, ICPC and IOI archives, and theory-heavy engineering notes.
All Euler problems
Project Euler

Maximising a Weighted Product

Let S_m = {(x_1, x_2,..., x_m): x_i > 0, sum_(i=1)^m x_i = m}. Let P_m = max_(S_m) prod_(i=1)^m x_i^i. Find sum_(m=2)^15 floor(P_m).

Source sync Apr 19, 2026
Problem #0190
Level Level 07
Solved By 4,750
Languages C++, Python
Answer 371048281
Length 176 words
optimizationgeometrybrute_force
Problem statement

Problem Statement

This archive keeps the full statement, math, and original media on the page.

Let \(S_m = (x_1, x_2, \dots , x_m)\) be the \(m\)-tuple of positive real numbers with \(x_1 + x_2 + \cdots + x_m = m\) for which \(P_m = x_1 \cdot x_2^2 \cdot \cdots \cdot x_m^m\) is maximised.

For example, it can be verified that \(\lfloor P_{10}\rfloor = 4112\) (\(\lfloor \, \rfloor \) is the integer part function).

Find \(\sum \limits _{m = 2}^{15} \lfloor P_m \rfloor \).

Problem 190 content is attributed to Project Euler and included here under the CC BY-NC-SA 4.0 license.

Open official problem License details

Problem 190: Maximising a Weighted Product

Mathematical Analysis

Optimization via Lagrange Multipliers

We want to maximize f(x1,…,xm)=∏i=1mxiif(x_1, \ldots, x_m) = \prod_{i=1}^m x_i^i subject to g(x1,…,xm)=∑i=1mxi−m=0g(x_1, \ldots, x_m) = \sum_{i=1}^m x_i - m = 0.

Taking logarithms, we equivalently maximize:

ln⁡f=∑i=1miln⁡xi\ln f = \sum_{i=1}^m i \ln x_i

Using Lagrange multipliers: ∇ln⁡f=λ∇g\nabla \ln f = \lambda \nabla g, which gives:

ixi=λfor all i\frac{i}{x_i} = \lambda \quad \text{for all } i

Therefore: xi=iλx_i = \frac{i}{\lambda}.

Solving for λ\lambda

From the constraint ∑i=1mxi=m\sum_{i=1}^m x_i = m:

∑i=1miλ=m  ⟹  1λ∑i=1mi=m  ⟹  1λ⋅m(m+1)2=m\sum_{i=1}^m \frac{i}{\lambda} = m \implies \frac{1}{\lambda} \sum_{i=1}^m i = m \implies \frac{1}{\lambda} \cdot \frac{m(m+1)}{2} = m λ=m+12\lambda = \frac{m+1}{2}

Optimal Values

xi=iλ=2im+1x_i = \frac{i}{\lambda} = \frac{2i}{m+1}

Maximum Value

Pm=∏i=1m(2im+1)i=∏i=1m(2i)i(m+1)i=∏i=1m(2i)i(m+1)m(m+1)/2P_m = \prod_{i=1}^m \left(\frac{2i}{m+1}\right)^i = \prod_{i=1}^m \frac{(2i)^i}{(m+1)^i} = \frac{\prod_{i=1}^m (2i)^i}{(m+1)^{m(m+1)/2}}

Proof of Maximum

The log of the objective, ∑iln⁡xi\sum i \ln x_i, is a concave function on the positive orthant (since each iln⁡xii \ln x_i is concave). The constraint is linear. Therefore, any critical point of the Lagrangian is a global maximum. Since we found a unique critical point, it must be the global maximum.

Computation

For each mm from 2 to 15:

  1. Compute xi=2i/(m+1)x_i = 2i/(m+1).
  2. Compute Pm=∏xiiP_m = \prod x_i^i.
  3. Take ⌊Pm⌋\lfloor P_m \rfloor.
  4. Sum all values.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. □\square

Complexity

  • Time: O(∑m=215m)=O(m2)O(\sum_{m=2}^{15} m) = O(m^2), negligible.
  • Space: O(1)O(1).

Answer

371048281\boxed{371048281}
Source code

Code

Each problem page includes the exact C++ and Python source files from the local archive.

C++ project_euler/problem_190/solution.cpp 
#include <bits/stdc++.h>
using namespace std;

int main() {
    long long total = 0;

    for (int m = 2; m <= 15; m++) {
        // x_i = 2i / (m+1)
        // P_m = product of (2i/(m+1))^i for i=1..m
        double log_pm = 0.0;
        for (int i = 1; i <= m; i++) {
            log_pm += i * log(2.0 * i / (m + 1));
        }
        long long pm = (long long)floor(exp(log_pm));
        total += pm;
    }

    cout << total << endl;
    return 0;
}