17 divisors

Number Theory Level 2

What is the smallest positive integer with exactly 17 positive divisors?

The answer is 65536.

4 solutions

Arjen Vreugdenhil
Apr 2, 2020

If the prime number decomposition of a number $N$ is $N = p_1^{e_1} \cdot p_2^{e_2} \cdots,$ then every divisor $d | N$ has the form $d = p_1^{a_1} \cdot p_2^{a_2} \cdots$ with $0 \leq a_i \leq e_i$ . There are $\delta(N) = (e_1+1)\cdot (e_2+1)\cdots$ ways to choose the exponents $a_i$ .

Now we have $\delta(N) = 17$ . Since 17 is prime, we can only have one prime $p_1$ and $e_1 + 1 = 17$ . Thus $N = p_1^{16}.$ The smallest possible choice for $p_1$ is 2, so $N = 2^{16} = \boxed{65\:536}.$

Wow, what an amazing puzzle to tease coworkers, and an unexpected insight into the NT! I never looked into the number of divisors before, and the amazing facts pop out immediately:
(1) the number of divisors of $n$ , $d(n)=2$ iff $n$ is a prime; generalizing,
(2) every divisor is a product of 0 to $k$ of every factor of $n$ with the multiplicity $k$ , so for the factoring $n=\prod p_i^{k_i}$ , every divisor is a $\prod p_i^{\{0,...,k_i\}}$ , and, since any combination of the prime factors yields a unique divisor, $d(n)=\prod (k_i+1)$ , which is, curiously,
(3) odd iff $n$ is a square (all terms in the product are odd iff all $k$ are even, i.e. $n$ is a square).
(4) Also, $d(n)=3$ iff $n$ is a square of a prime (divisors being $\{1,p,p^2=n\}$ ), and, generalizing,
(5) $d(n)=k+1$ if $n$ is a $k^\mathrm{th}$ power of a prime; even stronger,
(6) $d(n)=k+1$ iff $n$ is a $k^\mathrm{th}$ power of a prime and $d(n)$ itself is a prime, so that its computation in (2) is a unique factoring with a single term, which immediately yields a solution.

More stuff on topic:
https://oeis.org/A000005 - a lot of references there. The low OEIS sequence number 5, wow!
https://terrytao.wordpress.com/2008/09/23/the-divisor-bound/
https://terrytao.files.wordpress.com/2009/01/whatsnew.pdf, p. 59: same as above, expanded.

For a little numeric fun, following the Tao's paper, the mean $M(N) = \frac 1 N \sum_{n=1+s}^{N+s} \frac{\ln n}{d(n)}$ (with a small $s=10000$ to offset the likely irregularities in the range of small $n$ ) grows, albeit excruciatingly slowly: for $N=\{1,2,5,10,20,50,100\} \times 10^6$ , $M(N)=\{1.931, 1.982, 2.049, 2.099, 2.147, 2.210, 2.261\}$ . The log-log mean, $M'(N) = \frac 1 N \sum_{n=1+s}^{N+s} \frac{\ln \ln n}{d(n)},$ on the other hand, falls as the $N$ grows: for $N=\{1,3,10,30\} \times 10^6$ , $M'(N)=\{0.383548, 0.380563, 0.377107, 0.373889 \}$ .

Es Tnjui - 10 months, 2 weeks ago

Mahdi Raza
Apr 24, 2020

If $N = 2^{a_{1}} \cdot 3^{a_{2}} \cdots p_{n}^{a_{n}}$ , the number of divisors = $\bigg(a_{1} + 1\bigg)\cdot\bigg(a_{2} + 1\bigg)\cdots \cdot\bigg(a_{n} + 1\bigg)$ . Since $17$ is prime it cannot be factorised as a product of two numbers other than $1 \times 17$ . Thus, to have the smallest possible value, we assign $17 = a_{1} + 1$ and $1 = a_{2} + 1$ . $\implies a_{1} = 16, a_{2} = 0$ .

$\therefore N = 2^{(16)} \cdot 3^{(0)} = 2^{16} = \boxed{65536}$

I like how you have periodically solved it

Nethra Ramakrishnan - 1 year, 1 month ago

A Former Brilliant Member
Apr 20, 2020

Factors of 17 = 17 and 1

Subtract 1 from each factor = 16 and 0 = 16

$2^{16}$ = $65536$

Vinod Kumar
Oct 28, 2020

17 being a prime number of divisors, the only solution is that smallest number be 2^16 giving answer as 17.

The fact that 17 is odd tells you that the answer is a square; but it doesn't immediately follow that it is a power of two.

For instance, the smallest number with 15 divisors is 144, not $2^{14} = 16384$ .

Arjen Vreugdenhil - 7 months, 2 weeks ago

I made an error while typing, I should have said that 17 being a prime number instead of an odd number.

Vinod Kumar - 7 months, 2 weeks ago

17 divisors

The answer is 65536.

4 solutions

0 pending reports