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

The answer is 65536.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

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

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}$

1 Helpful
0 Interesting
2 Brilliant
1 Confused

I like how you have periodically solved it

Nethra Ramakrishnan
- 1 year, 1 month ago

Factors of 17 = 17 and 1

Subtract 1 from each factor = 16 and 0 = 16

$2^{16}$ = $65536$

2 Helpful
1 Interesting
2 Brilliant
4 Confused

0 Helpful
0 Interesting
0 Brilliant
0 Confused

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

Log in to reply

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

×

Problem Loading...

Note Loading...

Set Loading...

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}.$