Skip to content

Erdős problem 1000

Let A={n1<n2<}A=\{n_1<n_2<\cdots\} be an infinite sequence of integers, and let ϕA(k)\phi_A(k) count the number of 1mnk1\leq m\leq n_k such that the fraction mnk\frac{m}{n_k} does not have denominator njn_j for j<kj<k when written in lowest form; equivalently, nk(m,nk)nj \frac{n_k}{(m,n_k)}\neq n_j for all 1j<k1\leq j<k.

Sources

Browse retained paths and inspect the exact material available for this Problem.

5 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

1000.lean

Retained formal statement1 of 5

Let A={n1<n2<}A=\{n_1<n_2<\cdots\} be an infinite sequence of integers, and let ϕA(k)\phi_A(k) count the number of 1mnk1\leq m\leq n_k such that the fraction mnk\frac{m}{n_k} does not have denominator njn_j for j<kj<k when written in lowest form; equivalently, nk(m,nk)nj \frac{n_k}{(m,n_k)}\neq n_j for all 1j<k1\leq j<k.

Is there a sequence AA such that limN1NkNϕA(k)nk=0? \lim_{N\to \infty}\frac{1}{N}\sum_{k\leq N}\frac{\phi_A(k)}{n_k}=0?

This was solved by Haight [Ha] who proved that such a sequence does exist (contrary to Erdős' expectations).

FormalConjectures/ErdosProblems/1000.leanErdos1000.erdos_10001 lineExact file
True ↔ ∃ n, StrictMono n ∧ 0 < n 0 ∧ Filter.Tendsto (Erdos1000.phiAvg n) Filter.atTop (nhds 0)
SolvedProof has a holelean4external proof

The proof uses `sorry`: part of the argument is written but not proved. Lean accepts the file; it does not accept the theorem.

Search problems.science

Find a Problem, Result, source, or page