Erdős Problem 418

Reference: erdosproblems.com/418

Reviewed by @b-mehta on 2025-05-27

theorem erdos_418 : {x : ℕ | ∃ (n : ℕ), n - n.totient = x}ᶜ.Infinite ↔ True

Are there infinitely many integers not of the form $n - \phi(n)$?

This is true, as shown by Browkin and Schinzel [BrSc95].

[BrSc95] Browkin, J. and Schinzel, A., On integers not of the form {$n-\phi(n)$}. Colloq. Math. (1995), 55-58.

theorem erdos_418.variants.conditional (goldbach : ∀ (n : ℕ), 6 < n → Even n → ∃ (p : ℕ) (q : ℕ), p ≠ q ∧ Nat.Prime p ∧ Nat.Prime q ∧ n = p + q) (m : ℕ) (h : Odd m) : ∃ (n : ℕ), m + n.totient = n

It follows from a slight strengthening of the Goldbach conjecture that every odd number can be written as $n - \phi(n)$. In particular, we assume that every even number greater than 6 can be written as the sum of two distinct primes, in contrast to the usual Goldbach conjecture that every even number greater than 2 can be written as the sum of two primes.

theorem erdos_418.variants.sigma : ∃ (S : Set ℕ) (_ : S.HasPosDensity), S ⊆ {x : ℕ | ∃ (n : ℕ), (ArithmeticFunction.sigma 1) n - n = x}ᶜ

Erdős has shown that a positive density set of integers cannot be written as $\sigma(n) - n$.

[Er73b] Erdős, P., Über die Zahlen der Form $\sigma (n)-n$ und $n-\phi(n)$. Elem. Math. (1973), 83-86.

theorem erdos_418.variants.soln : {x : ℕ | ∃ (k : ℕ), 2 ^ (k + 1) * 509203 = x} ⊆ {x : ℕ | ∃ (n : ℕ), n - n.totient = x}ᶜ

A solution to erdos_418 was shown by Browkin and Schinzel [BrSc95] by showing that any integer of the form $2^(k + 1)\cdot 509203$ is not of the form $n - \phi(n)$.

[BrSc95] Browkin, J. and Schinzel, A., On integers not of the form {$n-\phi(n)$}. Colloq. Math. (1995), 55-58.

theorem erdos_418.variants.density : (∃ (S : Set ℕ) (_ : S.HasPosDensity), S ⊆ {x : ℕ | ∃ (n : ℕ), n - n.totient = x}ᶜ) ↔ sorry

It seems to be open whether there is a positive density set of integers not of the form $n - \phi(n)$.