TAOCP 3.2.1.1 Exercise 7

Exercise 7. [M24] What patterns can you spot in Table 1?

Verified: yes
Solve time: 1m48s

Solution

Examination of Table 1 reveals several recurring structural patterns in the factorizations of $w \pm 1$. First, consider numbers of the form $2^e - 1$. Many of these are Mersenne numbers, and when $e$ is prime, $2^e - 1$ is often prime, as in $2^{17}-1 = 131071$, $2^{19}-1 = 524287$, and $2^{31}-1 = 2147483647$. When $e$ is composite, the number $2^e - 1$ typically factors into small primes repeated in various powers, together with occasional larger primes. For example, $2^{24}-1 = 3^2 \cdot 5 \cdot 7 \cdot 13 \cdot 17 \cdot 241$ exhibits several small primes in low powers.

Similarly, numbers of the form $2^e + 1$ are Fermat-like numbers for small $e$. When $e = 2^k$ for some $k$, the number may be prime or factor into relatively large primes. For instance, $2^{16}+1 = 65537$ is prime, while $2^{32}+1 = 641 \cdot 6700417$ factors into two relatively large primes. In general, the plus-one numbers are more likely to contain larger prime factors than the corresponding minus-one numbers, reflecting the known irregularity of Fermat numbers.

The factorization of $3^e - 1$ displays a systematic pattern arising from the identity $3^e - 1 = (3-1)(3^{e-1} + 3^{e-2} + \cdots + 1) = 2 \cdot S$, where $S$ is a sum of powers of 3. This explains the frequent occurrence of small prime powers such as $3^2$, $3^3$, $3^4$, and the factors 7, 13, 37, etc., in these factorizations. Likewise, $3^e + 1$ often factors into primes of moderate size, sometimes with repeated patterns reflecting divisibility properties for even and odd $e$.

Another pattern concerns the growth of the largest prime factors. In $2^e - 1$ and $3^e - 1$, the largest prime tends to increase rapidly with $e$, often dominating the factorization, whereas in $2^e + 1$ and $3^e + 1$, the factors are more balanced between medium-size primes. This observation aligns with the theoretical expectation that numbers of the form $b^e \pm 1$ have predictable small factors related to cyclotomic polynomials, leaving one or more large primes as $e$ increases.

Further, many factorizations exhibit repeated prime powers, particularly for small primes. For instance, $3^2 \cdot 5^2 \cdot 7 \cdot 11 \cdot 13 \cdot 31 \cdot 41 \cdot 61 \cdot 151 \cdot 331 \cdot 1321$ occurs in $3^{60}-1$, demonstrating the compounded effect of repeated small prime divisors as $e$ increases. This reflects the arithmetic identity $b^{mn}-1 = (b^m-1)(b^{m(n-1)} + \cdots + 1)$, which recursively produces small prime factors from lower powers.

A final pattern is observed in the parity and relative sizes of the factors. For $2^e - 1$, all factors are odd, as expected, and for $2^e + 1$, at least one factor may be even if $e=1$, otherwise all are odd. The distributions of primes also suggest that minus-one numbers tend to have more small factors, while plus-one numbers often contain larger primes relative to $e$.

In summary, Table 1 exhibits the following patterns: Mersenne numbers ($2^e-1$) are often prime for prime $e$ and otherwise factor into small primes with a dominant large prime; Fermat-like numbers ($2^e+1$) often have fewer small factors and larger primes; powers of 3 minus one factor into small prime powers multiplied by occasional larger primes; powers of 3 plus one contain moderate-size primes with systematic variation depending on parity; repeated prime powers appear for large exponents due to multiplicative identities; and the largest prime factor generally grows with $e$ in all sequences.

This completes the solution.

∎