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