# E004: Computing $\sigma(n)$ at Scale — Sieve vs. Factorization

```{figure} ../_static/experiments/e004_hero.png
:width: 80%
:alt: Preview figure for E004
```

```{figure} ../_static/experiments/e004_hero_2.png
:width: 80%
:alt: Preview figure for E004
```

**Tags:** `number-theory`, `quantitative-exploration`, `numerics`, `optimization`
See: {doc}`../tags`.

## Highlights

- Benchmark bulk sieve vs. per-number factorization.
- Find runtime crossover points as $N$ grows.
- Validate correctness on sampled inputs.


## Goal

Benchmark two practical ways to compute the sum-of-divisors function:

1. **Sieve method:** compute all $\sigma(1..N)$ in one pass.
2. **Factorization method:** compute $\sigma(n)$ per-number from the prime factorization.

## Research question

For a range of bounds $N$:

- which approach is faster?
- where is the crossover point?
- what are the memory tradeoffs?

## Why this qualifies as a mathematical experiment

Both methods are mathematically equivalent, but performance depends on constants, caching, and implementation details.
This is a quantitative exploration of algorithmic behavior grounded in number-theory structure.

## Experiment design

### Method A: divisor-sum sieve (bulk computation)

Compute `sigma[1..N]` by adding each divisor to its multiples (as in E003).

### Method B: per-number factorization

Factor each $n$ (e.g. using a precomputed prime list up to $\sqrt{N}$) and compute:

If
$$
n = \prod_{i=1}^k p_i^{a_i},
$$
then
$$
\sigma(n) = \prod_{i=1}^k \frac{p_i^{a_i+1}-1}{p_i-1}.
$$

### Measurements

- wall-clock runtime vs. $N$ (multiple trials, median)
- peak memory (rough estimate acceptable for v1)
- correctness cross-check: random sample where both methods agree

### Outputs

- plot: runtime vs. $N$ for both methods
- short table: $N$, runtime(A), runtime(B), speedup

## How to run

```bash
make run EXP=e004
```

or:

```bash
uv run python -m mathxlab.experiments.e004
```

## Notes / pitfalls

- Factorization becomes expensive quickly; keep the factorization method limited to moderate $N$.
- Use integer arithmetic for correctness checks (`sigma[n] == 2*n` etc.).
- Report both runtime and *effective throughput* (numbers processed per second).

## Extensions

- Add a third method using smallest-prime-factor (SPF) sieve for fast factorization.
- Compare pure Python vs. `numpy` arrays for Method A.
- Turn the benchmark into a reusable utility for later experiments.

## Published run snapshot

If this experiment is included in the docs gallery, include the published snapshot (report + params).

```{include} ../reports/e004.md
:start-after: "<!-- REPORT:BEGIN -->"
:end-before: "<!-- REPORT:END -->"
```

::: {dropdown} params.json (snapshot)
:open:

```{literalinclude} ../params/e004.json
:language: json
```

:::

## References

See {doc}`../references`.

{cite:p}`Voight1998PerfectNumbersElementaryIntroduction,Weisstein2003PerfectNumberMathWorld`

## Related experiments

- {doc}`e098` (E098: Maximizers of σ(n)/n^α across α)
- {doc}`e017` (Sieve memory blow-up vs. segmented sieve)
- {doc}`e051` (Semiprimes: balanced vs. unbalanced factorization timing)
- {doc}`e002` (Even Perfect Numbers — Generator and Growth)
- {doc}`e003` (Abundancy Index Landscape)