# Talk:Sequence: smallest number with exactly n divisors

## The Combinatronics

A loop factorizing integers to find the number of divisors is a lame way to implement this task!

If I use only 1 prime then it should be 2 and S(n) = 2**(n-1). I shall conject that if n is prime then S(n) is 2**(n-1) no matter how many primes I use, we shall see why later.

Let me consider the case where I use 2 primes. In general they form integers of the form (P1**A1)*(P2**A2), for a minimal P1 should be 2 and P2 should be 3 with A1 greater than or equal A2. 2*3*5=30 so any values I can find less than or equal 30 with 2 primes is minimal. The number of factors of such an integer will be 1+A1+A2+A1*A2. Anything larger than 2**5 is greater than 30 so I construct a table:

A1 A2 factors value 1 1 4 6 2 1 6 12 2 2 9 36 3 1 8 24 3 2 12 72 3 3 16 216 4 1 10 48 4 2 15 144 4 3 20 432 4 4 25 1296

By examination I can now produce S(1)..S(8). S(9) may be 36, S(10) may be 48 and(S12) may be 72, but being greater than 30 there may be a smaller value with 3 primes.

For 3 primes the number of factors is 1+A1+A2+A3+A1*A2+A1*A3+A2*A3+A1*A2*A3 and are good upto 2*3*5*7 (210). 2*3*5 has 8 factors but can not be better than 24. 2**2*3*5=60 and has 12 factors, so it replaces the existing guess (72). This also validates my current guess for 9 and 10. So I can now generate S(1)..S(13).

Realizing that the formula for the number of factors for n primes is (1+A1)*(1+A2)...(1+An) I can see why there is no value better than S(n)=2**(n-1) for prime n. I can also calculate S(14):

14=(1+6)*(1+1)->2**6*3->192.--Nigel Galloway (talk) 12:37, 13 April 2019 (UTC)