Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 822

claims/: The 1 claim page of Problem 822, one per claimant's result; the problem's standing derives from them.

Statement. Does the set of integers of the form $n+\phi(n)$ have positive (lower) density?

Status. Proved. The site's label, for the refereed theorem of Gabdullin, Iudelevich and Luca: a positive proportion of the integers up to $x$ are of the form $n+\phi(n)$ , and at most $0.93x$ of them are; the site adopted it on 2025-10-14.

Source. erdosproblems.com/822, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #822, https://www.erdosproblems.com/822.

References.

[GIL24] Gabdullin, Mikhail R. and Iudelevich, Vitalii V. and Luca, Florian, Numbers of the form $k+f(k)$ . J. Number Theory 262 (2024), 58-85; arXiv:2306.16035 (2023).

Formalization. Statement in formal-conjectures: erdos_822 answers True with a sorry body and no formal_proof attribute at the pinned commit; the statement file is not a formalization. A Lean development in Boris Alexeev's lean-proofs repository presents itself as a formalization of the authors' Theorem 1.4 and is linked, not built in this repository, on the claim page.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (6)

Positive density of the values n plus phi(n)problems/arithmetic_functions/E0822/claims Arithmetic Functions arithmetic_functions/gabdullin_2024_numbers_form Theorem 1.3 (p. 2): if 0 <= f(k) <= ck, at least (2c+2)^{-1} x^{-1} sum f(k) integers up to x are not of the form k + f(k)Theorem 1.4 (p. 2): x << N_phi^+(x) <= (1/2 + int_0^1 Phi(t) dt/(1+t)^2 + o(1)) x

Graph