# Smallest number with given number of factors

• Apr 26th 2012, 11:26 AM
Tzarian
Find Smallest Number For Number of Factors
I would like to know how you would fine the smallest ordinary number with exactly a certain number of factors given, for example:

The number of factors is 6
The smallest number with 6 factors is 12
12 =
• 1 * 12
• 2 * 6
• 3 * 4

So the question is really:
The number of factors is n
The smallest number with n factors is X
How do you find X?

Please feel free to use an example because I think doing it all in algebra will be unreasonably difficult
• Apr 26th 2012, 12:05 PM
ignite
Re: Smallest number with given number of factors
Let N be any natural number and \$\displaystyle N={p_1}^{a_1}{p_2}^{a_2}...{p_n}^{a_n}\$ , where \$\displaystyle p_1,p_2,...,p_n\$ are prime numbers and \$\displaystyle a_1,a_2,a_n\$ are natural numbers.
Then number of factors of N is given by \$\displaystyle (a_1+1)(a_2+1)...(a_n+1)\$

You are given number of factors say k.First step would be to factorize k.That is write k as \$\displaystyle (a_1+1)(a_2+1)...(a_n+1)\$.
Once you have found out \$\displaystyle a_1,a_2,..,a_n\$ such that \$\displaystyle a_1 \ge a_2 ...\ge a_n \$ , your x would be \$\displaystyle 2^{a_1} 3^{a_2} 5^{a_3} .... \$

Main thing here is that you can multiple possibilities for \$\displaystyle a_i 's \$ and you have to optimize for that.

Example:Given k=12,find x.
k=3*2*2 . Corresponding x = \$\displaystyle 2^{(3-1)} 3^{(2-1)} 5^{(2-1)} \$=60
k=6*2 . Corresponding x = \$\displaystyle 2^{(6-1)} 3^{(2-1)} \$ = 96
k=4*3 . Corresponding x = \$\displaystyle 2^{(4-1)} 3^{(3-1)} \$ = 72
So minimum x would be 60.