Re: Divisors
- To: mathgroup at smc.vnet.net
- Subject: [mg24357] Re: [mg24272] Divisors
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Sun, 9 Jul 2000 04:53:00 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
There is a problem with the algorithm I described earlier. One has to avoid
multiplying elements like d1 by the primes p1 and p2 again as this would
not in general be a divisor. Thus one needs to keep track of the positions
of the primes (since p1, p2 etc. can be equal). So it maybe better to store
the primes in the form {{1},p1},{{2},p2} and divisors (like d1 in my earlier
message) obtained by multiplying {{1},p1} and {{2},p2} in the form
{{1,2},p1*p2}. Two divisors {{i1,i2,i3...},d1}, {{j1,j2,...},d2} are
multiplied (to give {Union[{i1,...},{j1,..}],d1*d2)) only if the lists
{i1,i2,...}, {j1,j2,...} are disjoint. (In other words, we have a "partial
monoid" of "divisors"). With these changes the program works as below. The
programming becomes somewhat more complicated but, it seems to me still not
too difficult.
Andrzej
on 00.7.8 6:05 PM, Andrzej Kozlowski at andrzej at tuins.ac.jp wrote:
> 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/