What is the efficient way to find the smallest integer with given or more number of divisors? What i naively think is that find the number of divisors of the numbers starting from 2. Sure this is not the best way. Is there a way of guessing the starting point close to the answer? May be some relation between n and the number of divisors it can have.
Asked
Active
Viewed 393 times
1
-
Do the divisors have to be unique? ie does 4 have 1 or 2 divisors (2 and 2), excluding 1 and 4 of course – Russ Jul 28 '12 at 16:27
-
http://www.math.hawaii.edu/~ron/pdfpapers/ordinarytest.pdf – Petar Minchev Jul 28 '12 at 16:48
-
Duplicate - http://stackoverflow.com/questions/8861994/algorithm-for-finding-smallest-number-with-given-number-of-factors – Petar Minchev Jul 28 '12 at 16:51
-
@Russ : yes they have to be unique – jairaj Jul 28 '12 at 16:51
2 Answers
3
If the prime decomposition of a number n is:
n = p1^a * p2^b * p3^c then the number of divisors is (a + 1) * (b + 1) * (c + 1).
This is a hint for the solution.
The problem is not so simple as it seems.
I found interesting theorems and papers solving the problem:
Petar Minchev
- 46,889
- 11
- 103
- 119
-
Good hint for the solution, but think about it. 30=2*3*5 has 8 divisors, by your formula you would get 2^7=128 as the smallest number. – Karoly Horvath Jul 28 '12 at 16:32
-
@Karoly Horvath - I found interesting theorems and papers. I pasted them as comments to the question. – Petar Minchev Jul 28 '12 at 16:50
-
@Karoly Horvath: nope, Petar Minchevs result is correct. 30=2*3*5 (recall that a,b and c are 1 in this case) and the formula comes to (1+1)*(1+1)*(1+1). It is a simple application of the fundamental theorem of arithmetic. – carlosdc Jul 28 '12 at 17:07
-
@carlosdc - Thanks for the support, but I am wrong. For n = 8, I will give 2^(8 - 1) = 128, but Karoly's suggestion 2 * 3 * 5 has again (1 + 1) * (1 + 1) * (1 + 1) = 2 * 2 * 2 = 8 divisors. Which is better than mine. – Petar Minchev Jul 28 '12 at 17:13
-
@Petar Minchev, I thought you were just proposing how to count the divisors, I didn't realize that was your algorithm for the whole problem. – carlosdc Jul 28 '12 at 17:17
-
@carlosdc - Well at first I thought it will work for the whole problem. Now I wrote it just as a hint(it is a part of the solution) and put links to the theorems and solutions. – Petar Minchev Jul 28 '12 at 17:28
0
Have you thought of using an adaptation of the Sieve of Eratosthenes to do this? Go through possible divisors in turn, and add 1 to an accumulated total at the appropriate point. For instance, when you reach 5, add 1 to the totals for 5, 10, 15 ... It would not take a great modification of the code to do that.
rossum
- 15,344
- 1
- 24
- 38