Problem 973: Lucky Number Sieve

Mathematical Foundation

Definition 1. Let $L_0 = (1, 3, 5, 7, 9, 11, \ldots)$ be the sequence of positive odd integers. Define the sieve process inductively: at stage $j \ge 1$, let $d_j$ be the $(j+1)$-th element of $L_{j-1}$. Form $L_j$ by deleting every $d_j$-th element from $L_{j-1}$. The lucky numbers are $\mathcal{L} = \bigcap_{j \ge 0} L_j$, i.e., the elements that survive all stages.

Theorem 1 (Termination of the Sieve). For any bound $N$, the sieve terminates in finitely many stages. Specifically, if $|L_{j-1}| < d_j$ at some stage $j$, no further elements are removed.

Proof. At each stage, the sieve value $d_j$ is the $(j+1)$-th element of $L_{j-1}$. Since each stage removes at least one element, $|L_j| < |L_{j-1}|$ as long as $d_j \le |L_{j-1}|$. Eventually $d_j > |L_{j-1}|$, so no elements are removed and the sequence stabilizes. $\square$

Theorem 2 (Asymptotic Density). Let $\mathcal{L}(N)$ denote the number of lucky numbers up to $N$. Then

as $N \to \infty$, analogous to the Prime Number Theorem.

Proof. (Heuristic, due to Hawkins, 1958.) At each sieve stage with parameter $d$, the survival probability is $(d-1)/d$. The product $\prod (1 - 1/d)$ over sieve values up to $\sqrt{N}$ behaves like $\prod_{p \le \sqrt{N}} (1 - 1/p)$ for primes, yielding the same $1/\ln N$ density by Mertens’ theorem. A rigorous proof of the exact asymptotic remains open, but extensive numerical evidence strongly supports it. $\square$

Lemma 1 (First Lucky Numbers). The first 20 lucky numbers are:

Proof. Direct application of the sieve:

• $L_0$: all odd numbers $1, 3, 5, 7, 9, 11, 13, \ldots$
• Stage 1 ($d_1 = 3$): remove positions $3, 6, 9, \ldots$ from $L_0$, eliminating $5, 11, 17, 23, \ldots$
• Stage 2 ($d_2 = 7$): remove every 7th from remaining, eliminating $19, 39, \ldots$
• Continue until stabilization. $\square$

Editorial

Compute the sum of all lucky numbers below 10^5. Lucky numbers are generated by a sieve process: 1. Start with odd numbers: 1, 3, 5, 7, 9, 11, 13, … 2. The second number is 3, so remove every 3rd element. 3. The next surviving number is 7, so remove every 7th element. 4. Repeat with each subsequent surviving number. We initialize with odd numbers less than N. Finally, remove every d-th element (0-indexed: positions d-1, 2d-1, 3d-1, …).

Pseudocode

Initialize with odd numbers less than N
Remove every d-th element (0-indexed: positions d-1, 2d-1, 3d-1, ...)

Complexity Analysis

• Time: Each sieve stage removes a $1/d_j$ fraction of the list. The total work across all stages is $O\!\left(\sum_j |L_j|/d_j\right)$. Since $d_j$ grows roughly as $j \ln j$ and $|L_j| \approx N/(2\ln N)$, the total is approximately $O(N \log N / \log\log N)$. In practice with an array-based implementation using in-place removal, this is $O(N \sqrt{N})$ in the worst case due to shifting.
• Space: $O(N)$ for the list.

Answer

#include <bits/stdc++.h>
using namespace std;
int main() {
    const int N = 100000;
    vector<int> nums;
    for (int i = 1; i < N; i += 2) nums.push_back(i);
    int idx = 1;
    while (idx < (int)nums.size() && nums[idx] <= (int)nums.size()) {
        int step = nums[idx];
        vector<int> next;
        for (int i = 0; i < (int)nums.size(); i++)
            if ((i+1) % step != 0) next.push_back(nums[i]);
        nums = next;
        idx++;
    }
    long long ans = 0;
    for (int x : nums) ans += x;
    cout << ans << endl;
    return 0;
}

"""
Problem 973: Lucky Number Sieve

Compute the sum of all lucky numbers below 10^5.

Lucky numbers are generated by a sieve process:
    1. Start with odd numbers: 1, 3, 5, 7, 9, 11, 13, ...
    2. The second number is 3, so remove every 3rd element.
    3. The next surviving number is 7, so remove every 7th element.
    4. Repeat with each subsequent surviving number.

Key results:
    - Lucky numbers share many properties with primes (Goldbach-like conjectures)
    - Their density is asymptotically ~ n / ln(n), similar to primes
    - answer = sum of all lucky numbers < 10^5

Methods:
    1. lucky_sieve          — generate lucky numbers via iterative sieving
    2. lucky_counting_func  — count lucky numbers up to x (pi_L analog)
    3. gap_analysis         — compute gaps between consecutive lucky numbers
    4. lucky_vs_prime_density — compare lucky and prime counting functions
"""

from math import isqrt
from collections import Counter

def lucky_sieve(N):
    """Return list of all lucky numbers below N."""
    nums = list(range(1, N, 2))  # start with odd numbers
    idx = 1
    while idx < len(nums) and nums[idx] <= len(nums):
        step = nums[idx]
        nums = [nums[i] for i in range(len(nums)) if (i + 1) % step != 0]
        idx += 1
    return nums

def lucky_counting_func(luckys, checkpoints):
    """For each x in checkpoints, count lucky numbers <= x."""
    counts = []
    j = 0
    for x in sorted(checkpoints):
        while j < len(luckys) and luckys[j] <= x:
            j += 1
        counts.append(j)
    return counts

def gap_analysis(luckys):
    """Return list of gaps and a Counter of gap frequencies."""
    gaps = [luckys[i + 1] - luckys[i] for i in range(len(luckys) - 1)]
    return gaps, Counter(gaps)

def prime_sieve(n):
    """Return list of primes up to n."""
    s = bytearray(b'\x01') * (n + 1)
    s[0] = s[1] = 0
    for i in range(2, isqrt(n) + 1):
        if s[i]:
            s[i * i :: i] = bytearray(len(s[i * i :: i]))
    return [i for i in range(2, n + 1) if s[i]]

#  Verification
# Known first lucky numbers: 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 39, 43, 49
_luckys = lucky_sieve(50)
assert _luckys == [1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 39, 43, 49], \
    f"Lucky sieve mismatch: {_luckys}"

#  Main computation
N = 10 ** 5
luckys = lucky_sieve(N)
answer = sum(luckys)
print(answer)

#  Visualization — 4-panel figure