 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/ii/paper-4/1i/solution

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

v_{p} (n 2 n) = \sum_{j \geq 1} (⌊ 2 n / p^{j} ⌋ - 2 ⌊ n / p^{j} ⌋),

whose summands are zero or one. If the sum is at least

k

, some nonzero summand has index

j \geq k

, whence

p^{k} \leq p^{j} \leq 2 n

Grouping the von Mangoldt function by prime gives

ψ (x) = \sum_{p \leq x} ⌊ lo g x / lo g p ⌋ lo g p .

Every prime-power contribution to

lo g (n 2 n)

occurs in

ψ (2 n)

by the first part. Finally

(n 2 n) = \prod_{j = 1}^{n} (n + j) / j \geq 2^{n}

, so

ψ (2 n) \geq n lo g 2

 New to topics? Read the docs here!