I.

Statement of the problem.

1.1. The problem with which we are concerned in this paper may be stated roughly as follows: What is the normal degree of compositeness of a number $n$? We shall prove a number of theorems the general result of which is to shew that $n$ is, as a rule, composed of about $\log \log n$ factors.

These statements are vague, and we must define our problem more precisely before we proceed further.

1.2. There are two ways in which it is natural to measure the ``degree of compositeness'' of $n$, viz.

1. by its number of divisors,
2. by its number of prime factors.

In this paper we adopt the second point of view. A distinction arises according as multiple factors are or are not counted multiply. We shall denote the number of different prime factors by $f(n),$ and the total number of prime factors by $F(n)$, so that (e.g.) $$ f(2^3 3^2 5)=3, \ F(2^3 3^2 5)=6. $$ With regard to these functions (or any other arithmetical functions of $n$) four questions naturally suggest themselves.

(1) In the first place we may ask what is the minimum order of the function considered. We wish to determine an elementary function of $n$, with as low a rate of increase as possible, such that (e.g.) $$ f(n) \leq \phi(n) $$ for an infinity of values of $n$. This question is, for the functions now under consideration, trivial; for it is plain that $$ f(n)=F(n)=1 $$ when $n$ is a prime.

(2) Secondly, we may ask what is the maximum order of the function. This question also is trivial for $F(n):$ we have $$ F(n)=\frac{\log n}{\log \ 2} $$ whenever $n$ is of the form $2^k$; and there is no $\phi(n)$ of slower increase which satisfies the conditions. The answer is less obvious in the case of $f(n):$ but, supposing $n$ to be the product of the first $k$ primes, we can shew (by purely elementary reasoning) that, if $\epsilon$ is any positive number, we have $$ f(n)\lt (1+\epsilon)\frac{\log \ n}{\log \log \ n} $$ for all sufficiently large values of $n$, and $$ f(n)>(1-\epsilon)\frac{\log \ n}{\log \log \ n} $$ for an infinity of values; so that the maximum order of $f(n)$ is $$ \frac{\log \ n}{\log \log \ n}. $$

It is worth mentioning, for the sake of comparison, that the minimum order of $d(n)$, the number of divisors of $n$, is 2, while the maximum order lies between $$ 2^{(1-\epsilon)\log n/\log \log n}, \ \ 2^{(1+\epsilon) \log n/\log \log n} $$ for every positive value of $\epsilon$.¹

(3) Thirdly, we may ask what is the average order of the function. It is well known – to return for a moment to the theory of $d(n)$ – that

This result, indeed, is almost trivial, and far more is known; it is known in fact that this result being one of the deepest in the analytic theory of numbers. It would be natural, then, to say that the average order of $d(n)$ is $\log n$.

A similar problem presents itself for $f(n)$ and $F(n)$; and it is easy to shew that, in this sense, the average order of $f(n) $ and $F(n)$ is $\log \log n$. In fact it may be shewn, by purely elementary methods, that

where $A$ and $B$ are certain constants.

This problem, however, we shall dismiss for the present, as results still more precise than (1.23) and (1.24) can be found by transcendental methods.

(4) Fourthly, we may ask what is the normal order of the function. This phrase requires a little more explanation.

Suppose that $N(x)$ is the number of numbers, not exceeding $x$, which possess a certain property $P$. This property may be a function of $n$ only, or of $x$ only, of both $n$ and $x$: we shall be concerned only with cases in which it is a function of one variable alone. And suppose further that

when $x \rightarrow \infty$. Then we shall say, if $P$ is a function of $n$ only, that almost all numbers possess the property, and, if $P$ is a function of $x$ only, that almost all numbers less than $x$ possess the property. Thus, to take a trivial example, almost all numbers are composite.

If then $g(n)$ is an arithmetical function of $n$ and $\phi(n)$ an elementary increasing function, and if, for every positive $\epsilon$, we have

for almost all values of $n$, we shall say that the normal order of $g(n)$ is $\phi(n)$.

It is in no way necessary that a function should possess either a determinate average order or a determinate normal order, or that one should be determinate when the other is, or that, if both are determinate, they should be the same. But we shall find that each of the functions $f(n)$ and $F(n)$ has both the average order and the normal order $\log \log n.$

The definitions just given may be modified so as to apply only to numbers of a special class. If $Q(x)$ is the number of numbers of the class not exceeding $x$, and $N(x)$ the number of these numbers which possess the property $P$, and

then we shall say that almost all of the numbers (or almost all of the numbers less than $x$) possess the property.

II.

``Quadratfrei'' numbers.

2.1. It is most convenient to begin by confining our attention to quadratfrei numbers, numbers, that is to say, which contain no prime factor raised to a power higher than the first. It is well known that the number $Q(x)$ of such numbers, not exceeding $x$, satisfies the relation

We shall denote by $\pi_{\nu}(x)$ the number of numbers which are products of just $\nu$ different prime factors and do not exceed $x$, so that $\pi_1 (x)=\pi(x)$ is the number of primes not exceeding $x$, and $$ \sum^{\infty}_{1} \pi_{\nu} (x)=Q(x). $$ It has been shewn by Landau³ that

for every fixed value of $\nu$. In what follows we shall require, not an asymptotic equality, but an inequality satisfied for all values of $\nu$ and $x$.\bigskip

2.2. Lemma ${\rm A}$. There are absolute constants $C$ and $K$ such that

for $$\nu=0, 1,2, \dots, \ x\geq 2.$$

The inequality (2.21) is certainly true when $\nu=0$, whatever the value of $C$. It is known (and may be proved by elementary methods⁴) that

and where $B$ and $H$ are constants. We shall prove by induction that (2.21) is true if

Consider the numbers which do not exceed $x$ and are comprised in the table \begin{eqnarray*} 2\cdot p_1\cdot p_2\cdots p_{\nu},\\ 3\cdot p_1\cdot p_2\cdots p_{\nu},\\ 5\cdot p_1\cdot p_2\cdots p_{\nu},\\ \cdots \cdots,\\ P\cdot p_1\cdot p_2 \cdots p_{\nu}, \end{eqnarray*} where $p_1, p_2, \dots , p_{\nu}$ are, in each row, different primes arranged in ascending order of magnitude, and where $p_{\nu} \geq 2$ in the first row, $p_{\nu} \geq 3$ in second, $p_{\nu} \geq 5$ in the third, and so on. It is plain that $P \leq \surd x.$ The total number of numbers in the table is plainly not greater than $$ \sum_{p^{2} \leq x} \ \pi_{\nu} \left(\frac{x}{p}\right). $$

If now $\omega_1, \omega_2, \dots$ are primes and $$ \omega_1 \lt \omega_2 \cdots \lt \omega_{\nu+1,} \ \omega_1 \omega_2 \cdots \omega_{\nu+1 \leq x,} $$ the number $\omega_1 \omega_2 \cdots \omega_{\nu+1}$ will occur at least $\nu$ times in the table, once in the row in which the first figure is $\omega_1$ once in that in which it is $\omega_2, \dots$, once in that in which it is $\omega_{\nu}$. We have therefore

Assuming, then, that (2.21) is true when $\nu$ is replaced by $\nu-1$, we obtain⁵ But since $\log p \leq \myfrac{1}{2} \log x$; and so Substituting in (2.24), we obtain (2.21).

2.3. We can now prove one of our main theorems.

Theorem ${\rm A}$. Suppose that $\phi$ is a function of $x$ which tends steadily to infinity with $x$. Then

for almost all quadratfrei numbers $n$ less than $x$.

It is plainly enough to prove that

It will be sufficient to consider one of the two sums $S_1, S_2,$ say the latter; the discussion of $S_1$ proceeds on the same lines and is a little simpler. We have

Write $$ \log \log x+C=\xi. $$ Then the condition that $$ \nu >\log\log x+\phi \sqrt{\log\log x}, $$ where $\phi$ is some function of $x$ which tends steadily to infinity with $x$, is plainly equivalent to the condition that $$ \nu > \xi+\Psi \surd \xi, $$ where $\Psi$ is some function of $\xi$ which tends steadily to infinity with $\xi$; and so what we have to prove is that We choose a positive number $\delta$ so small that and write say. In the first place we have where $\nu_1$ is the smallest integer greater than $(1+\delta) \xi$. It follows that where the $K$'s are absolute constants and $$ \Delta=(1+\delta)\log(1+\delta)-\delta. $$ And since $$ (1+\delta)\log (1+\delta)-\delta > (1+\delta)(\delta-\myfrac{1}{2}\delta^2)-\delta=\myfrac{1}{2}\delta^2 (1-\delta)=\eta, $$ say, we obtain where $\eta$ is positive: so that In $S^{\prime},$ we write $\nu=\xi+\mu,$ so that $\Psi \surd \xi\lt \mu\leq \delta \xi.$ Then

Thus

since $\Psi \rightarrow \infty$. From (2.36), (2.374), and (2.382) follows the truth of (2.34), and so that of (2.322). As (2.321) may be proved in the same manner, the proof of Theorem A is completed.

2.4. Theorem ${\rm A}'$. If $\phi$ is a function of $n$ which tends steadily to infinity with $n$, then almost all quadratfrei numbers have between $$ \log \log n-\phi \sqrt{\log \log n} \ and \ \log \log n+\phi \sqrt{\log \log n} $$ prime factors.

This theorem is a simple corollary of Theorem A. Consider the numbers not exceeding $x$. We may plainly neglect numbers less than $\surd x$; so that $$ \myfrac{1}{2} \log x \leq \log n \leq \log x, $$

Given $\phi$, we can determine a function $\Psi (x)$ such that $\Psi$ tends steadily to infinity with $x$ and

Then $$ \Psi(x)\lt \myfrac{1}{2} \phi (n) \ (\surd x \leq n \leq x). $$

In the first place $$ \phi \sqrt{\log \log n} > \Psi \sqrt{\log \log x} $$ if $$ \log \log n > \myfrac{1}{4} \log \log x, $$ which is certainly true, in virtue of (2.41), for sufficiently large values of $x$. Thus

In the second place the corresponding inequality

is certainly true if $$ \phi \sqrt{\log \log n} > \Psi \sqrt{\log \log x}+\log 2; $$ and this also is true, in virtue of (2.41) and (2.42), for sufficiently large values of $x$. From (2.43), (2.44), and Theorem A, Theorem A$^{\prime}$ follows at once.

As a corollary we have

Theorem ${\rm A}^{\prime\prime}$. The normal order of the number of prime factors of a quadratfrei number is $\log \log n$.

III.

The normal order of $f(n)$.

3.1. So far we have confined our attention to numbers which have no repeated factors. When we remove this restriction, the functions $f(n)$ and $F(n)$ have to be distinguished from one another.

We shall denote by $\varpi_{\nu}(x)$ the number of numbers, not exceeding $x$, for which $$ f(n)=\nu. $$ It is obvious that $$ \varpi_{\nu}(x) \geq \pi_{\nu} (x). $$

We require an inequality for $\varpi_{\nu} (x)$ similar to that for $\pi_{\nu}(x)$ given by Lemma A.

Lemma ${\rm B}$. There are absolute constants $D$ and $L$ such that

for $$ \nu=0,1,2,\dots, \ x \geq 2. $$

It is plain that $$ \varpi_{1} (x)=\pi(x)+\pi (\surd x)+\pi (\sqrt[3]{x})+\cdots =O \left(\frac{x}{\log x}\right). $$

The inequality is therefore true for $\nu=0,$ whatever the value of $D$. We shall prove by induction that it is true in general if

where $B$ and $H$ have the same values as in 2.2, and

Consider the numbers which do not exceed $x$ and are comprised in the table \begin{eqnarray*} 2^{a}\cdot p_1^{a_1}\cdot p_2^{a_2} \cdots p_{\nu}^{a_{\nu}},\\ 3^{a}\cdot p_1^{a_1}\cdot p_2^{a_2} \cdots p_{\nu}^{a_{\nu}},\\ \ldots \ldots \ldots \ldots \ldots, \\ P^{a}\cdot p_1^{a_1}\cdot p_2^{a_2} \cdots p_{\nu}^{a_{\nu}}, \end{eqnarray*} where $p_1, p_2, \dots, p_{\nu}$ satisfy the same conditions as in the table of 2.2. It is plain that $P \leq \surd x$ if $a=1, P \leq \sqrt[3]{x}$ if $a=2$, and so on, so that the total number of numbers in the table does not exceed $$ \sum_{p^{a+1} \leq x} \ \varpi_{\nu} \left(\frac{x}{p^{a}}\right). $$ If now $\omega_1, \omega_2, \ldots$ are primes and $$ \omega_1 \lt \omega_2 \lt \cdots \lt \omega_{\nu +1}, \quad \omega_1^{a_1} \omega_2^{a_2} \cdots \omega^{a_{\nu +1}}_{\nu+1} \leq x, $$ the number $\omega_1^{a_1} \omega_2^{a_2} \cdots\omega^{a_{\nu +1}}_{\nu+1} $ will occur at least $\nu$ times in one of the tables which correspond to different values of $a$. We have therefore

Now let us suppose that (3.11) is true when $\nu-1$ is substituted for $\nu$. Then it is plain⁹ that Now as we have already seen in 2.2. Also, if $p^{s+1} \leq x$, we have $$ \frac{x}{p^s} \geq x^{1/(s+1)}, \quad \log \frac{x}{p^s} \geq \frac{\log x}{s+1}; $$ and so if $s\geq 2.$ Hence From (3.15) and (3.18) the truth of (3.11) follows immediately.

3.2. We can now argue with $\varpi_{\nu}(x)$ as we argued with $\pi_{\nu} (x)$ in 2.3 and the paragraphs which follow; and we may, without further preface, state the following theorems.

Theorem ${\rm B}$. If $\phi$ is a function $x$ which tends steadily to infinity to $x$, then $$\log \log x-\phi \sqrt{(\log \log x )} \lt f(n) \lt \log \log x+\phi \sqrt{(\log \log x)} $$ for almost all numbers $n$ less than $x$.

Theorem ${\rm B}^{\prime}$. If $ \phi$ is a function of $n$ which tends steadily to infinity with $n$, then almost all numbers have between $$\log \log n - \phi \sqrt{(\log \log n)}\quad and \quad\log \log n+ \phi \sqrt{(\log \log n)} $$ different prime factors.

Theorem ${\rm B}^{\prime\prime}$. The normal order of the number of different prime factors of a number is $\log \log n$.

IV.

The normal order of $F(n)$.

4.1. We have now to consider the corresponding theorems for $F(n)$, the number of prime factors of $n$ when multiple factors are counted multiply. These theorems are slightly more difficult. The additional difficulty occurs, however, only in the first stage of the argument, which requires the proof of some inequality analogous to those given by Lemmas A and B.

We denote by $$ \Pi_{\nu} (x) $$ the number of numbers, not exceeding $x$, for which $$ F(n)=\nu. $$ It would be natural to expect an inequality of the same form as those of Lemmas A and B, though naturally with different values of the constants. It is easy to see, however, that no such inequality can possibly be true.

For, if $\nu$ is greater than a constant multiple of $\log x$, the function $$ \frac{x}{\log x}\ \frac{(\log \log x +C)^{\nu}}{\nu !} $$ is — as may be seen at once by a simple approximation based upon Stirling's theorem — exceedingly small; and $\Pi_{\nu+1}(x)$, being an integer, cannot be small unless it is zero. Thus such an inequality as is suggested would shew that $F(n)$ cannot be of order as high as $\log x$ for any $n$ less than $x$; and this is false, as we can see by taking $$ x=2^{k} +1, \ n=2^k, \ F(n)=\frac{\log n}{\log 2}. $$ the inequality required must therefore be of a less simple character.

4.2. Lemma ${\rm C}$. Suppose that $K$ and $C$ have the same meaning as in Lemma A, and that

Then the series being continued to the term $\lambda^{\nu}$.

It is plainly sufficient to prove this inequality when $\lambda=\frac{9}{10}$. In what follows we shall suppose that $\lambda$ has this particular value.

We require a preliminary inequality analogous to (2.23) and (3.14). Consider the numbers which do not exceed $x$ and are comprised in the table \begin{eqnarray*} 2^{a}\cdot p_1\cdot p_2 \cdots p_{\nu+1-a},\\ 3^{a}\cdot p_1\cdot p_2 \cdots p_{\nu+1-a},\\ \ldots\ldots\ldots\ldots, \\ P^{a}\cdot p_1\cdot p_2 \cdots p_{\nu+1-a}, \end{eqnarray*} where now $p_1, p_2, \dots, p_{\nu+1-\alpha}$ are primes, arranged in ascending order of magnitude, but not necessarily different, and where $p_{\nu+1-\alpha} \geq 2$ in the first row, $p_{\nu+1-\alpha} \geq 3$ in the second, and so forth. Arguing as in 2.2. and 3.1, we now find

This inequality differs formally from (3.14) in that the suffixes of the functions on the right-hand side sink by one from term to term.

We can now prove (4.22) by a process of induction similar in principle to that of 2.2 and 3.1. Let us suppose that the inequality is true when $\nu$ is replaced by $\nu-1$, and let us write $$ \log \log {x}+C = \xi, $$ as in 2.3. Substituting in (4.23), and observing that $$ \log \log \frac{x}{p^{s}}+C \leq \xi, $$ we obtain

Now, as we have seen already,

and if $s \geq 2$. It is moreover easy to prove that if $s=2,$ and if $s>2$.¹⁰ From (4.24) – (4.2532) it follows that When we collect together the various terms on the right-hand side which involve the same powers of $\xi$, it will be found that the coefficient of $\xi^{\nu-p}$ is exactly $$ \frac{Kx}{\log x} \ \frac{\lambda p}{(\nu-p)!}, $$ except when $p=1$, when it is $$ \left(1-\frac{1}{\nu}\right) \frac{Kx}{\log x} \ \frac{\lambda}{(\nu-1)!}. $$ We thus obtain (4.22).

4.3. We may now argue substantially as in 2.3. We have to shew, for example, that

and this is equivalent to proving that where $\Psi$ is any function of $x$ which tends to infinity with $x$.

We choose $\delta$ so that

and write say. In $S^{\prime}$, we have where and by means of this inequality we can shew, just as in 2.3, that In discussing $S^{\prime\prime}$ we must use (4.22) in a different manner. We have and so where by (4.33). Hence From (4.34), (4.353), and (4.364), it follows that $S=o(x)$.

4.4. We have therefore the following theorems.

Theorem ${\rm C}$. The result of Theorem B remains true when $F(n)$ is substituted for $f(n)$.

Theorem ${\rm C}^{\prime}$. The result of Theorem ${\rm B}^{\prime}$ remains true when the word ``different'' is omitted.

Theorem ${\rm C}^{\prime\prime}$. The normal order of the total number of prime factors of a number is $\log \log n$.

V.

The normal order of $d(n)$.

5.1. It is natural to ask whether similar theorems cannot be proved with regard to some of the other standard arithmetical functions of $n$, such as $d(n)$.

If $$ n=p_1^{a_1} p_2^{ a_2} \cdots p_{\nu}^{ a_{\nu}}, $$ we have $$ d(n)=(1+a_1)(1+a_2) \cdots (1+a_{\nu}). $$ Since $$ 2 \leq 1+a \leq 2^{a} $$ if $ a \geq 1,$ we obtain at once $$ 2^{\nu} \leq d(n) \leq 2^{a_{1}+a_{2}+ \cdots +a_{\nu}}, $$ or

From (5.11), and Theorems $B^{\prime}$ and $C^{\prime}$, we obtain at once

Theorem ${\rm D}^{\prime}$. The inequalities

where $\phi$ is any function of $n$ which tends to infinity with $n$, are satisfied for almost all numbers $n$.

The inequalities (5.12) are of a much less precise type than (1.26): we cannot say that the normal order of $d(n)$ is $2^{\log \log n}$. We can however say that (to put it roughly) the normal order of $d(n)$ is about $$ 2^{\log \log n}=(\log n)^{\log 2}=(\log n)^{0.69\dots}. $$ It should be observed that this order is far removed from $\log n$, the average order f $d(n)$. The explanation of this apparent paradox is simple. The majority of numbers have about $(\log n)^{\log 2}$ divisors. But those which have an abnormal number may have a very much larger number indeed: the excess of the maximum order over the normal order is so great that, when we compute the average order, it is the numbers with an abnormal number of divisors which dominate the calculation. The maximum order of the number of prime factors is not large enough to give rise to a similar phenomenon.