Problem 1000

Let $A=\{n_1<n_2<\cdots\}$ be an infinite sequence of integers, and let $\phi_A(k)$ count the number of $1\leq m\leq n_k$ such that the fraction $\frac{m}{n_k}$ does not have denominator $n_j$ for $j<k$ when written in lowest form; equivalently,

\frac{n_k}{(m,n_k)}\neq n_j

for all $1\leq j<k$ .

Is there a sequence $A$ such that

\lim_{N\to \infty}\frac{1}{N}\sum_{k\leq N}\frac{\phi_A(k)}{n_k}=0?

Source: erdosproblems.com/1000

Number theory
Diophantine approximation

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The site, accessed 2026-09-04 (page last edited 2025-12-05), labels the problem PROVED (LEAN) and credits Haight's thesis [Ha]; the Lean qualifier refers to a third-party formalization linked on the Haight claim page (1971) and not built or audited here.

Ca50b: Cassels, J. W. S., Some metrical theorems in Diophantine approximation. I. Proc. Cambridge Philos. Soc. (1950), 209-218.
Er64b: Erdős, P., Problems and results on diophantine approximations. Compositio Math. (1964), 52-65.
Ha: Haight, John Andrew, Metric Diophantine Approximation and Related Topics. PhD thesis, University of London, Westfield College, February 1971 (the title page's date; the catalog's entry [Ha] gives no year). ProQuest record.

Problem 1000

Status

Proof claims

Discussion