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/