Counting distinct values of Euler’s totient function

← All digests

Family 024 · Number theory
Importance 3/5 · Provisional editorial rating
Sources consulted 2026-10-10

1. The question

Euler’s totient function $\varphi(n)$ counts the integers from one to $n$ that are coprime to $n$. Its values repeat: $\varphi(5)=\varphi(8)=\varphi(10)=\varphi(12)=4$. Other integers never occur. How many different outputs are at most $x$?

This is not the same as counting inputs $n\le x$, or even counting all inputs whose outputs are at most $x$. Every output must be counted exactly once, regardless of how many preimages it has.

Family 024 claims an explicit asymptotic equivalent for the number of distinct totients. It also answers a simpler-looking question of Erdős and Hall: if the output bound is multiplied by a fixed constant $c$, does the number of outputs asymptotically multiply by $c$ too? The manuscript’s answer is yes.

2. Background and essential definitions

The product formula is

$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right),$$

where the product is over distinct prime divisors. In particular, $\varphi(p)=p-1$ for a prime, and $\varphi(ab)=\varphi(a)\varphi(b)$ when $a,b$ are coprime.

Let

$$\mathcal V=\{\varphi(n):n\ge1\},\qquad V(x)=\#\{v\in\mathcal V:v\le x\}.$$

The symbol $\mathcal V$ denotes the set of outputs, while $V(x)$ counts them. The prime outputs alone show that $V(x)$ is at least roughly $x/\log x$, but products of shifted primes contribute many additional values.

An asymptotic equivalent $V(x)\sim M(x)$ means $V(x)/M(x)\to1$. This is stronger than $V(x)\asymp M(x)$, which only places the ratio between two positive constants. A bounded but unknown multiplicative factor can still prevent a limiting ratio from being known.

All logarithms here are natural, and $\log_j x$ means the logarithm iterated $j$ times. Thus $\log_2 x=\log\log x$, while $\log_3 x=\log\log\log x$. Formulas involving several such logarithms are intended for sufficiently large $x$.

For a totient value $v$, define its least preimage by

$$\ell(v)=\min\{n\ge1:\varphi(n)=v\}.$$

For example, $\ell(4)=5$. Counting distinct outputs, counting all preimages and locating the least preimage are three different problems; the manuscript addresses the first and gives an additional result on the third.

3. Development history and previous partial results

Pillai proved that totient values have density zero among the positive integers. Erdős sharpened upper bounds using the typical factorization of $p-1$, and his work on products of two shifted primes improved the elementary lower bound.

Erdős and Hall obtained a much larger lower-order factor and asked whether $V(cx)/V(x)\to c$ for fixed $c>1$. Their 1976 paper is the source of this dilation question. Pomerance brought the upper bound to the same logarithmic scale; Maier and Pomerance then identified the leading constant in the exponent:

$$V(x)=\frac{x}{\log x} \exp\!\left((C_0+o(1))(\log_3x)^2\right), \qquad C_0\approx0.8178146.$$

Ford’s 1998 work went much further, determining the count up to a bounded multiplicative factor and describing the prime-factor structure of typical preimages. The current manuscript uses the revised 2013 version of that paper as its structural input.

Ford also proved that a fixed multiplicative interval $(x,cx]$ contains a number of totients comparable to $V(x)$. This guarantees many outputs in that interval, but does not specify the limiting ratio or remove the bounded factor in the total count.

The remaining task is delicate because multiple prime factorizations can produce the same output. Approximating every factorization by a continuous volume can overcount. The new manuscript retains the short arithmetic tail exactly and controls collisions between the long prefixes before claiming an asymptotic for distinct values.

4. What the new manuscripts claim

A scale with an arithmetic phase coefficient

The explicit main term uses constants defined by a positive recurrence. Put

$$a_j=(j+1)\log(j+1)-j\log j-1\qquad(j\ge1),$$

and let $\rho\in(0,1)$ be the unique solution of

$$\sum_{j\ge1}a_j\rho^j=1.$$

Define

$$\lambda=\log(1/\rho),\qquad g_0=1,\qquad g_j=\sum_{d=1}^{j}a_dg_{j-d}.$$

For large $x$, set

$$B=\log_2x,\qquad m=\left\lfloor\frac{\log B-\log_2B}{\lambda}\right\rfloor, \qquad \theta=\frac{\log B-\log_2B}{\lambda}-m,$$

so $0\le\theta<1$, and put

$$G_m=\frac{B^m}{m!\prod_{j=1}^{m}g_j}.$$

Theorem 2.1 claims

$$\boxed{V(x)\sim\frac{x}{\log x}G_m A(1;\theta).}$$

The factor $A(1;\theta)$ is positive and bounded above and away from zero. It is a function of a phase, not asserted to be a single constant. It is defined independently of $V(x)$ as a uniform limit of explicit approximants $A_H(1;s)$ built from finite prime and integer data.

The notation “1” means that every tail value receives weight one. Section 6 below describes the construction. The coefficient is not defined tautologically by dividing the unknown count by its proposed scale.

Fixed dilation

The same theorem claims, for every fixed real $c>0$,

$$\frac{V(cx)}{V(x)}\longrightarrow c.$$

This is called regular variation of index one. For example, $(x,2x]$ contains asymptotically as many distinct totients as $[1,x]$, even though the proportion of all integers that are totients tends to zero.

The manuscript proves this by comparing counts at common endpoint parameters. It does not infer the conclusion from an unproved continuity property of the phase coefficient. No continuity or other regularity of $s\mapsto A(1;s)$ is asserted.

Where least preimages lie

For a fixed positive integer $k$, let

$$N_k(x)=\#\{v\in\mathcal V:v\le x,\ kx<\ell(v)\le(k+1)x\}.$$

Define the bounded nonnegative weight

$$f_k(r)=\min\{1,(k+1)/r\}-\min\{1,k/r\}.$$

Theorem 2.2 claims a corresponding weighted formula,

$$N_k(x)=\frac{x}{\log x}G_m\bigl(A(f_k;\theta)+o(1)\bigr).$$

If there is even one totient $d$ with $\ell(d)>kd$, then $A(f_k;s)$ is uniformly positive and $N_k(x)\asymp_k V(x)$. If there is no such seed, $N_k(x)=0$ for every $x>0$. The positive alternative is established for $k=1,2$; the manuscript does not determine all larger $k$.

5. Why the advance matters

Provisional importance: 3/5. Taken as stated, the theorem closes a longstanding gap between order-of-magnitude estimates and an asymptotic equivalent for the range of a fundamental arithmetic function. It also answers the Erdős–Hall fixed-dilation question.

The main term retains genuinely discrete arithmetic information. A continuous approximation captures most prime-factor geometry, but it cannot simply erase collisions among the smaller factors. The coefficient records these collisions through a finite union before taking a limit.

This is a substantial advance in the distribution of arithmetic-function values. Its scope is precise: it counts distinct totients and locates certain least preimages, without resolving all multiplicity or inverse-totient questions.

6. The main idea

Separate a long prime prefix from a short exact tail

Order the prime factors of a suitable preimage from largest to smallest. Ford’s structural estimates place their double logarithms in a region resembling a simplex, a higher-dimensional generalization of a triangle.

The manuscript splits this list twice. A long prefix is treated continuously by volume. A shorter collection of smaller primes, together with a smooth cofactor whose prime factors are bounded, is kept as exact arithmetic data. The two cuts are separated so the discarded part is small enough to absorb the tail’s complexity.

For a fixed tail cutoff $H$, the retained tail possibilities are finite and independent of $x$. The proof first lets $x$ grow with $H$ fixed, and only then lets $H$ grow. Reversing that order would lose the finite-arithmetic interpretation.

Count outputs rather than descriptions

Different long prefixes might yield the same totient. The paper compares equations between products of shifted primes and shows that the total contribution of such prefix collisions is negligible. It uses a layered method descended from Maier–Pomerance and Ford; each sieve application involves only two or three linear forms even though the number of layers grows.

The structural coverage must also be strong enough for the least-preimage analysis: outside a negligible exceptional set, every relevant preimage has the required form. Finding one convenient preimage would not by itself control the least one.

After prefix collisions have been removed, different exact tails can still give the same value. They are deliberately not declared unique. Instead, all regions permitted by tails with the same totient are combined by taking their union. Inclusion–exclusion counts that union once.

What the coefficient records

A concrete probabilistic description makes the finite union easier to interpret. Fix a phase $s$, set

$$\alpha_s=\lambda e^{\lambda s},\qquad \gamma=\left(\sum_{j\ge1}j a_j\rho^j\right)^{-1},$$

and enumerate the permitted bounded tails $\eta$. Each tail is an integer $w(\eta)$ expressed using a prescribed finite list of primes and a smooth cofactor. It has a totient $d=\varphi(w(\eta))$.

If the tail primes are indexed by $l<H$, their double logarithms $v_l$ determine thresholds

$$D(h,\eta)=\sum_l a_{h-l}v_l\qquad(h\ge H).$$

The sums run over the retained tail indices. The manuscript’s explicit bounded inequalities specify which lists are permitted. The continuous prefix volume allowed by a tail is represented by an event

$$E_\eta=\bigcap_{h\ge H} \left\{E_h\ge\frac{\gamma}{\alpha_s}\rho^hD(h,\eta)\right\},$$

where the $E_h$ are independent exponential random variables of mean one. These auxiliary variables encode volumes; the theorem does not model prime factors as literally independent random variables.

The approximant $A_H(f;s)$ is a normalized sum over distinct tail totients $d$, with weight $f(\ell(d)/d)/d$, multiplied by the probability of the union of the events for all tails producing $d$. The normalization is

$$\rho^{H(H-1)/2}\left(\frac{\gamma}{\alpha_s}\right)^H.$$

There are finitely many tails for each $H$. Intersections of their events use the maximum threshold at each coordinate, so exponential probabilities and finite inclusion–exclusion give an explicit formula with absolutely convergent series. The main coefficient uses $f=1$, requiring no least-preimage search. For weighted coefficients, a tail witness itself bounds the finite search for $\ell(d)$.

Uniform convergence in the phase produces $A(1;s)$ and the particular $A(f_k;s)$ needed above. Counting the largest prime supplies the factor $x/\log x$ and the tail weight $1/d$; normalized prefix volumes supply $G_m$ and the remaining coefficient.

7. Scope, limitations, and open questions

The coefficient is explicit through finite arithmetic approximants and a uniform limit. The theorem does not assert that it is constant, continuous or easy to evaluate efficiently. No numerical convergence rate for computing it is part of the headline statement.

The dilation factor $c$ is fixed. The result does not automatically give uniform estimates for $c$ depending on $x$, or asymptotics in short additive intervals.

Most importantly, uniqueness of the long prefix is not uniqueness of the whole preimage. Large fibers of $\varphi$, including those discussed in family 011, are compatible with this theorem and are not an input to it.

The question whether $\ell(d)/d$ is unbounded remains unresolved here. Equivalently, the least-preimage positive alternative is not established for every integer $k$. An asymptotic formula for the range does not settle all inverse problems for the function.

8. Sources and further reading

Theorems 2.1–2.2 give the main and weighted asymptotics. Section 2.2, especially equations (2.5)–(2.8), gives the complete finite-tail definition of the coefficient. Sections 4–5 control prefix collisions, Section 6 proves the limiting formula, and Section 7 treats least preimages.

The Erdős–Hall paper and Ford’s revised distribution paper linked in section 3 are the principal historical sources. The manuscript also cites Pillai, Erdős, Pomerance and Maier–Pomerance for the earlier bounds. Optional background on Euler’s totient function helps connect the product formula to its range.

Source manuscripts

• M1. OpenAI, An asymptotic formula for the number of totients (September 25, 2026).

Sources consulted on 10 October 2026 at repository revision fd4aeeb. Download the manuscript citations.