 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/iii/paper-150/1/b/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

Apply part a to

A = {1, \dots, ⌊ x ⌋}

and all primes. Since

∣ {n \leq x : d ∣ n} ∣ = ⌊ \frac{x}{d} ⌋,

we obtain

S (A, P, z) = x \sum_{d ∣ P (z)} \frac{μ ( d )}{d} + O (\sum_{d ∣ P (z)} 1) = x \prod_{p \leq z} (1 - \frac{1}{p}) + O (2^{π (z)}) .

For

z \leq lo g x

, the error is at most

2^{z} \leq x^{l o g 2} = o (x / lo g z)

z \to \infty

\prod_{p \leq z} (1 - \frac{1}{p}) = \frac{e ^{- γ} + o ( 1 )}{l o g z} .

Thus

∣ {n \in [1, x] : n has no prime factor at most z} ∣ = (e^{- γ} + o (1)) \frac{x}{l o g z},

so one may take

C = e^{- γ} > 0

. For bounded

z

, the preceding exact product formula gives the corresponding fixed density.

 New to topics? Read the docs here!