Integers with 15 Divisors

Let $n = \prod_{i=1}^k p_i ^{\alpha_i}$ , where $p_i$ are all its' prime divisors for every $i=1,2,\ldots,k$ . Let $d(n)$ define as the number of divisor(s) of $n$ . So, all of its' divisors must be in the form $\prod_{i=1}^{k} p^{\beta_{i}}_{i}$ , where $0 \leq \beta_{i} \leq \alpha_{i}$ . Notice that there are $(\alpha_i + 1)$ possible values of $\beta_{i}$ , those are $0,1,2,\ldots,\alpha_{i}$ . So, $d(n)$ is equal to the multiplication of $(\alpha_{i}+1)$ or $d(n) = \prod_{i=1}^{k} (\alpha_{i}+1)$ where $\alpha_i$ is an integer so that $n$ is divided by $p^{\alpha_i}_{i}$ but $n$ isn't divided by $p^{\alpha_i+1}_{i}$ .

Back to the question, 15 can be expressed as $1 \times 15$ or $3 \times 5$ . So, the numbers that have 15 divisors must be in $p^{14}$ or $p^2 \cdot q^4$ .

First $p^{14} \leq 19999 \iff p \leq 2$ , so $p=2$ is the only solution.

Second $p^2.q^4 \leq 19999 \iff p.q^2 \leq 141$ , there are 18 solutions. Those are $(p,q) = (3,2),(5,2),(7,2),(11,2),(13,2),(17,2),(19,2),(23,2)$ , $(29,2),(31,2),(2,3),(5,3),(7,3),(11,3),(13,3),(2,5),(3,5),(2,7)$ .

So, totally, there are 19 numbers $\leq 19999$ that have exactly 15 divisors.

Let the prime factorization of a number be $p_1^{e_1}p_2^{e_2}...p_n^{e_n}$ . Then, all divisors of the number are of the form

$p_1^{a_1}p_2^{a_2}...p_n^{a_n}$ , where $0 \leq a_i \leq e_i$ .

Note that each $a_1, a_2, ..., a_n$ corresponds to exactly one divisor. Therefore, there are

$(e_1+1)(e_2+1)...(e_n+1)$ total divisors of the number.

A number with 15 divisors can thus be expressed in one of the 2 forms:

$p_1^14, p_1^4p_2^2$ .

In the first case, note that $2^{14}<19999$ but $3^{14}>19999$ . Therefore, there is 1 solution in this case.

In the second case, we subdivide into cases based on $p_1$ .

If $p_1=2$ , then $p_2^2<\frac{19999}{16} \implies p_2<35.36$ , which has the 10 solutions $p_2=3,5,7,11,13,17,19,23,29,31$ .

Similarly, there are 5, 2, and 1 solutions respectively for $p_1=3,5,7$ . This gives a total of $1+10+5+2+1=19$ solutions.

15 divisors = p^14 or p^2*q^4

p^14 form -> 2^14... p^2*q^4 form -> 2^2(3^4,5^4 and 7^4) 3^2(2^4 and 5^4) 5^2(2^4 and 3^4) 7^2(2^4 and 3^4) 11^2(2^4 and 3^4) 13^2(2^4 and 3^4) 17^2(2^4) 19^2(2^4) 23^2(2^4) 29^2(2^4) 31^2(2^4)

total = 19 numbers

In order for a number to have 15 factors, it must be of the form p^14 or p^4 times q^2 where p and q are distinct prime numbers. If the number is of the form p^14 then only p=2 works. If the number is of the form p^4 times q^2 we consider cases. If p=2, then q=3, 5, 7, 11, 13, 17, 19, 23, 29, and 31 work for a total of 10 numbers. If p=3, then q=2, 5, 7, 11, 13 work for 5 more numbers. If p=5, then q= 2 and 3 work. And if p=7 the p=2 works. Lastly, if p>10, then q<2 and so it is impossible. So there are 1+10+5+2+1=19 numbers that work.

One should be familiar with the concept that a number, say n, when prime factorized , i.e. n= p^a. q^b .r^c .... where p, q,r are different prime numbers, has, (a+1)(b+1)(c+1)... number of different divisors. Now, we have 15 as the number of divisors 15= 1 3 5 = 15*1 On comparison, 1=a+1 , 3=b+1 , 5=c+1 =>a=0,b=2,c=4 or 15=a+1 , 1=b+1 => a=14,b=0

Second case is fairly simple, among all the primes with power raised to 14, only 2^14 lies in the interval [1,19999] Hence 2^14 is one integer.

For the first case, we have our integer in the form of p^2 . q^4 , where p and q are our prime numbers p>=2 , hence p^2 >=4

Now, 19999/4 <5000, hence q^4 has to lie between [1,4999] . Only 2,3,5 and 7 fulfill this criteria.

For q=2, q^4=16 19999/16 >1250 hence p^2 lies in [1,1249] , not that p is not equal to 2 since q=2 . Easy inspection would show us p can be 3,5,7,11,13,17,19,23,29 or 31 i.e. 10 different values hence we have 10 different integers with q=2.

For q=3, q^4 = 81 19999/81< 247 Hence p^2 lies in the interval [1,246] Here also , p is not equal to 3 since q=3 Possible values of p are 2,5,7,11,13 i.e.5 values

For q=5, q^4 = 625 19999/625 < 32 hence p^2 lies in [1,31] hence p can take values 2 and 3 only (not 5 as q=5)

Lastly, q=7, q^4 = 2401 19999/2401 <9 p^2 lies in [1,8] i.e. p = 2 only So total number of numbers we we looking for are : 1 + 10 + 5 + 2 +1 = 19

We know that the number of divisors of any integer with prime factorization p^a * q^b...z^n = (a+1)(b+1)........(n+1)

So let p and q be primes , then

15 divisors = p^14 or p^2*q^4

p^14 form -> 2^14.. [1] p^2*q^4 form -> 2^2(3^4,5^4 and 7^4) [3] 3^2(2^4 and 5^4) [2] 5^2(2^4 and 3^4) [2] 7^2(2^4 and 3^4) [2] 11^2(2^4 and 3^4) [2] 13^2(2^4 and 3^4) [2] 17^2(2^4) [1] 19^2(2^4) [1] 23^2(2^4) [1] 29^2(2^4) [1] 31^2(2^4) [1]

total = 19 numbers

Let $\prod_{i=1}^k p_i^{a_i}$ be the prime factorization of $n$ with $p1<p2 \cdots < p_k$ . Then $n$ has $\prod_{i=1}^k (a_i+1)$ divisors. In this question we need to have $15$ divisors which can be $3*5 , 5*3$ or just $15$

*Case $3*5$ * : We have $k = 2, a_1 = 2, a_2 = 4$ and since $p_1^6 < p_1^2 p_2^4 = n \leq 19999$ , we must have $p_1 \leq 5$ .

For $p_1 = 2$ , we must have $p_2^4 \leq 19999/4 \Rightarrow p_2 \leq 7$ , $3$ solutions.

For $p_1 = 3$ , we must have $p_2^4 \leq 19999/9 \Rightarrow p_2 \leq 5$ , $1$ solutions.

For $p_1 = 5$ , we must have $p_2^4 \leq 19999/25 \Rightarrow p_2 \leq 5$ , $0$ solutions.

Total of 4 solutions.

Case $5*3$ : We have $k = 2, a_1 = 4, a_2 = 2$ , by the same reasoning as above, $p_1 \leq 5$ .

For $p_1 = 2$ , we must have $p_2^2 \leq 19999/16 \Rightarrow p_2 \leq 31$ , $10$ solutions.

For $p_1 = 3$ , we must have $p_2^2 \leq 19999/81 \Rightarrow p_2 \leq 13$ , $4$ solutions.

For $p_1 = 5$ , we must have $p_2^2 \leq 19999/625 \Rightarrow p_2 \leq 5$ , $0$ solutions.

Total of 14 solutions.

Case $15$ : We have $k = 1, a_1 = 14$ , only $p_1 = 2$ works as $3^{14} > 19999$

Total of 1 solutions.

So there is a total of $4+14 +1 = 19$ integers from $1$ to $19999$ that have exactly $15$ divisors.

A number n has the form (a^k) (b^m) ...., the number of divisors in n is (k+1) (m+1) ......

since the number of divisors is 15, (k+1) (m+1) ..... = 15

Looking at this, we first consider the factors of 15. We have 2, 15 and 1 and 3 and 5. Considering the case where k = 14 and m=0 (only two variables since there are only 2 factors) yield only 1 solution: 2^14.

We now consider our second case where our two numbers are 3 and 5. If k=4 and m=2, we get 17 solutions:

(2^4)*(3^2)

(2^4)*(5^2)

(2^4)*(7^2)

(2^4)*(11^2)

(2^4)*(13^2)

(2^4)*(17^2)

(2^4)*(19^2)

(2^4)*(23^2)

(2^4)*(29^2)

(2^4)*(31^2)

(3^4)*(2^2)

(3^4)*(5^2)

(3^4)*(7^2)

(3^4)*(11^2)

(3^4)*(13^2)

(5^4)*(2^2)

(5^4)*(3^2)

This yields a total of 18 numbers. However, we forgot to count 1 stated by the initial condition, which makes our answer 19.

We see that $15 = 1 \times 15 = 3 \times 5$ .

Let $N =p_1^{e_1} \times p_2^{e_2} \times ... \times p_n^{e_n}$ Where $p_i$ denotes the i th prime factor of N.

Number of divisors of N are $d(N) = \prod_{i=1}^{n} (1 + e_i)$

In the given question d(N) = 15 . But $15 = 3 \times 5$ . There is no other way to factorize 15 . Hence the number should contain only two factors, for it's sum of divisprs to be 15 . In the given question it also states that, $N < 20,000$ .

p 1^e 1 \times p 2^e 2 < 20,000; Since the number should contain only 2 factors

Without loss of generality assume, $e_1 < e_2$

$(1 + e_1)(1 + e_2) = 15$

$(1 + e_1)(1 + e_2) = 3 \times 5$

Therefore $e_1 = 2, e_2 = 4$

Now the lets try to find the largest prime factor possible, lets call it L.

Smallest is obviously 2. $L^2 \times 2^4 < 20,000$ .

$L^2 < 20,000/16$

$L < sqrt(20,000/16)$

$L < 35.3$

Since L is also a prime, L = 31.

Hence our set of possible primes are boiled down to $H = \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31\}$

Our question boils down to: Number of pairs i,j such that i and j are distinct and $p_i^4 \times p_j^2 < 20,000, p_i, p_j \in H$

Let's consider each element in H for $p_i$ .

As we know, for 2, every other element is possible. i.e, 10.

For 3, $3^4 \times p_j ^ 2 < 20,000$

$p_j ^ 2 < 247$

$p_j < 16$

Therefore, 2, 5, 7, 11, 13 are possible. i.e. 5.

For 5, $5^4 \times p_j ^ 2 < 20,000$

$p_j ^ 2 < 32$

$p_j < 6$

Therefore, 2, 3, are possible. i.e. 2 solutions.

Similarly for 7, 2 is possible, i.e. 1 solution.

Also $2^{14}$ was not considered earlier, i.e. 1 solution.

Hence a total of 19 solutions.

15 divisors implies it is either in the form a^14 or b^2 c^4 a^14 form -> 2^14... b^2 c^4 form -> 2^2 3^4,2^2 5^4 and 2^2 7^4 3^2 2^4 and 3^2 5^4 5^2 2^4 and 5^2 3^4 7^2 2^4 and 7^2 3^4 11^2 2^4 and 11^2 3^4 13^2 2^4 and 13^2 3^4 17^2 2^4 19^2 2^4 23^2 2^4 29^2 2^4 31^2 2^4 So, 19.

we know every no can be represented in the form of primes.WE have to find no between 1 and 19999 whic have exactly 15 divisors.

now we try to break 15 into it's divisor in every possible way and we divide it into cases and proceed further.[note $5*3 and 5*3*1$ are essentially same in our solution as

No of divisors of $p^a+q^b+r^c+s^d............$ =(a+1) (b+1) (c+1)*(d+1)................. hence when 15=5x3 then a=4 and b=2 (or vice verse) and when $15=5*3*1$ then also a=4 and b=2 (or vice verse) and c =0 c is any other no which does not take value 4 and 2) hence it would not give rise to any new number. as (k^0=1) (also 1 is not a prime!)

case 1 - 15=15x1 then a+1=15 or a=14 .numbers between 1 to 19999 which are of form $p^14$ we see that only p=2 satisfies our case .

case 2- 15=5x3 then a=4 and b=2 and all others (c,d,e....)will be equal to 0. hence the no which we have to find will be satisfying this condition. $2 \leq p^4+q^2 <20000$

now when p=2 then $q<\sqrt{20000/16}$ hence q can have values 3,5,7,..........13 which are 10 .(in counting)(2 is excluded) similarily when p=3 then q can have values 2,5,7,11,13 which are 5 in number. when p=5 then q can have values 2,3 which are 2 in number when p=7 then q can have values 2 which is single!

now p cannot be greater than 7 as 11^4 does not satisfy our condition $2 \leq p^4+q^2 <20000$ hence solutions in this case 2 are in total 18 and in case 1 only 1 solution was possible.

hence total solutions are 19 in number . (SOLVED)

If a number $N$ has prime factorization $N = p_1 ^ {q_1} p_2^{q_2} \ldots p_n^{q_n}$ where $p_i$ are distinct primes and $q_i$ are positive integers, then $N$ has $(q_1+1)(q_2+1) \ldots (q_n+1)$ divisors, each of which have the form $p_1^{a_1} p_2^{a_2} \ldots p_n^{a_n}$ , where $0 \leq a_i \leq q_i \,$ for all values of $i$ . As an example, the number 24 has prime factorization $24 = 2^3 \cdot 3$ , so will have $(3+1)(1+1)=8$ divisors. Each of the divisors $(1, 2, 4, 8, 3, 6, 12, 24)$ have the form $2^a 3^b$ where $a = 0, 1, 2$ or $3$ and $b = 0$ or $1$ .

In order for a number to have exactly 15 divisors, if we consider the prime factorization of $N$ , the above statement tells us that either $N = p_1^{14}$ , which has $(14+1) = 15$ divisors, or $N= p_1^{2} \cdot p_2^{4}$ , which has $(2+1)(4+1) = 15$ divisors. We consider these cases:

Case 1: $N = p_1 ^{14}$ . Since $2^{14} = 16 \times 1024 =16384$ and $3^{14} = 2187^2 > 10^6$ , so there is 1 solution in this case.

Case 2: $N= p_1 ^2 p_2 ^4$ . We proceed to count the solutions by considering the value of $p_2$ .

Case 2a: $p_2 = 2$ . Then $N < 20000$ implies that $p_1 ^2 < \frac {20000}{16} = 1250$ , so $p_1 < \sqrt{1250} <36$ . Since $p_1$ is an integer, $p_1 \leq 35$ . This gives us solutions $p_1 = 3, 5, 7, 11, 13, 17, 19, 23, 29, 31$ , so there are 10 solutions.

Case 2b: $p_2 = 3$ . Then $N < 20000$ implies that $p_1 ^2 < \frac {20000} {81} < 247$ , so $p_1 < \sqrt{247} < 16$ . Since $p_1$ is an integer, $p_1 \leq 15$ . This gives us solutions $p_1 = 2, 5, 7, 11, 13$ , so there are 5 solutions.

Case 2c: $p_2 = 5$ . Then $N < 20000$ implies that $p_1^2 < \frac {20000} {625} = 32$ , so $p_1 < \sqrt{32} < 6$ . Since $p_1$ is an integer, $p_1 \leq 5$ . This gives us solutions $p_1 = 2, 3$ , so there are 2 solutions.

Case 2d: $p_2 = 7$ . Then $N < 20000$ implies that $p_1^2 < \frac {20000} { 2401 } < 9$ , so $p_1 < \sqrt{9} = 3$ . Since $p_1$ is an integer, $p_1 \leq 2$ . This gives us solutions $p_1=2$ , so there is 1 solution.

Case 2e: $p_2 = 11$ . Then $N < 20000$ implies that $p_1 ^2 < \frac {20000}{11^4} < 2$ . Since $p_1$ is an integer, there are no solutions.

We have to check that $p_1^2 p_2 ^4 < 20000$ for all values of $p_1, p_2$ above. This is true because we kept our bounds tights when calculating $p_1^2 < \frac {20000}{p_2^4}$ .

In conclusion, there are $1+10+5+2+1 = 19$ solutions.