6
$\begingroup$

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
$\endgroup$
  • 3
    $\begingroup$ Do you know how you can compute the number of divisors of $n$ from the prime factorisation of $n$? $\endgroup$ – Daniel Fischer Nov 29 '15 at 19:48
4
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.