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 .
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 !
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 .
4 9 9 9 9 9 < 1 8 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 be a positive integer and n = p 1 e 1 p 2 e 2 ⋯ 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 ) ⋯ ( e k + 1 ) (this can be proven by a simple counting argument.) We want ( e 1 + 1 ) ( e 2 + 1 ) ⋯ ( 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.
Why are these the only possible cases?
If a was not prime, there would be more divisors? (i.e. not exactly 3)
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.
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 ) = 1 3 0 3 2 1 . Since (19^(4)\ is too large, the answer must be the number of prime numbers less than 17 (excluding 1.) The answer is 7.
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 ≤ 9 9 9 9 9 ⟹ X ≤ 1 7 . 8 9 . . .
Only seven prime numbers less than that, so answer is 7.
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...
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
In order to have 3 proper divisors, the number should be able to be presented in the form of 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.
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?
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.
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.
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 ⋅ p 2 b ⋅ p 3 c ⋅ p 4 d ⋅ p 5 e ⋅ ⋅ ⋅ ⋅ ⋅
By divisor theorem, we know that, the number of divisors of m is...
( a + 1 ) ( b + 1 ) ( c + 1 ) ( d + 1 ) ( e + 1 ) ⋅ ⋅ ⋅ ⋅ ⋅
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 ⟹ a = 4
Finally, we conclude that, m = p 4 , where p is a prime...
Here, 1 ≤ m ≤ 9 9 9 9 9
Since, 1 7 4 = 8 3 5 2 1 < 9 9 9 9 9 < 1 8 4 = 1 0 4 9 7 6
The possible solutions are every prime p ≤ 1 7 ... There are exactly 7 such primes ( 2 , 3 , 5 , 7 , 1 1 , 1 3 , 1 7 ) ...
Therefore, the required answer is 7 !