Problem 697: Randomly Decaying Sequence

Mathematical Analysis

Product of Uniform Random Variables

We have $X_n = c \cdot \prod_{i=1}^{n} U_i$ where $U_i \sim \text{Uniform}(0,1)$.

Taking logarithms: $\ln X_n = \ln c + \sum_{i=1}^{n} \ln U_i$.

Since $U_i \sim \text{Uniform}(0,1)$, we have $-\ln U_i \sim \text{Exponential}(1)$.

Therefore $-\sum_{i=1}^{n} \ln U_i \sim \text{Gamma}(n, 1)$.

Connection to Chi-Squared Distribution

The sum $S_n = -2\sum_{i=1}^{n} \ln U_i \sim \chi^2(2n)$ (chi-squared with $2n$ degrees of freedom).

Condition for $P(X_n < 1) = 0.25$

$P(X_n < 1) = P(\ln X_n < 0) = P\left(\sum_{i=1}^{n} \ln U_i < -\ln c\right) = P\left(S_n > 2\ln c\right) = 0.25$

So $2\ln c = \chi^2_{2n, 0.75}$ (the 75th percentile of $\chi^2(2n)$).

Normal Approximation

For large degrees of freedom $\nu = 2n$, the Wilson-Hilferty approximation gives:

where $z_p$ is the $p$-th quantile of the standard normal distribution.

For $p = 0.75$: $z_{0.75} = \Phi^{-1}(0.75) \approx 0.6744897501960817$.

With $n = 10^7$ and $\nu = 2 \times 10^7$:

Then $\log_{10} c = \frac{\ln c}{\ln 10}$.

Editorial

We round to 2 decimal places. We enumerate the admissible parameter range, discard candidates that violate the derived bounds or arithmetic constraints, and update the final set or total whenever a candidate passes the acceptance test.

Pseudocode

Set $\nu = 2 \times 10^7$
Compute $z_{0.75} = \Phi^{-1}(0.75)$
Apply Wilson-Hilferty: $\chi^2 = \nu(1 - 2/(9\nu) + z_{0.75}\sqrt{2/(9\nu)})^3$
Compute $\log_{10} c = \chi^2 / (2 \ln 10)$
Round to 2 decimal places

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 Analysis

$O(1)$ - direct formula evaluation.

Answer

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

int main() {
    // We need P(X_n < 1) = 0.25 where X_n = c * prod(U_i)
    // This gives 2*ln(c) = chi^2_{2n, 0.75}
    // Using Wilson-Hilferty approximation for chi-squared quantile

    long long n = 10000000LL;
    double nu = 2.0 * n;

    // z_{0.75} = inverse normal CDF at 0.75
    // Using the known value
    double z = 0.6744897501960817;

    // Wilson-Hilferty approximation
    double term = 1.0 - 2.0 / (9.0 * nu) + z * sqrt(2.0 / (9.0 * nu));
    double chi2 = nu * term * term * term;

    // 2*ln(c) = chi2, so ln(c) = chi2/2
    // log10(c) = ln(c) / ln(10) = chi2 / (2 * ln(10))
    double log10c = chi2 / (2.0 * log(10.0));

    // Round to 2 decimal places
    cout << fixed << setprecision(2) << log10c << endl;

    return 0;
}

#!/usr/bin/env python3
"""Project Euler Problem 697: Randomly Decaying Sequence"""

from scipy.stats import norm, chi2
import math

def solve():
    n = 10_000_000
    nu = 2 * n  # degrees of freedom for chi-squared

    # We need P(X_n < 1) = 0.25
    # X_n = c * prod(U_i), -ln(U_i) ~ Exp(1)
    # -2*sum(ln(U_i)) ~ chi^2(2n)
    # P(X_n < 1) = P(sum(-ln(U_i)) > ln(c)) = P(chi^2(2n) > 2*ln(c)) = 0.25
    # So 2*ln(c) = chi^2 quantile at 0.75

    chi2_val = chi2.ppf(0.75, nu)
    log10_c = chi2_val / (2 * math.log(10))

    print(f"{log10_c:.2f}")

    z_075 = norm.ppf(0.75)  # ~0.6744897501960817
    term = 1 - 2/(9*nu) + z_075 * math.sqrt(2/(9*nu))
    chi2_approx = nu * term**3
    log10_c_approx = chi2_approx / (2 * math.log(10))
    print(f"Wilson-Hilferty: {log10_c_approx:.2f}")

solve()