Re: Divisors

• To: mathgroup at smc.vnet.net
• Subject: [mg24311] Re: [mg24272] Divisors
• From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
• Date: Sun, 9 Jul 2000 04:52:25 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

```
on 00.7.6 12:10 PM, Hans Havermann at hahaj at home.com wrote:

> I need a re-formulated "divisors" function that works, *not* on
> Integers, but on the *list of factors* that one gets when one applies
> FactorInteger to a number. That way I can still get the divisors of a
> number whose factorization is difficult, but nonetheless known.
>
> I have a rough working model of such a function but it relies on the
> function Subsets found in DiscreteMath`Combinatorica` (see below) and I
> don't have enough RAM to apply Subsets to lists larger than 20 elements.
> Unfortunately, I need to find the divisors of numbers whose
> factorization comprises as many as 40 elements.
>
> Can anyone provide a programming solution?
>
> --
> << DiscreteMath`Combinatorica`
>
> fac = First[Transpose[FactorInteger[2*3*3*11*11*11*13]]];
> pow = Last[Transpose[FactorInteger[2*3*3*11*11*11*13]]];
> expfac = {}; Do[
> Do[expfac = Append[expfac, fac[[i]]], {j, 1, pow[[i]]}], {i, 1,
> Length[pow]}]; expfac
>
> {2, 3, 3, 11, 11, 11, 13}
>
> div = ReplacePart[Union[Subsets[expfac]], {1}, 1]
>
> {{1}, {2}, {3}, {11}, {13}, {2, 3}, {2, 11}, {2, 13}, {3, 3}, {3, 11},
> {3, 13}, {11, 11}, {11, 13}, {2, 3, 3}, {2, 3, 11}, {2, 3, 13}, {2, 11,
> 11}, {2, 11, 13}, {3, 3, 11}, {3, 3, 13}, {3, 11, 11}, {3, 11, 13}, {11,
> 11, 11}, {11, 11, 13}, {2, 3, 3, 11}, {2, 3, 3, 13}, {2, 3, 11, 11}, {2,
> 3, 11, 13}, {2, 11, 11, 11}, {2, 11, 11, 13}, {3, 3, 11, 11}, {3, 3, 11,
> 13}, {3, 11, 11, 11}, {3, 11, 11, 13}, {11, 11, 11, 13}, {2, 3, 3, 11,
> 11}, {2, 3, 3, 11, 13}, {2, 3, 11, 11, 11}, {2, 3, 11, 11, 13}, {2, 11,
> 11, 11, 13}, {3, 3, 11, 11, 11}, {3, 3, 11, 11, 13}, {3, 11, 11, 11,
> 13}, {2, 3, 3, 11, 11, 11}, {2, 3, 3, 11, 11, 13}, {2, 3, 11, 11, 11,
> 13}, {3, 3, 11, 11, 11, 13}, {2, 3, 3, 11, 11, 11, 13}}
>
> Sort[Table[Apply[Times, div[[i]]], {i, 1, Length[div]}]]
>
> {1, 2, 3, 6, 9, 11, 13, 18, 22, 26, 33, 39, 66, 78, 99, 117, 121, 143,
> 198, 234, 242, 286, 363, 429, 726, 858, 1089, 1287, 1331, 1573, 2178,
> 2574, 2662, 3146, 3993, 4719, 7986, 9438, 11979, 14157, 17303, 23958,
> 28314, 34606, 51909, 103818, 155727, 311454}
>
> Divisors[2*3*3*11*11*11*13] - %
>
> {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
>
I expect you do not really meant to say  that you want to construct a list
containing possibly up to 2^40 elements. Maybe I am underestimating the
speed of advance of computer technology, but I doubt that you will ever have
enough Ram for such a job! Moreover,  various iterators in Mathematica (e.g.
in Table etc) have to be MachineIntegers and:

In[3]:=
Developer`MachineIntegerQ[2^40]

Out[3]=
False

The only  approach I can think of that might go somewhere in this direction
is to  split your list of divisors into smaller sublists in some well
organised way, and try to construct these smaller lists. For example, you
might simply look at divisors which can be represented as products of k
prime divisors (counting multiplicities). That simply means you should use
the KSubsets function rather than the Subsets function from the
DiscreteMath`Combinatorica` package. Here is a function that would do this:

<< DiscreteMath`Combinatorica`

divisors[l_, k_] :=
Block[{x},
Union[Times @@@
KSubsets[Flatten[Map[Table[#[[1]], {x, #[[2]]}] &, l]], k]]]

applying this to your example you get:
l = FactorInteger[2*3*3*11*11*11*13];

In[5]:=
divisors[l, 4]

Out[5]=
{198, 234, 726, 858, 1089, 1287, 2662, 3146, 3993, 4719, 17303}

and

In[6]:=
Divisors[2*3*3*11*11*11*13] ==
Sort[Flatten[Table[divisors[l, i], {i, 0, Plus @@ Last[Transpose[l]]}]]]

Out[6]=
True

Note, however, that if you were really dealing with a number that factored
into 40 different primes, than there would be 40!/(20!20!)= 137846528820
divisors which themselves are products of 20 primes. That would still make a
list which is far too large to fit into your RAM or indeed to be stored on
any storage medium.

Andrzej

--
Andrzej Kozlowski
Toyama International University, JAPAN

For Mathematica related links and resources try:
<http://www.sstreams.com/Mathematica/>

```

• Prev by Date: Re: A strange bug in Solve
• Next by Date: RE: The Csc problem
• Previous by thread: Re: Divisors
• Next by thread: LogPlot != Plot[Log]