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/>