Re: smallest positive integer that has exactly k divisors

On 24 Okt., 09:43, Proginoskes <CCHeck...@xxxxxxxxx> wrote:
On Oct 23, 11:11 pm, "mensana...@xxxxxxxxxxx" <mensana...@xxxxxxx>
wrote:



On Oct 24, 12:20?am, mukesh tiwari <mukeshtiwari.ii...@xxxxxxxxx>
wrote:

Hello everybody . i have to find the smallest positive integer that
has exactly k divisors. for example if k=6 then 12 is the minimum
number which have 6 divisors.One brute force approach i came across
is find the prime factorization and calculate the divisors until
divisors are equal to the k but this one is taking to much time even
for 2000 factors .

## On Oct 24, 12:20 am, mukesh tiwari <mukeshtiwari.ii...@xxxxxxxxx>
wrote:
## > Hello everybody . i have to find the smallest positive integer
that
## > has exactly k divisors. for example if k=6 then 12 is the
minimum
## > number which have 6 divisors.
## > One brute force approach i came across
## > is find the prime factorization and calculate the divisors
until
## > divisors are equal to the k but this one is taking to much time
even
## > for 2000 factors .
##
## Did you really mean 2000 factors? You do know that the
## number of divisors is 2**factors, don't you?

Really? Then how can 12 have 6 divisors? (6 is not a power of 2.)

This is true, _if_ N is square-free (i.e., when 1 is the only perfect
square which divides into N with no remainder).

***

To do this algorithmically, you would need to look at all possible
factorizations of 2000, and given such a factorization

a(1) * a(2) * ... * a(k),

where a(1) >= a(2) >= ... >= a(k), you look at the number

2^[a(1)-1] * 3^[a(2)-1] * ... * p(k)^[a(k)-1],

where p(k) is the kth prime. This is the smallest number of the form

q(1)^[a(1)-1] * q(2)^[a(2)-1] * ... * q(k)^[a(k)-1],

where q(1), q(2), ..., q(k) are distinct primes. (I think.) Then you
would take the minimum of all of these numbers. There might be a
faster way, though, which I can't think of, right at the moment.

--- Christopher Heckman

Thus,
2000
= 2000
= 1000*2
= 500*4
= 500*2*2
= 400*5
= 200*10
= 200*5*2
= 125*16
= 125*8*2
= 125*4*4
= 125*4*2*2
= 125*2*2*2*2
= 100*20
= 100*10*2
= 100*5*4
= 100*5*2*2
= ...

There's a lot to test this way.

Can we add more constraints?
Well, we can predict that
2^(a*b-1) * 3^(c-1) is less/greater than 2^(a-1) * 3^(b*c-1)
as soon as 2^a less/greater 3^c, similar for other consecutive primes.

Thus we may throw away any factoritations
2000 = a(1) * a(2) * ... * a(k)
where some a(i) has a proper divisor d <= a(i-1) or more precisely
where p(i-1)^a(i-1) > p(i)^d
as well as those where some a(i) has a proper divisor d such that
p(i)^d > p(i+1)^a(i+1).
The first condition together with a(i)>=a(i+1) implies that
all a(i) except possibly a(1) are prime.

In the special case of N=2000, we know thus that a(2) is 5 or 2 or 1.
1) If a(2)=1, a(1) must not have a proper divisor>=2.
But in this case a(1)=2000 -- impossible.
We note that in general, the final result will not be a power of 2
unless N is prime (or N=1).
2) If a(2)=2, a(1) must not have a proper divisor >=4 (2^4 > 3^2).
But since all a(i)<=2 for i>=2, the factors 5 must all occur
in a(1) -- impossible.
3) Remains: a(2)=5, a(1) must not have a proper divisor >=8 (2^8 >
3^5).
Especially, a(1) is either 5 or 8, leaving the following
candidate factorizations of 2000:

5*5*5*2*2*2*2
8*5*5*5*2

Now we only need to take the smaller of

2^4 * 3^4 * 5^4 * 7 * 11 * 13 * 17
and
2^7 * 3^4 * 5^4 * 7^4 * 11

hagman



are thus restricted to testing
2000
1000*2
500*2*2
400*5
250*2*2*2
200*5*2

that a(1) >= a(2) >= 2, thus

.

Relevant Pages