1
$\begingroup$

I am trying to find all divisors of 200! [Project Euler, problem 608 - in case anybody is curious]. It has many divisors and hence using Divisors[200!] is not an option.

What I am trying to do is to loop in parallel from 1 to 200! and if the value Divisible[200!,i] yields true then use that number i to perform further calculations.

Now, this is giving me issues that Mathematica tries to construct a List from 1 to 200! (which is a HUGE list), whereas I want Mathematica to consider one number at a time. I have tried experimenting with Hold, HoldAll and Release but frankly, I am very new to Mathematica and am not making any progress.

Any help will be greatly appreciated.

$\endgroup$
3
  • $\begingroup$ I don't know the problem (#608), but your description implies you want to find ~10^29+ divisors -- you're gonna need ~10^15 cores to finish in one day or so. $\endgroup$
    – Michael E2
    Oct 1, 2017 at 2:06
  • $\begingroup$ The whole point of problem 608 is to avoid needless computations—of which there are many. For instance, you count the number of divisors of 12 when calculating (for different values of $k$): $\sigma_0 (1 \cdot 12)$ and $\sigma_0 (2 \cdot 6)$ and $\sigma_0 (3 \cdot 4)$ and $\sigma_0 (4 \cdot 3)$ etc. Such "overcounting" occurs hundreds of billions of times in this overall calculation. $\endgroup$ Oct 1, 2017 at 2:57
  • 1
    $\begingroup$ For the example given in the problem link in my comment, this code gives the proper answer: Total@Table[ Sum[DivisorSigma[0, i k], {k, 1, 10^6}], {i, Divisors[4!]}]. $\endgroup$ Oct 1, 2017 at 3:23

1 Answer 1

4
$\begingroup$

How many (not-necessarily-prime) factors of $200!$ are there? First, get all the prime factors. (The maximum such factor will be less than $200$, of course--in fact it is $199$.) FactorInteger[200!] gives each prime factor with its multiplicity:

{{2, 197}, {3, 97}, {5, 49}, {7, 32}, {11, 19}, {13, 16}, {17, 11}, {19, 10}, {23, 8}, {29, 6}, {31, 6}, {37, 5}, {41, 4}, {43, 4}, {47, 4}, {53, 3}, {59, 3}, {61, 3}, {67, 2}, {71, 2}, {73, 2}, {79, 2}, {83, 2}, {89, 2}, {97, 2}, {101, 1}, {103, 1}, {107, 1}, {109, 1}, {113, 1}, {127, 1}, {131, 1}, {137, 1}, {139, 1}, {149, 1}, {151, 1}, {157, 1}, {163, 1}, {167, 1}, {173, 1}, {179, 1}, {181, 1}, {191, 1}, {193, 1}, {197, 1}, {199, 1}}

So any factor can be expressed as a product $2^{a_2} \times 3^{a_3} \times \cdots \times 199^{a_{199}}$, where the value of $a_2$ can be $0, 1, 2, \ldots, 197$, and thus there are $198$ possible values in the $2$ "slot," and likewise $98$ possible values in the $3$ "slot," and so on. The total number of factors is then just the product of the total number of values for each "slot." That is computed thus:

Times @@ (# + 1 & /@ FactorInteger[200!][[All, 2]])

$n = 139503973313460993785856000000 = 1.39504\times 10^{29}$.

If you want the humongous list of factors, just compute $2^{a_2} \times 3^{a_3} \times \cdots$ and plug in every one of the $n$ combinations of values of $a_i$ given the constraints above.

Clearly this is not the way to solve Euler 608, but it does (I submit) solve the question as posed. Moreover, this method can be easily parallelized (by apportioning different ranges of $a_i$ to different processors), but this number is so large such direct computation is infeasible on realistic hardware.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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