Re: Divisors
- To: mathgroup at smc.vnet.net
- Subject: [mg24355] Re: [mg24272] Divisors
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Sun, 9 Jul 2000 04:52:58 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
on 00.7.8 2:18 PM, Hans Havermann at hahaj at home.com wrote:
> What I actually need to complete the sequences is *not* the entire list of
> divisors for these repunits, but only (if it has 2k divisors) the k-th
> divisor of the *sorted* divisor list. I don't know if it is possible to
> generate this central divisor without first sorting the list of *all*
> divisors.
>
> Therein lies the rub. :)
I am not quite sure if I understand you correctly but If I do than the
answer seems to be yes. Suppose you have a sorted list of primes
{p1,p2,p3,p4,....,pn} (possibly with repetitions) and you would like to find
the k-th divisor of p1*p2*...*pn. You do not need to construct a list of all
divisors. Instead you can proceed as follows. We start with two lists,
primes and div, whose initial values are primes={p1,p2,p3,...} and div={}.
Next:it is easy to find the smallest three divisors, they must be 1,p1,p2
so we set div={1,p1,p2}. Next we compare p1*p2 and p3. We add the smaller
of these to div, which now has elements div={1,p1,p2,d1}, where d1 is either
p1*p2 or p3. Set primes to Complement[primes,div]. We again have to compare
the smallest product of two elements in div (which is not itself in div)
with the first element of primes and then modify both lists as before. We
then continue until we have k elements in div. I haven't tried computing the
running time but this surely is faster than making a list of all possible
divisors and sorting it. Also, it looks a pretty easy job to write an
Mathematica program that does this.
Andrzej
--
Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/
http://sigma.tuins.ac.jp/