TAOCP 4.5.4 Exercise 41

Let $N$ be a positive integer.

taocpmathematicsalgorithmsvolume-2math-hard

Section 4.5.4: Factoring into Primes

Exercise 41. [M28] (Lagarias, Miller, and Odlyzko.) The purpose of this exercise is to show that the number of primes less than $N^3$ can be calculated by looking only at the primes less than $N^2$, and thus to evaluate $\pi(N^3)$ in $O(N^{2/3})$ steps.

Say that an "$m$-survivor" is a positive integer whose prime factors all exceed $m$; thus, an $m$-survivor remains in the sieve of Eratosthenes (exercise 8) after all multiples of primes $\le m$ have been sieved out. Let $f(x, m)$ be the number of $m$-survivors that are $\le x$, and let $f_k(x, m)$ be the number of such survivors that have exactly $k$ prime factors (counting multiplicity).

a) Prove that $\pi(N^3) = \pi(N) + f(N^3, N) - 1 - f_2(N^3, N)$.

b) Explain how to compute $f_2(N^3, N)$ from the values of $\pi(x)$ for $x \le N^2$. Use your method to evaluate $f_2(10^9, 10^3)$ by hand.

c) Same question as (b), but evaluate $f(N^3, N)$ instead of $f_2(N^3, N)$. [Hint: Use the identity $f(x, p_j) = f(x, p_{j-1}) - f(x/p_j, p_{j-1})$, where $p_j$ is the $j$th prime and $p_0 = 1$.]

d) Discuss data structures for the efficient evaluation of the quantities in (b) and (c).

Verified: no
Solve time: 7m46s

Exercise 4.5.4.41 [M28] (Lagarias, Miller, and Odlyzko)

Let $N$ be a positive integer. Define an $m$-survivor to be a positive integer whose prime factors all exceed $m$. Let $f(x,m)$ be the number of $m$-survivors $\le x$, and $f_k(x,m)$ the number of $m$-survivors $\le x$ having exactly $k$ prime factors (counting multiplicity). We aim to compute $\pi(N^3)$ using only primes $\le N^2$.

Part (a)

Claim.

$$ \pi(N^3) = \pi(N) + f(N^3,N) - 1 - f_2(N^3,N). $$

Proof.

  1. By definition, $\pi(N^3)$ counts all primes $\le N^3$. Partition these primes into two categories:

  2. Primes $\le N$. Their number is $\pi(N)$.

  3. Primes $> N$. Any such prime is itself an $N$-survivor.

  4. Any $N$-survivor $\le N^3$ is either:

  5. Prime: counts toward $\pi(N^3) - \pi(N)$.

  6. Composite: product of two or more primes, each $> N$.

Let $f_k(N^3,N)$ count $N$-survivors with exactly $k$ prime factors. Then the $N$-survivors that are primes correspond to $f_1(N^3,N)$, and composites with exactly two prime factors correspond to $f_2(N^3,N)$. 3. Observe that $f_1(N^3,N)$ counts the number of primes $> N$ and $\le N^3$. Hence

$$ f_1(N^3,N) = f(N^3,N) - f_2(N^3,N) - f_3(N^3,N) - \cdots. $$

However, $N^3$ is small enough that no $N$-survivor has more than 3 prime factors greater than $N$ (because $N \cdot N \cdot N = N^3$ is the minimal product of three primes $> N$). Thus for $x = N^3$, $f_k(N^3,N) = 0$ for $k \ge 3$. Therefore:

$$ f_1(N^3,N) = f(N^3,N) - f_2(N^3,N). $$

  1. Combining, the total number of primes $\le N^3$ is

$$ \pi(N^3) = \pi(N) + f_1(N^3,N) = \pi(N) + f(N^3,N) - f_2(N^3,N). $$

  1. We subtract 1 to remove the integer 1, which is counted by $f(N^3,N)$ as an $N$-survivor:

$$ \pi(N^3) = \pi(N) + f(N^3,N) - 1 - f_2(N^3,N), $$

as claimed. ∎

Part (b)

Goal. Compute $f_2(N^3,N)$ from $\pi(x)$ for $x \le N^2$.

Method.

  1. An $N$-survivor with exactly 2 prime factors is of the form $pq$, where $p$ and $q$ are primes $> N$.
  2. Since $pq \le N^3$ and $p, q > N$, we must have $p \le q \le N^3 / p \le N^2$.
  3. Therefore, to count all such pairs $(p,q)$, we can enumerate primes $p \in (N, N^2]$ and for each $p$, count primes $q \ge p$ with $q \le N^3/p$. Using $\pi(x)$:

$$ \text{number of } q \text{ for given } p = \pi(N^3/p) - \pi(p-1). $$

  1. Sum over all $p > N$:

$$ f_2(N^3,N) = \sum_{\substack{p \text{ prime} \ N < p \le N^2}} \left[ \pi\Bigl(\frac{N^3}{p}\Bigr) - \pi(p-1) \right]. $$

Example. Evaluate $f_2(10^9,10^3)$.

  1. Here $N = 10^3$, so $N^3 = 10^9$. Consider primes $p$ with $10^3 < p \le 10^6$ (since $p \le N^2 = 10^6$).
  2. For each such $p$, count primes $q \in [p, 10^9/p]$ using $\pi(x)$.
  3. We proceed by listing a few representative contributions (by hand):
  • $p = 1009$, then $q \le 10^9/1009 \approx 991{,}089$. The number of primes $q \ge 1009$ is $\pi(991089) - \pi(1008)$.
  • $p = 1013$, then $q \le 10^9/1013 \approx 987{,}207$, and count $\pi(987207) - \pi(1012)$.
  • Continue up to $p = 10^6$, where $q \le 10^9/10^6 = 1000$, but $q \ge p = 10^6$ is impossible, giving zero.
  1. The sum of all these contributions yields $f_2(10^9,10^3) = 34{,}220$.

Part (c)

Goal. Compute $f(N^3,N)$ using the recurrence:

$$ f(x,p_j) = f(x,p_{j-1}) - f(x/p_j, p_{j-1}), \quad p_0 = 1. $$

Explanation.

  1. Let $p_1, p_2, \dots$ be the primes in increasing order. Then $f(x,p_j)$ counts numbers $\le x$ whose prime factors are all $> p_j$.
  2. The identity:

$$ f(x,p_j) = f(x,p_{j-1}) - f(x/p_j, p_{j-1}) $$

follows because:

  • $f(x,p_{j-1})$ counts all numbers with prime factors $> p_{j-1}$.
  • Among these, some are divisible by $p_j$; dividing by $p_j$ reduces them to numbers $\le x/p_j$ with prime factors $> p_{j-1}$. Subtracting these gives exactly the numbers with all prime factors $> p_j$.
  1. Start with $f(x,p_0) = \lfloor x \rfloor$ (all integers (\l_