3 proper 5

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

Details and assumptions

If n n is a positive integer, a proper divisor of n n is an integer d d such that 1 < d < n 1<d<n and d d divides n 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.

10 solutions

Abrar Nihar
Sep 16, 2013

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

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

p 1 a p 2 b p 3 c p 4 d p 5 e 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 m is...

( a + 1 ) ( b + 1 ) ( c + 1 ) ( d + 1 ) ( e + 1 ) (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 m is 5 5 ...

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

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

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

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

Here, 1 m 99999 1 \le m \le 99999

Since, 1 7 4 = 83521 < 99999 < 1 8 4 = 104976 17^4 = 83521 < 99999 < 18^4 = 104976

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

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

Moderator note:

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

Did exactly the same !

Venkata Karthik Bandaru - 6 years, 3 months ago
Jonathan Lowe
Sep 16, 2013

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 a^{4} where a a is a prime number such that the divisors of the number are a a , a 2 a^{2} and a 3 a^{3} .

99999 4 < 18 \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.

In reply to Calvin L.'s comment:

Basically the numbers we seek must have 3+2=5 divisors. Let n n be a positive integer and n = p 1 e 1 p 2 e 2 p k e k n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} its unique prime factorization, where all the p i p_i are primes. It is well-known that the number of divisors of n n is d ( n ) = ( e 1 + 1 ) ( e 2 + 1 ) ( e k + 1 ) 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 ) ( e k + 1 ) = 5 (e_1+1)(e_2+1)\cdots (e_k+1)=5 . But 5 5 is prime. Furthermore, all the e i e_i 's are positive integers, hence we let (WLOG) ( e 1 + 1 ) = 1 (e_1+1)=1 and e 2 + 1 ) = 5 e_2+1)=5 . This yields n = p 4 n=p^4 , where p p is prime, as desired.

Arkan Megraoui - 7 years, 8 months ago

Why are these the only possible cases?

Calvin Lin Staff - 7 years, 8 months ago

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
Eva Donlon
Sep 19, 2013

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 1 9 ( 4 ) = 130321. 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.

Ben Williams
Sep 19, 2013

See divisors article.

for a number, X X , with prime factorisation,

X = p 1 n p 2 m p 3 o . . . . X=p_{1}^{n}p_{2}^{m}p_{3}^{o}.... number of factors are ( n + 1 ) ( m + 1 ) ( o + 1 ) . . . (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 (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 X=a^{4} , where a is a prime. And X 99999 X 17.89... X \le 99999 \implies X\le 17.89...

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

Andres Fabrega
Sep 16, 2013

If the number has 3 proper divisors, it will have 5 total divisors (the 3 proper + n + 1). Therefore, using tau´s formula for number of divisors, we know the number is of the form n = D^4, for any prime D. Now, since n =< 99999, and the 4th root of 99999 is 17.(decimals), we know D =< 17. Therefore, since there are 7 primes until 17, the answer is 7.

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

Andres Fabrega - 7 years, 8 months ago
Nash Sarail
Sep 18, 2013

Three proper divisors + 1 + itself = 5 divisors. By analyzing, we find that prime numbers raised to 4 has three proper divisors: the square root, the square root of the square root, and the product of the square root and the 4th root. Raising 17 to the 4th gives a number higher than 99999, so we only have 7 prime numbers before 17.

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.

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

Why are these the only possible values? Did you check all 99999 numbers?

Calvin Lin Staff - 7 years, 8 months ago
Wee Hau Chin
Sep 15, 2013

In order to have 3 proper divisors, the number should be able to be presented in the form of x 4 x^{4} and x must be a prime number. This is because the proper divisors of x 4 x^{4} are x, x 2 x^{2} and x 3 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.

Why are these the only possible cases? Why must x x be a prime number?

Calvin Lin Staff - 7 years, 8 months ago

The only case in which n have exactly 3 proper divisors is when n=x^4 x is a primitive number. The three divisors of n is x, x2 and x^3. Besides that, 1<n<99999; so we have 1<x<18 Thus x can be one of seven value: 2,3,5,7,11,13,17

Why is this the only case?

Calvin Lin Staff - 7 years, 8 months ago

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

Log in to reply

sorry in the 4th line i wrote "no'.

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

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...