# Why does A005179 (smallest number with N factors) have spikes at prime numbers of factors?

A005179 is a list of the lowest number with n factors, for each n. The list has rather extreme local maxima when n is prime. Why?

n lowest number with n factors
1 1
2 2
3 4
4 6
5 16
6 12
7 64
8 24
9 36
10 48
11 1024
12 60
13 4096
14 192
15 144
16 120
17 65536
18 180
19 262144
20 240
• Do you know how you can compute the number of divisors of $n$ from the prime factorisation of $n$? – Daniel Fischer Nov 29 '15 at 19:48

There's a nice theorem which is directly applicable:

If $m=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$ where the $p_i$s are distinct primes, then the number of factors of $m$ is $$(a_1+1)(a_2+1)\dots(a_k+1)$$

In the above, each $a_i+1$ term represents choosing which power of $p_i$ is used in the factor.

Now, let $m$ be the $q$-th term the A005179 sequence where $q$ is prime, and let $m=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$. From the theorem, we have $$q=(a_1+1)(a_2+1)\dots(a_k+1)$$ However, since $q$ is prime it can only be written as a product of $1$ and itself - hence for some $i$ we have $a_i+1=q$ while for $j\ne i$ we have $a_j+1=1$. This means the $q$-th term in the sequence is just $m=p_i^{q-1}$ for some prime $p_i$, and since $2$ is the smallest prime, the $q$-th term is $2^{q-1}$.

It is an extreme spike because (in loose terms) the $n$-th term where $n$ is composite can be written with fewer powers of primes. For example the $10$-th entry is $48=2^4\cdot3$ requiring only $5$ powers of primes while the $11$-th entry is $1024=2^{10}$, requiring $10$ powers of a prime. In particular, the $(q-1)$-th entry is $\le 2^{(q-3)/2}\cdot3$ and the $(q+1)$-th entry is $\le 2^{(q-1)/2}\cdot3$ (where $q$ is an odd prime).