# Proof: Fewer than 20 percent of the positive integers from 1 to 1000 are prime

- **Generated:** 2026-03-28
- **Verdict:** PROVED
- **Audit trail:** [proof_audit.md](proof_audit.md) | [proof.py](proof.py)

## Key Findings

- There are exactly **168 prime numbers** in the range [1, 1000], computed by two independent algorithms that agree perfectly.
- 168 out of 1000 is **16.8%**, which is strictly less than 20%.
- The prime count of 168 matches the well-known number-theoretic value pi(1000) = 168.
- No adversarial interpretation of the claim changes the result.

## Claim Interpretation

**Natural language:** Fewer than 20 percent of the positive integers from 1 to 1000 are prime.

**Formal interpretation:** The count of primes in {1, 2, ..., 1000} divided by 1000, expressed as a percentage, is strictly less than 20. Equivalently, the prime count must be strictly less than 200. The phrase "fewer than" unambiguously implies strict inequality (<).

## Evidence Summary

| ID | Fact | Verified |
|----|------|----------|
| A1 | Prime count via Sieve of Eratosthenes | Computed: 168 primes |
| A2 | Prime count via trial division (independent cross-check) | Computed: 168 primes |
| A3 | Percentage of primes in [1, 1000] | Computed: 16.8% |

## Proof Logic

Two independent algorithms enumerate all primes in [1, 1000]:

1. **Sieve of Eratosthenes (A1):** Marks composites by iterating through multiples of each prime up to sqrt(1000). Produces a list of 168 primes, from 2 to 997.

2. **Trial division (A2):** Tests each integer in [1, 1000] individually for primality by checking divisibility up to its square root. Also produces exactly 168 primes.

Both methods yield identical prime lists (A1, A2 — independently computed). The percentage is then 168 / 1000 x 100 = 16.8% (A3), which satisfies 16.8 < 20.

## Counter-Evidence Search

- **Could the algorithms have bugs that undercount primes?** Two independent algorithms (sieve and trial division) produce identical results. The count of 168 matches the well-known value pi(1000) = 168 from number theory. No undercounting detected.

- **Could "20 percent" be interpreted differently?** "Fewer than" is unambiguously strict inequality. Even under a non-strict reading (<=), 168 <= 200 holds. No interpretation changes the result.

## Conclusion

**PROVED.** There are exactly 168 prime numbers among the positive integers from 1 to 1000, which is 16.8% — strictly fewer than 20%. This was established by two independent computational methods (Sieve of Eratosthenes and trial division) that produce identical results, consistent with the known value pi(1000) = 168.

---

Generated by [proof-engine](https://github.com/yaniv-golan/proof-engine) v0.10.0 on 2026-03-28.
