2
$\begingroup$

I have a list that represents a factorization of a number: its format is identical to the output of FactorInteger. I need to select the divisors that meet some criteria, but using Divisors seemed redundant because the number is already factored. Also, the number is extremely large, has several prime factors with 20+ digits, and has so many factors that generating the list of all divisors required so much memory and time. (My Mathematica crashed after taking around 13GB of memory)

For example, using $\frac{10^{180}-1}{9} = \underbrace{11...11}_{180 \space 1s}$ as a dummy number:

num = {{3, 2}, {7, 1}, {11, 1}, {13, 1}, {19, 1}, {31, 1}, {37, 1}, {41, 1},
 {61, 1}, {101, 1}, {181, 1}, {211, 1}, {241, 1}, {271, 1}, {2161, 1},
 {3541, 1}, {9091, 1}, {9901, 1}, {27961, 1}, {29611, 1}, {52579, 1},
 {238681, 1}, {333667, 1}, {2906161, 1}, {3762091, 1}, {4188901, 1},
 {39526741, 1}, {999999000001, 1}, {8985695684401, 1}, {4185502830133110721, 1},
 {4999437541453012143121, 1}, {1105097795002994798105101, 1}}

This is (the simplified version of) my code that crashed my computer:

Select[Divisors[Times @@ Power @@@ num], crit]

This meant that I can't simply make a list of all divisors and then use Select.

If the factors list did not contain any repeated prime factors, I could have done this:

factors = num[[All, 1]];
Reap[Do[If[crit, Sow[#]]&@ Inner[Power, factors,
  IntegerDigits[a, 2, Length[factors]], Times],
 {a, 0, 2^Length[factors] - 1)]]

This works because a is converted to binary, and each factor of the number is raised to a digit of a (1 or 0) and multiplied. As a increases, it will cover all possible divisors.

This cannot be done because my num has repeated prime factors. How could I do this with a large number with repeated prime factors?

Edit:

The problem is that the list of all divisors is too large to store. I am looking for a way to generate and test criteria to divisors one by one so that the list of all divisors do not need to get stored during the process (see code that begins with factors). By divisors, I mean all numbers that can divide another number. For instance, divisors of 30 would be {1,2,3,5,6,10,15,30}.

$\endgroup$
  • 1
    $\begingroup$ It seems to me that f /@ DeleteDuplicates[num[[All, 1]]] should work. Am I missing something? $\endgroup$ – m_goldberg Jan 1 '16 at 22:40
  • $\begingroup$ I am not sure where are you going with this because the occurence of repeated prime factors is part of the factorized representation of the original integer therefore, to eliminate the repeated occurrences of prime factors is in fact, changing the original integer. So I am not sure where is this going. I can tell you that for these type of performace issues there is ParallelTable which could avoid session crashes by distributing the computation among different kernels and cores in one or more machines. $\endgroup$ – Schopenhauer Jan 2 '16 at 0:51
  • $\begingroup$ @m_goldberg I need to apply f to all divisors of the number, not just the prime factors. num is a prime factorization, not a list of divisors. $\endgroup$ – JungHwan Min Jan 2 '16 at 2:34
  • 1
    $\begingroup$ @Schopenhauer I mentioned that the repeated prime factor makes the third code (begins with factors) unusable. I am looking for a way to apply f to all divisors without generating the full list of divisors. The code I presented successfully does the job but only works for numbers that have no repeated prime factors. I am trying to find a way to write a code that does the same task but does not fail for numbers with repeated prime factors. $\endgroup$ – JungHwan Min Jan 2 '16 at 2:38
  • $\begingroup$ @JHM So the question is more about controlling evaluation. I would not use the front end to carry out this task. I would use a script with the set of Parallel and Wait functions and put my partial results in files.mx or files.txt then use Get, ReadList or other method to scan these for the elements of interest to go further. I would also try a more general approach i.e. using Algebra. Maybe a little far fetch but these stream processing type of computations seem better suited for a GPU. $\endgroup$ – Schopenhauer Jan 6 '16 at 11:51
4
$\begingroup$

Here's a sketch of a way to do this:

ClearAll["Global`*"]


(* fake some biggish number and get prime factorization *)    
num = Times @@ (Range[12]!)
fi = FactorInteger[num];

(* spit out divisors *)
ki = fi[[All, 2]] + 1;
vars = Transpose[{Unique[] & /@ ki, ki}];
result = Reap[
   With[{seq = Sequence @@ vars, vars = vars[[All, 1]]}, 
    Do[Sow[Times @@ (fi[[All, 1]]^(vars - 1))], seq]]];

(* check against Divisors fn. *)
Length@Divisors[num]
Divisors[num] == Sort[result[[2, 1]]]

127313963299399416749559771247411200000000000

387828

True

Simply sets up iterators based on multiplicity of prime factors, spits out all the combinations. Obviously, you'd do your whatever within the Do - I just Sow/Reap here to get them all for the small example.

N.B.: The results are unsorted, not sure there's an efficient way to produce a huge set sequentially in order, but the results are the distinct divisors in any case.

$\endgroup$
  • $\begingroup$ I have attempted this approach, using a Do loop, but the time taken was significantly longer. For a relatively small number (with 2 million divisors), f /@ Divisors[ ... ] took less than 1/8 of time taken by my Do loop code. My Do loop code is almost identical to this code. $\endgroup$ – JungHwan Min Jan 2 '16 at 7:45
1
$\begingroup$

There are 6,442,450,944 divisors. Are you sure you want to go there?

Anyway, you can just use Outer. Here is an example on the first seven primes in your factorization, yielding 192 unique divisors (including 1 and the number itself):

f = {{3, 2}, {7, 1}, {11, 1}, {13, 1}, {19, 1}, {31, 1}, {37, 1}};
Flatten[Outer[Times, ##] & @@ (#1^Range[0, #2] & @@@ f)]//Sort
{1,3,7,9,11,13,19,21,31,33,37,39,57,63,77,91,93,99,111,117,133,143,171,209,217,231,247,259,273,279,333,341,399,403,407,429,481,589,627,651,693,703,741,777,819,1001,1023,1147,1197,1209,1221,1287,1443,1463,1729,1767,1881,1953,2109,2223,2331,2387,2717,2821,2849,3003,3069,3367,3441,3627,3663,4123,4329,4389,4433,4921,5187,5291,5301,6327,6479,7161,7657,7733,8029,8151,8463,8547,9009,9139,10101,10323,12369,12617,13167,13299,14763,14911,15561,15873,19019,19437,21483,21793,22971,23199,24087,24453,25389,25641,27417,30303,31031,37037,37107,37851,39897,44289,44733,45353,47619,53599,54131,57057,58311,63973,65379,68913,69597,72261,82251,84227,88319,93093,100529,104377,111111,113553,134199,136059,152551,160797,162393,164021,171171,191919,196137,239723,252681,264957,279279,283309,301587,313131,333333,408177,457653,482391,487179,492063,575757,589589,703703,719169,758043,794871,849927,904761,939393,1148147,1372959,1476189,1678061,1768767,1983163,2111109,2157507,2549781,3116399,3444441,5034183,5306301,5949489,6333327,9349197,10333323,15102549,17848467,21814793,28047591,65444379,196333137}

That is the same as the output of:

Divisors[196333137]

You can trivially apply a function to each as they are generated (this time didn't bother sorting them):

Flatten[Outer[g[Times[##]] &, ##] & @@ (#1^Range[0, #2] & @@@ f)]
{g[1],g[37],g[31],g[1147],g[19],g[703],g[589],g[21793],g[13],g[481],g[403],g[14911],g[247],g[9139],g[7657],g[283309],g[11],g[407],g[341],g[12617],g[209],g[7733],g[6479],g[239723],g[143],g[5291],g[4433],g[164021],g[2717],g[100529],g[84227],g[3116399],g[7],g[259],g[217],g[8029],g[133],g[4921],g[4123],g[152551],g[91],g[3367],g[2821],g[104377],g[1729],g[63973],g[53599],g[1983163],g[77],g[2849],g[2387],g[88319],g[1463],g[54131],g[45353],g[1678061],g[1001],g[37037],g[31031],g[1148147],g[19019],g[703703],g[589589],g[21814793],g[3],g[111],g[93],g[3441],g[57],g[2109],g[1767],g[65379],g[39],g[1443],g[1209],g[44733],g[741],g[27417],g[22971],g[849927],g[33],g[1221],g[1023],g[37851],g[627],g[23199],g[19437],g[719169],g[429],g[15873],g[13299],g[492063],g[8151],g[301587],g[252681],g[9349197],g[21],g[777],g[651],g[24087],g[399],g[14763],g[12369],g[457653],g[273],g[10101],g[8463],g[313131],g[5187],g[191919],g[160797],g[5949489],g[231],g[8547],g[7161],g[264957],g[4389],g[162393],g[136059],g[5034183],g[3003],g[111111],g[93093],g[3444441],g[57057],g[2111109],g[1768767],g[65444379],g[9],g[333],g[279],g[10323],g[171],g[6327],g[5301],g[196137],g[117],g[4329],g[3627],g[134199],g[2223],g[82251],g[68913],g[2549781],g[99],g[3663],g[3069],g[113553],g[1881],g[69597],g[58311],g[2157507],g[1287],g[47619],g[39897],g[1476189],g[24453],g[904761],g[758043],g[28047591],g[63],g[2331],g[1953],g[72261],g[1197],g[44289],g[37107],g[1372959],g[819],g[30303],g[25389],g[939393],g[15561],g[575757],g[482391],g[17848467],g[693],g[25641],g[21483],g[794871],g[13167],g[487179],g[408177],g[15102549],g[9009],g[333333],g[279279],g[10333323],g[171171],g[6333327],g[5306301],g[196333137]}

This fixes the what you "could have done", but that's still going to generate a giant list of six billion things. You need to say what you're going to do with the six billion function results.

Given the edited question, you can generate the divisors recursively and use Reap and Sow to return a (hopefully) small subset of them that meet a test. For example, applying the test g to the divisors generated by the factor list f (n starts as 1):

gen[{n_, f_}, g_] := 
 If[Length@f == 0, If[g@n, Sow@n];, 
  gen[{n f[[1, 1]]^#, Drop[f, 1]}, g] & /@ Range[0, f[[1, 2]]];]

Then:

f = {{3, 2}, {7, 1}, {11, 1}, {13, 1}, {19, 1}, {31, 1}, {37, 1}};
Reap[gen[{1, f}, # > 1000000 &];][[2, 1]]

gives all of the divisors greater than a million:

{3116399,1983163,1678061,1148147,21814793,9349197,5949489,5034183,3444441,2111109,1768767,65444379,2549781,2157507,1476189,28047591,1372959,17848467,15102549,10333323,6333327,5306301,196333137}

The recursion depth will be the length of the factors list, and so will take very little memory. The memory will be driven by how many divisors meet the criterion to Sow.

$\endgroup$
  • $\begingroup$ The problem is that generating the list of divisors would take too much time and memory. I am trying to find a way to apply a function f to each divisor without generating the entire list of divisors; I am not looking for a way to generate the list of divisors without Divisors. $\endgroup$ – JungHwan Min Jan 2 '16 at 7:16
  • $\begingroup$ That was not clear until your later "Edit:". What you said in your question before that edit was that you were trying to avoid the FactorInteger part of Divisors. Furthermore, your example of what you "could have done" does exactly this, generating all the values. I answered your original question: This cannot be done because my num has repeated prime factors. How could I apply a function to all divisors of a large number with repeated prime factors? $\endgroup$ – Mark Adler Jan 2 '16 at 7:54
  • $\begingroup$ I realized that the entire question was misstated. The function I am using contains If and Sow, and I am trying to select the divisors that fit some criteria. Generating the entire list of divisors and then using Select would consume too much memory, so I was searching a way to select the desired divisors without doing that. $\endgroup$ – JungHwan Min Jan 2 '16 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.