5
$\begingroup$

How many positive integers from $1-1000$ have $5$ divisors?

Any answers would be greatly appreciated. If you have any questions, I will edit for clarification.

$\endgroup$

closed as off-topic by user296602, Sahiba Arora, Claude Leibovici, user99914, user223391 Jan 6 '18 at 17:27

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Community, Sahiba Arora, Claude Leibovici, Community, Community
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Only perfect squares have an odd number of divisors. Of the perfect squares, what characteristics separates perfect squares with 3 divisors, 5 divisors and more than 5 divisors? $\endgroup$ – Doug M Jan 6 '18 at 0:57
  • 4
    $\begingroup$ Exactly five? Or at least five? $\endgroup$ – JakeRobb Jan 6 '18 at 4:56
  • 3
    $\begingroup$ Ask Python : [n for n in range(1001) if sum(1 for d in range(1, n+1) if n % d == 0) == 5]. It returns [16, 81, 625]. $\endgroup$ – Eric Duminil Jan 6 '18 at 10:05
18
$\begingroup$

(Filling in some details, on the off chance that other answers are unfamiliar to potential readers!)

Consider the prime factorization of $75 = 3^1 \cdot 5^2$. How many factors does $75$ have? Well, in forming a factor of $75$, we have to choose how many $3$s to include - there is one available, but we could also choose none; so, the number of choices is $1+1=2$ - and how many $5$s to include - there are two available, but we could also choose none; so, the number of choices is $2+1=3$. The aforementioned $2$ choices and $3$ choices yield $2 \cdot 3 = 6$ combinations using the prime factors, and these are all the factors of $75$:

$$3^0 \cdot 5^0, 3^0 \cdot 5^1, 3^0 \cdot 5^2, 3^1 \cdot 5^0, 3^1 \cdot 5^1, 3^1 \cdot 5^2$$

More generally, a number with prime factorization $p^a \cdot q^b$ for distinct primes $p$ and $q$ has $(a+1)(b+1)$ factors, since you can form these factors by making one of $a+1$ choices for how many $p$s to include (ranging from $0$ to all $a$) and one of $b+1$ choices for how many $q$s to include (ranging from $0$ to all $b$). Even more generally, you arrive at the formula in Bernard's answer.

So: In one's investigation of $5$, it becomes clear that this can arise as the number of factors if, and only if, it came from a number of the form $p^4$ for a prime $p$. All that remains now is to observe how many primes to the fourth power are present between $1$ and $1000$; this is precisely what is done in Mohammad Riazi-Kermani's answer: just $2^4 = 16$, $3^4 = 81$, and $5^4 = 625$. Already we have $6^4 = 1296 > 1000$, so the three listed numbers are exhaustive.

As a follow up exercise, you may wish to count how many factors $4^4$ and $6^4$ have.

(Which would you guess has more? Etc.)

$\endgroup$
23
$\begingroup$

Hint:

If an integer $n$ has a decomposition as a product of distinct prime powers: $$n=\prod_{i=1}^r p_i^{\alpha_i},$$ the number of divisors of $n$ equal to $\:\displaystyle\prod_{i=1}^r(\alpha_i+1)$.

If this product is equal to $5$, what can you conclude?

$\endgroup$
11
$\begingroup$

The only way that a number has exactly $5$ positive divisors is for the number to be a fourth power of a prime number. Thus the answer is 3. The numbers are $$ 2^4,3^4,5^4$$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.