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/