Find the number of positive integers from 1 to 99999 inclusive that have exactly $3$ proper divisors.

**
Details and assumptions
**

If
$n$
is a positive integer, a
**
proper divisor
**
of
$n$
is an integer
$d$
such that
$1<d<n$
and
$d$
divides
$n$
.

You may choose to read Divisors of an Integer .

The answer is 7.

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

Great explanation for why the number must be of the form $p^ 4$ .

Did exactly the same !

Venkata Karthik Bandaru
- 6 years, 3 months ago

First we must realise that not many numbers have exactly 3 proper divisors. Numbers that have exactly 3 proper divisors must be in the form $a^{4}$ where $a$ is a prime number such that the divisors of the number are $a$ , $a^{2}$ and $a^{3}$ .

$\sqrt[4]{99999} < 18$ so we consult the list of primes and find there are 7 possible values for a (primes less than 18) and therefore 7 integers which have 3 proper divisors.

3 Helpful
0 Interesting
0 Brilliant
0 Confused

In reply to Calvin L.'s comment:

Basically the numbers we seek must have 3+2=5 divisors. Let $n$ be a positive integer and $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ its unique prime factorization, where all the $p_i$ are primes. It is well-known that the number of divisors of $n$ is $d(n)=(e_1+1)(e_2+1)\cdots (e_k+1)$ (this can be proven by a simple counting argument.) We want $(e_1+1)(e_2+1)\cdots (e_k+1)=5$ . But $5$ is prime. Furthermore, all the $e_i$ 's are positive integers, hence we let (WLOG) $(e_1+1)=1$ and $e_2+1)=5$ . This yields $n=p^4$ , where $p$ is prime, as desired.

Arkan Megraoui
- 7 years, 8 months ago

Why are these the only possible cases?

If a was not prime, there would be more divisors? (i.e. not exactly 3)

Jonathan Lowe
- 7 years, 8 months ago

Log in to reply

Yes. We may take 4 for example. Raising it to the 4th gives us 256, with proper factors 2, 4, 8, etc. The number of factors were doubled because 4 has a proper factor 2.

Nash Sarail
- 7 years, 8 months ago

Since proper divisors exclude 1 and n, n must have 5 divisors in total. This means that the number must be written in the form \(p^(4)\.

By trial and error I found that \(17^(4) = 83521\) and $19^(4) = 130321.$ Since (19^(4)\ is too large, the answer must be the number of prime numbers less than 17 (excluding 1.) The answer is 7.

1 Helpful
0 Interesting
0 Brilliant
0 Confused

See divisors article.

for a number, $X$ , with prime factorisation,

$X=p_{1}^{n}p_{2}^{m}p_{3}^{o}....$
number of factors are
$(n+1)(m+1)(o+1)...$
,
**
including
**
1 and X.

Therefore for three
**
proper divisors
**
we require that the product of the prime powers is 5,

$(n+1)(m+1)(o+1)...=5$ . Since five is prime, this is only possible if n=4, rest are 0.

in other words, $X=a^{4}$ , where a is a prime. And $X \le 99999 \implies X\le 17.89...$

Only seven prime numbers less than that, so answer is 7.

1 Helpful
0 Interesting
0 Brilliant
0 Confused

1 Helpful
0 Interesting
0 Brilliant
0 Confused

SORRY, IN THE THIRD LINE I MEANT "Now, since n =< 99999"... Typo, sorry about that...

Andres Fabrega
- 7 years, 8 months ago

0 Helpful
0 Interesting
0 Brilliant
0 Confused

Consider few numbers which have exactly 3 proper divisors such as 16(2, 4 and 8) and 625(5, 25 and 125), Notice that these numbers are perfect squares and their square roots are perfect squares with square roots are prime numbers.

Since we need to find the fourth power of prime numbers, I found the count of prime numbers whose 4th power is less than 99999. This can be done by rounding down the 4th root of 99999 and finding the count of primes less than or equal to this value. This count of primes is the answer to the question.

0 Helpful
0 Interesting
0 Brilliant
0 Confused

they are (2)^4, (3)^4, (5)^4, (7)^4, (11)^4, (13)^4, and (17)^4

0 Helpful
0 Interesting
0 Brilliant
0 Confused

*
$x^{4}$
*
and
*
x
*
must be a prime number. This is because the proper divisors of
*
$x^{4}$
*
are
*
x,
$x^{2}$
and
$x^{3}$
*
which satisfy the above condition. Therefore, the values of
*
x
*
which satisfy the conditions are
*
2,3,5,7,11,13,17
*
which is equal to 7.

0 Helpful
0 Interesting
0 Brilliant
0 Confused

0 Helpful
0 Interesting
0 Brilliant
0 Confused

Why is this the only case?

Log in to reply

because if we take a composite x (lets say x=z \times y) then no of the form x^4 will have more than 3 proper factors as x itself can be split into z \times y.so the factors will be z,y,x,z^2,y^2,x^2 and so on .......till a definite no more than 3.

yash gupta
- 7 years, 8 months ago

Divisors of n is always exist in pairs( for example A and B ), so the number of divisors is even unless it is a square where A=B. If the power of x is a even bigger than 4 ( for example 6), we can split x^3 into small divisor ( x^2 and x^3) and obtain two pairs of divisors. x cannot be a composite according to Yash G.

Đinh Việt Thắng
- 7 years, 8 months ago

×

Problem Loading...

Note Loading...

Set Loading...

Since the number has $3$ proper divisors, it has total $5$ divisors including $1$ and the number itself!

Suppose the number is $m$ ... Consider the prime factorization of $m$ ...

$p_1 ^a \cdot p_2 ^b \cdot p_3 ^c \cdot p_4 ^d \cdot p_5 ^e \cdot \cdot \cdot \cdot \cdot$

By divisor theorem, we know that, the number of divisors of $m$ is...

$(a+1)(b+1)(c+1)(d+1)(e+1) \cdot \cdot \cdot \cdot \cdot$

Here, we know that the number of divisors of $m$ is $5$ ...

As $5$ is a prime, it can't be factored further into positive primes...

Hence, the prime factorization of $m$ is of the form $p^a$ with $(a+1)$ divisors...

We have, $a+1=5 \Longrightarrow a = 4$

Finally, we conclude that, $m=p^4$ , where $p$ is a prime...

Here, $1 \le m \le 99999$

Since, $17^4 = 83521 < 99999 < 18^4 = 104976$

The possible solutions are every prime $p \le 17$ ... There are exactly $7$ such primes ( $2,3,5,7,11,13,17)$ ...

Therefore, the required answer is $\fbox{7}$ !