Question

Minimizing number for number of divisors. Ideas?

Answer 1

Let's say sigma is the divisor counting function: \[\Large \sigma ( 12)=6\] since 12 has divisors of 1, 2, 3, 4, 6, and 12, that's all six of them. If we have a number's prime factorization, then the formula is simple, we just add one to each of the exponents and multiply them: \[\Large \sigma(2^23^1)=(2+1)(1+1)=3*2=6\] So then now let's get interesting with this...

Answer 2

There are two extreme cases to consider I believe, that is when we are looking at only powers of a single prime (for this problem, the smallest prime number seems the most reasonable) and the primorial. \[\Large \sigma(p^n) = n+1 \\ \Large \sigma(p_k \#) = (1+1)^k=2^k\] A refresher on primorial is that is like a factorial, but multiplies up to the kth prime. We can combine these two however...

Answer 3

\[\Large \sigma((p_k \#)^n)=(n+1)^k\] And recognize that for any number of divisors, \[\Large n*k=constant=C\] I believe. So can we minimize (n+1)^k with the constraint n*k=C?

Answer 4

Plugging in one to the other I noticed this nice and familiar looking expression to e: \[\Large (1+\frac{C}{k})^k \] And playing with lagrange multipliers I really didn't get anywhere but I kind of got lost and I'm not entirely sure what all can and can't work. I'm really at this point looking for an approximate answer and here's what I have so far, any ideas?

Answer 5

Really I'm just looking for a way to discern if a number is the minimum possible value for the number of divisors it has. So a concrete example of this would be to say that 12 minimizes number of factors for 4 divisors since it's better number than 18 or 32 which also have 6 divisors.

Answer 6

I don't know if my reasoning was good earlier, so don't try to read too hard into it if you think it's wrong it's probably wrong lol.

Answer 7

Actually I think that constraint might be wrong. It is conserving the number of prime factors if we do that, which is not what we want.

I want to maximize the number of divisors of some number while minimizing its value. Maybe I should say that, since it seems slightly more broad but is the same question, but sort of double ended.

Answer 8

This is a concept known as /highly composite numbers/. In general, 2*3*5...*p is a reasonably good upper bound for these numbers, but it requires a bit of fiddling to get the exact number.

e.g. say we want the lowest number with 16 divisors.

We know that 2 * 3 * 5 * 7 has 2^4 divisors. But can we do better? If there is a lower number, it must not contain 7, so remove that. We now have (1 + 1)(1+1)(1+1) divisors. to get back to 16, we must increase one of our current powers by 2, to 3.

2^3 * 3 * 5 has 16 divisors, but is it less? Yes, it is, because 2^2 < 7. Can we do any better? A quick check shows that we cannot, as 3^2 > 5.

Answer 9

(In the case of the Project Euler question, we actually want something slightly different from highly composite numbers, but the method you would use to find them is that same: find an upper bound, then swap out primes one by one if you can increase earlier powers and stay above the divisor limit)

Answer 10

What's the project euler question that goes with apparently this concept? haha

Answer 11

The one where you need to find the smallest n where 1/x + 1/y = 1/n has 1000 solutions, because it's based on sigma(n^2)

Although they actually released an even more closely related one recently, as their 500th problem: find the smallest number with 2^(500500) divisors (modulo some other number, because the actual number will have millions of digits)

Answer 12

Oh I see, so we are looking at the same problem haha. I think there is a way to write the general formula though for the highly composite numbers, just for fun.

Answer 13

Sadly, I don't think there is. It relies on comparing the value of each new prime with powers of earlier ones, and the randomness of primes will cause problems.

Answer 14

Sure, it will be a constraint based on the power of the prime exceeding the kth prime sort of thing. It really won't be that much better but kind of just pin down the number of the prime sort of... It won't be incredibly exciting or enlightening probably, but oh well.

Answer 15

Ahhh I found what I was looking for on wikipedia lol http://en.wikipedia.org/wiki/Superior_highly_composite_number#Properties