Skip to content

Erdős problem 694

Let Unparsed notation: f_\max(n) be the largest mm such that ϕ(m)=n\phi(m) = n, and Unparsed notation: f_\min(n) be the smallest such mm, where ϕ\phi is Euler's totient function. Investigate Unparsed notation: \max_{n\leq x}\frac{f_\max(n)}{f_\min(n)}.

Sources

The source's own material, retained exactly.

3 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

694.lean

Retained formal statement1 of 3

Let Unparsed notation: f_\max(n) be the largest mm such that ϕ(m)=n\phi(m) = n, and Unparsed notation: f_\min(n) be the smallest such mm, where ϕ\phi is Euler's totient function. Investigate Unparsed notation: \max_{n\leq x}\frac{f_\max(n)}{f_\min(n)}.

GPT-5.5 Pro (prompted by Price) has proved (see also the comments for a summary) that max⁡n≤xfmax⁡(n)fmin⁡(n)=(eγ+o(1))log⁡log⁡x. \max_{n\leq x}\frac{f_{\max}(n)}{f_{\min}(n)}=(e^\gamma+o(1))\log\log x.

A Lean formalisation of the reduction exists, conditional on Mertens' product theorem and Linnik's theorem; see the formal proof.

FormalConjectures/ErdosProblems/694.leanErdos694.erdos_6948 linesExact file
∀ (fmax fmin : ℕ → ℕ),  (∀ (n : ℕ), IsGreatest (Nat.totient ⁻¹' {n}) (fmax n)) →    (∀ (n : ℕ), IsLeast (Nat.totient ⁻¹' {n}) (fmin n)) →      ∃ o,        Filter.Tendsto o Filter.atTop (nhds 0) ∧          ∀ (x : ℕ),            sSup {x_1 | ∃ n, ∃ (_ : n ≤ x) (_ : ∃ m, m.totient = n), ↑(fmax n) / ↑(fmin n) = x_1} =              (Real.exp Real.eulerMascheroniConstant + o x) * Real.log (Real.log ↑x)
SolvedStatement only, no proof