Re: smallest positive integer that has exactly k divisors

On Oct 24, 2:43 am, 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?

It doesn't, it has 6 UNIQUE divisors.

(6 is not a power of 2.)

No, but 8 is:

000 12 2 * 2 * 3
001 4 2 * 2 * 1
010 6 2 * 1 * 3
011 2 2 * 1 * 1
100 6 1 * 2 * 3
101 2 1 * 2 * 1
110 3 1 * 1 * 3
111 1 1 * 1 * 1

Note, 6 appears twice as does 2, that's why there's 6.


This is true, _if_ N is square-free

No, square-free just means the UNIQUE divisors will be the same
as 2**factors, but there will always be 2**factors divisors.
It's like rolling dice, there are 36 possible outcomes, but
only 11 unique sums. And you DO know that you have to count
the duplicates when calculating probability?

(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.

That looks like too much work. How hard is it to consolidate
the duplicates?

import gmpy
factors = [2,2,2,2,5,5,5]
unique_divisors = set([])
for i in xrange(2**len(factors)):
divisor_pattern = gmpy.digits(i,2).zfill(len(factors)) # binary
number
product = 1
# print divisor_pattern,
divisor_factors = []
for f,g in enumerate(divisor_pattern):
if g == '0': # factor present
product *= factors[f]
divisor_factors.append('%2s' % (factors[f]))
else: # 1 if factor not present
divisor_factors.append(' 1')
# print '%6d %s' % (product,' * '.join(divisor_factors))

if not (product in unique_divisors):
unique_divisors.add(product)

print
print unique_divisors

## set([400, 2, 100, 25, 16, 1, 200, 80, 10, 2000, 1000, 50,
## 500, 8, 40, 20, 250, 125, 4, 5])


Not hard at all.


--- Christopher Heckman

.

Relevant Pages