Project Euler

Largest Product in a Series

Given a 1000-digit number D = d_0 d_1... d_999 (where each d_i in {0, 1,..., 9}), find the maximum product of 13 consecutive digits: M = max_(0 <= i <= 987) prod_(j=0)^12 d_(i+j).

Source sync Apr 19, 2026

Problem #0008

Level Level 00

Solved By 379,224

Languages C++, Python

Answer 23514624000

Length 390 words

searchbrute_forceoptimization

The four adjacent digits in the $1000$-digit number that have the greatest product are $9 \times 9 \times 8 \times 9 = 5832$. \begin {align*} 73167176531330624919225119674426574742355349194934 \\ 96983520312774506326239578318016984801869478851843 \\ 85861560789112949495459501737958331952853208805511 \\ 12540698747158523863050715693290963295227443043557 \\ 66896648950445244523161731856403098711121722383113 \\ 62229893423380308135336276614282806444486645238749 \\ 30358907296290491560440772390713810515859307960866 \\ 70172427121883998797908792274921901699720888093776 \\ 65727333001053367881220235421809751254540594752243 \\ 52584907711670556013604839586446706324415722155397 \\ 53697817977846174064955149290862569321978468622482 \\ 83972241375657056057490261407972968652414535100474 \\ 82166370484403199890008895243450658541227588666881 \\ 16427171479924442928230863465674813919123162824586 \\ 17866458359124566529476545682848912883142607690042 \\ 24219022671055626321111109370544217506941658960408 \\ 07198403850962455444362981230987879927244284909188 \\ 84580156166097919133875499200524063689912560717606 \\ 05886116467109405077541002256983155200055935729725 \\ 71636269561882670428252483600823257530420752963450 \end {align*}

Find the thirteen adjacent digits in the $1000$-digit number that have the greatest product. What is the value of this product?

Problem 8: Largest Product in a Series

Mathematical Development

Window Products

Definition 1. For integers $i$ and $k$ with $0 \le i \le N-k$ , define the window product

P_i = \prod_{j=0}^{k-1} d_{i+j}.

For this problem, $N = 1000$ and $k = 13$ , so there are

N-k+1 = 1000-13+1 = 988

candidate windows.

Theorem 1 (Exhaustive search is sufficient). The desired quantity is

M = \max_{0 \le i \le N-k} P_i,

so evaluating all $988$ window products and retaining the largest one yields the correct answer.

Proof. The set

\mathcal{W} = \{P_i : 0 \le i \le N-k\}

is finite. Therefore it has a maximum element. An exhaustive search computes every element of $\mathcal{W}$ and returns the largest value encountered, which is exactly $\max \mathcal{W} = M$ . $\square$

Lemma 1 (Zero windows). If one of the digits in a length-13 window is zero, then the product of that window is zero.

Proof. A product containing a factor equal to zero is zero. $\square$

Remark. Lemma 1 explains why many windows are automatically non-optimal, but the reference implementation does not need any special-case optimization: it simply computes all $988$ products directly.

Numerical Evaluation

Proposition 1. The maximum product is attained by the 13-digit block

5576689664895,

which begins at index $197$ (using zero-based indexing), and its product is

23{,}514{,}624{,}000.

Proof. Exhaustive evaluation of the $988$ window products shows that the largest one occurs for the block

d_{197} d_{198} \cdots d_{209} = 5576689664895.

Its product is computed directly as

\begin{aligned} 5 \cdot 5 &= 25,\\ 25 \cdot 7 &= 175,\\ 175 \cdot 6 &= 1050,\\ 1050 \cdot 6 &= 6300,\\ 6300 \cdot 8 &= 50400,\\ 50400 \cdot 9 &= 453600,\\ 453600 \cdot 6 &= 2721600,\\ 2721600 \cdot 6 &= 16329600,\\ 16329600 \cdot 4 &= 65318400,\\ 65318400 \cdot 8 &= 522547200,\\ 522547200 \cdot 9 &= 4702924800,\\ 4702924800 \cdot 5 &= 23514624000. \end{aligned}

Hence the maximal product is $23{,}514{,}624{,}000$ . $\square$

Editorial

We enumerate every block of $k$ consecutive digits in the 1000-digit string. For each starting position we multiply the $k$ digits in that window and compare the product against the current maximum. This exhaustive scan is sufficient because every admissible length- $k$ substring appears exactly once as some window.

Theorem 2 (Algorithm correctness). LargestProductInSeries(d, k) returns the largest product of $k$ consecutive digits.

Proof. For each index $i$ with $0 \le i \le N-k$ , the inner loop computes exactly

P_i = \prod_{j=0}^{k-1} d_{i+j}.

The outer loop visits every admissible starting position exactly once and keeps the maximum value seen so far in best. By Theorem 1, the maximum over these values is precisely the desired quantity. Therefore the returned value is correct. $\square$

Pseudocode

Algorithm: Maximum Product of Consecutive Digits
Require: A digit string d_1 d_2 ... d_m and a window length k.
Ensure: The maximum product of k consecutive digits in the string.
1: Interpret the input as a sequence of decimal digits and initialize best ← 0.
2: For each starting position i with i + k - 1 ≤ m do:
3:     Compute P ← product of the k digits beginning at position i.
4:     If P > best, set best ← P.
5: Return best.

Complexity Analysis

Theorem 3. The algorithm runs in $\Theta((N-k+1)k)$ time and uses $O(N)$ space in the given implementation.

Proof. There are exactly $N-k+1$ windows, and for each window the inner loop performs exactly $k$ multiplications. Hence the running time is

\Theta((N-k+1)k).

For this problem,

(N-k+1)k = 988 \cdot 13 = 12{,}844,

so the computation is tiny. The Python implementation first stores the 1000 digits in a list, which uses $O(N)$ space; aside from that list, only a constant number of scalar variables are maintained. $\square$

Answer

\boxed{23514624000}

C++ project_euler/problem_008/solution.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    string num =
        "73167176531330624919225119674426574742355349194934"
        "96983520312774506326239578318016984801869478851843"
        "85861560789112949495459501737958331952853208805511"
        "12540698747158523863050715693290963295227443043557"
        "66896648950445244523161731856403098711121722383113"
        "62229893423380308135336276614282806444486645238749"
        "30358907296290491560440772390713810515859307960866"
        "70172427121883998797908792274921901699720888093776"
        "65727333001053367881220235421809751254540594752243"
        "52584907711670556013604839586446706324415722155397"
        "53697817977846174064955149290862569321978468622482"
        "83972241375657056057490261407972968652414535100474"
        "82166370484403199890008895243450658541227588666881"
        "16427171479924442928230863465674813919123162824586"
        "17866458359124566529476545682848912883142607690042"
        "24219022671055626321111109370544217506941658960408"
        "07198403850962455444362981230987879927244284909188"
        "84580156166097919133875499200524063689912560717606"
        "05886116467109405077541002256983155200055935729725"
        "71636269561882670428252483600823257530420752963450";

    int k = 13, n = num.size();
    long long best = 0;
    for (int i = 0; i + k <= n; i++) {
        long long prod = 1;
        for (int j = 0; j < k; j++)
            prod *= (num[i + j] - '0');
        best = max(best, prod);
    }
    cout << best << endl;
    return 0;
}

Python project_euler/problem_008/solution.py

from math import prod



def solve():
    NUMBER = (
        "73167176531330624919225119674426574742355349194934"
        "96983520312774506326239578318016984801869478851843"
        "85861560789112949495459501737958331952853208805511"
        "12540698747158523863050715693290963295227443043557"
        "66896648950445244523161731856403098711121722383113"
        "62229893423380308135336276614282806444486645238749"
        "30358907296290491560440772390713810515859307960866"
        "70172427121883998797908792274921901699720888093776"
        "65727333001053367881220235421809751254540594752243"
        "52584907711670556013604839586446706324415722155397"
        "53697817977846174064955149290862569321978468622482"
        "83972241375657056057490261407972968652414535100474"
        "82166370484403199890008895243450658541227588666881"
        "16427171479924442928230863465674813919123162824586"
        "17866458359124566529476545682848912883142607690042"
        "24219022671055626321111109370544217506941658960408"
        "07198403850962455444362981230987879927244284909188"
        "84580156166097919133875499200524063689912560717606"
        "05886116467109405077541002256983155200055935729725"
        "71636269561882670428252483600823257530420752963450"
    )

    K = 13
    digits = [int(c) for c in NUMBER]
    return max(prod(digits[i:i + K]) for i in range(len(digits) - K + 1))


answer = solve()
assert answer == 23514624000
print(answer)