Problem 416

Let $V(x)$ count the number of $n\leq x$ such that $\phi(m)=n$ is solvable. Does $V(2x)/V(x)\to 2$ ? Is there an asymptotic formula for $V(x)$ ?

Source: erdosproblems.com/416

Number theory

Status

ClaimedProved

A full solution has been claimed but not yet accepted. The statement is true.

The site labels the problem OPEN (page last edited 30 September 2025, fetched 2026-09-27; marked as not decidable by a finite computation); its proof-claims thread lists two partial claims: the Conjectures.io Lean record, posted by the site's maintainer on 2026-09-27 with the note that he has not verified it, and Zeraoulia's fixed-scale limit points. The claims recorded are Kruer and Kohlmeyer on the first question, the OpenAI release's fixed-scale limit on the first question, and the release's asymptotic equivalent on the second; the standing derived from them is the frontmatter. No refereed publication exists for any of them. Ford's order-of-magnitude theorem falls short of a formula.

Er35b: Erdős, P., On the normal number of prime factors of $p-1$ and some related problems concerning Euler's $\varphi$ -function. Quart. J. Math. (1935), 205-213.
Er74b: Erdős, P., Remarks on some problems in number theory. Math. Balkanica (1974), 197-202; printed p. 201 defines the count and states both questions, with the Erdős–Hall bounds and Hall's improvement, recorded on Erdős 1974, The count of totient values and the doubling question. Library home: Erdős 1974.
Er79e: Erdős, Paul, Some unconventional problems in number theory. Astérisque (1979), 73-82.
Fo98: Ford, Kevin, The distribution of totients. Ramanujan J. (1998), 67-151.
Gu04: Guy, Richard K., Unsolved problems in number theory, third edition, Problem Books in Mathematics, Springer (2004), xviii+437 pp.; B36 "Euler's totient function", printed p. 139: Erdős and Hall's $\Phi(y)=ye^{f(y)}/\ln y$ for the number of $n\le y$ with $\phi(x)=n$ solvable, $f(y)$ between $c(\ln\ln\ln y)^2$ and $c(\ln y)^{1/2}$ [sic, as printed; the Erdős–Hall upper bound is $e^{f(y)}\le e^{c(\ln\ln y)^{1/2}}$ ], Maier and Pomerance's proof that the lower bound is correct with $c\approx0.8178$ , and Erdős's conjecture that $\Phi(cy)/\Phi(y)\to c$ , "the best substitute that one can find for an asymptotic formula for $\Phi(y)$ ". Library home: Guy 2004.
MaPo88: Maier, Helmut and Pomerance, Carl, On the number of distinct values of Euler's $\phi$ -function. Acta Arith. (1988), 263-275.
Pi29: Pillai, S. Sivasankaranarayana, On some functions connected with $\phi(n)$ . Bull. Amer. Math. Soc. (1929), 832-836.

Problem 416

Status

Proof claims

Discussion