Have I found all the numbers less than 50,000 with exactly 11 divisors?

Question

The math problem I am trying to solve is to find all positive integers that meet these two conditions:

• have exactly 11 divisors
• are less than 50,000

My starting point is a number with exactly 11 divisors is of the form:

$c_1p_1 * c_2p_2 * c_3p_3 * ... * c_{11}p_{11}$

where: $c_i$ is an integer and $p_i$ is prime

and noting that 1 can be a divisor but can only be included once in the list of divisors.

Therefore the smallest such number is: $1*2^{10} = 1024$

The next such number would be: $2^{11} = 2048$

So far $c_i$ has been 1, but I will now start letting some of them be 2 until I reach the upper bound of 50,000. This gives me:

$2^{12}$, $2^{13}$, $2^{14}$ and $2^{15}$ (as $2^{16} > 50,000)$

I feel like I'm onto a useful pattern. So I will start using 3s as well (again until I reach the upper bound):

$3*2^{10}$, $3^2*2^9$, $3^3*2^8$, $3^4*2^7$, $3^5*2^6$, $3^6*2^5$, $3^7*2^4$

Now 4s: $4*2^{10}$, $4^2*2^9$, $4^3*2^8$, $4^4*2^7$

Then 5s: $5*2^{10}$, $5^2*2^9$, $5^3*2^8$

Then 6s: $6*2^{10}$, $6^2*2^9$

Then 7s: $7*2^{10}$, $7^2*2^9$

Then 8s: $8*2^{10}$, $8^2*2^9$

Then 9s: $9*2^{10}$, $9^2*2^9$

Then 10s: $10*2^{10}$

I've now reached the point where there's only one number in the sub-sequence. Therefore, I also have:

$11*2^{10}, 12*2^{10}, 13*2^{10}, ..., 48*2^{10}$

I now feel I've exhausted my algorithm. However I'm not sure if my answer is correct and complete. So, have I enumerated all such numbers? Or have I missed some or doubled-up?

Answer 1

If you're looking at a number with prime factorization $$ p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n} $$ (note, there are no $c$s in a prime factorization), then it has exactly $(a_1+1)\cdot(a_2+1)\cdots(a_n+1)$ divisors.

Since $11$ is prime, the only way it can be written as such a product is just $(10+1)$. So you're looking for numbers of the form $p^{10}$ -- and only that form -- less than $50,000$.

Answer 2

If $n$ has a prime factorization of $p_1^ip_2^jp_3^k$, it has $(i+1)(j+1)(k+1)$ divisors. The numbers with exactly 11 divisors are of the form $p^{10}$ since 11 is prime.

Since $3^{10} > 50,000$, the only answer is $1024$.

Answer 3

Your approach doesn't really make sense to me, especially the starting point: Without knowing the form of the $c_i$, how can you assert that your number has $11$ divisors? It actually can't: A number divisible by $11$ distinct primes has $2^{10} = 1024$ distinct divisors.

---

An approach: Factor $N = p_1^{\alpha_1} ... p_k^{\alpha_k}$ with $p_i$ prime and $\alpha_i$ integers that are at least $1$. The number of divisors of $N$ is then $$(\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1)$$

In particular, as soon as there are two such terms, this is composite - and not $11$. What can you conclude?

The number is $p^{10}$ for a prime $p < \sqrt[10]{50000} < 3$.

Answer 4

To flog a horse consider how many factors $p^k $ have. The factors are:

$1,p,p^2,p^3,.......,p^k$

That's $k+1$ factors.

How many factors does $p^kq^m$ have?

$1,p^2,p^3,......,p^k$

$q,qp,qp^2,qp^3,......,qp^k $

$q^2,q^2p,q^2p^2,q^2p^3......,q^2p^k$

......

......

$q^m,q^mp,q^mp^2,q^mp^3.....,q^mp^k$

That is $(k+1)(m+1)$ total factors.

Now how many factors does $\prod p_i^{k_i} $ have?

Well, each $p_i$ prime has factors for every power from 0 to $k_i $. That's $k_i +1$ factors. The each of those factors can be multiplied by the powers of any other {1,$p_j,p_j^2,...p_j^{k_j} $. The total number of combinations is therefore. $\prod (k_i +1) $.

So if $c = \prod p_i^{k_i} $ then $c $ has $\prod (k_i+1) =11$ factors. as 11 is prime, 11 = $k+1$ so $c=p^{10}$ for some prime $p $.

The only such number in range is $c=2^{10}=1024$ that has 11 factors: 1,2, 4 ,8,16,32,64,128,256,512,1024.