Divisor Equation(2)

Number Theory Level 5

Define $d(n)$ to be the number of positive divisors of $n$ for a positive integer $n.$ For example, $d(2018)=4.$

What is the smallest positive integer $k$ such that no $n$ satisfies the equation $\frac{n}{d(n)}=k?$

If you think there is no answer, write 0 as your answer.

Bonus: Solve this without a computer program.

The answer is 18.

1 solution

Patrick Corn
Jul 25, 2018

The answer is $k=18.$

First let's show that every smaller number equals $\frac{n}{d(n)}$ for some $n.$ This can be done by inspection:

k	n
1	1
2	8
3	24
4	36
5	40
6	72
7	56
8	80
9	108
10	180
11	88
12	240
13	104
14	252
15	360
16	128
17	136

Now there is a relatively trivial upper bound on $d(n),$ namely $d(n) \le 2\sqrt{n}.$ This is clear because divisors can be put into pairs which multiply to $n,$ so that one of the numbers in each pair is $\le \sqrt{n}.$ (This still works for perfect square $n$ ; think about it if you're unsure.)

So this gives $\frac{n}{d(n)} \ge \frac{n}{2\sqrt{n}} = \frac{\sqrt{n}}2.$ So we need only compute $\frac{n}{d(n)}$ up to $n=1296$ to be sure that $\frac{n}{d(n)}=18$ has no solution. This is easy for a computer.

k	n
1	1
2	8
3	24
4	36
5	40
6	72
7	56
8	80
9	108
10	180
11	88
12	240
13	104
14	252
15	360
16	128
17	136

k	n
1	1
2	8
3	24
4	36
5	40
6	72
7	56
8	80
9	108
10	180
11	88
12	240
13	104
14	252
15	360
16	128
17	136

Divisor Equation(2)

The answer is 18.

1 solution

0 pending reports

k	n
1	1
2	8
3	24
4	36
5	40
6	72
7	56
8	80
9	108
10	180
11	88
12	240
13	104
14	252
15	360
16	128
17	136