MathGroup Archive 2000

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Divisors

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.


on 00.7.8 6:05 PM, Andrzej Kozlowski at andrzej at wrote:

> on 00.7.8 2:18 PM, Hans Havermann at hahaj at 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

  • Prev by Date: A strange bug in Solve
  • Next by Date: RE: Contour labeling
  • Previous by thread: Re: Divisors
  • Next by thread: Re: Divisors