Try to use lowercase names at least for the initial letter of your functions.
My timings are different than yours. Probably your computer is much faster than mine.
In your code pro
is calculated in 144 seconds and GCD[func[160001],pro]
needs another 34 seconds so a total of 178 seconds. Of course pro is calculated only once but the same happens in the clustered products below.
prp = {};
func[q_] := 77^q + 2;
Do[If[TimeConstrained[PrimeQ[func[i]], 1, True],
AppendTo[prp, i]], {i, 160000, 161000}]
The following function divides in clusters the product to gain memory but also speed.
ClearAll[gcd];
gcd[list_List, noprimes_: 20000000, noclusters_: 1] :=
Module[{clusters, n, pro},
clusters =
Table[{(i - 1)*noprimes/noclusters + 1, i*noprimes/noclusters}, {i,
noclusters}];
Times @@ ParallelTable[
pro = Product[i, {i, Prime[Range @@ clusters[[j]]]}];
GCD[func[#], pro] & /@ list
, {j, 1, noclusters}]
]
Notice : noclusters must divide exactly noprimes
So using 40 clusters I managed to gain speed and lot's of memory.
AbsoluteTiming[
gcd[{160001}, 200000000, 40]
]
run in 140 seconds (in total for a single kernel).
You can use it also as : gcd[prp,20000000,40]
to get all results.
Remark:
You can also gain a speedup x3 (it runs in 45 seconds in my machine) in a quad core if you use ParallelTable
inside the gcd
function. Times @@ ParallelTable[pro = Product[i, {i, .....
Results: (parallel table on in 644 sec only) So now you can grow your search space.
{643.072782, {117414067, 1, 1002109, 1, 1, 86192723, 1, 1445419, 1, 1,
1, 1, 1, 123791117, 1, 14474231, 100253533, 1, 1, 1, 113404303, 1,
1, 1227181, 1, 1, 1, 1, 1, 1, 27367889, 1, 1, 1, 1, 41178451,
10287491, 1, 1, 1, 367885753, 1604461, 1, 1, 1, 1, 196558247, 1, 1,
582153380112268780892543053, 152758451, 1, 1, 1, 1, 1, 1, 1, 1, 1,
207751097, 117692293, 42702377, 1}}
Results: for 100M primes
{3332.700619, {117414067, 1, 1002109, 1, 1, 86192723, 1, 1445419, 1,
1, 1, 1, 1, 123791117, 1, 14474231, 167856571665498613, 1, 1, 1,
113404303, 1, 1, 1227181, 1, 1, 1097490881, 1, 1, 1, 27367889, 1,
1271310361, 1, 712991261, 41178451, 10287491, 1, 1, 1, 367885753,
1604461, 1758063169, 552414241, 1, 1, 196558247, 1, 1,
582153380112268780892543053, 152758451, 1, 1, 1635548081, 1, 1, 1,
1, 1, 1, 207751097, 117692293, 42702377, 1}}
Results: for 1 billion primes AbsoluteTiming[gcd[prp, 1000000000, 2000]]
{55026.855356, {117414067, 1, 1002109, 1, 1, 86192723, 1, 1445419, 1,
1, 1, 1, 1, 554101616002949381, 1, 14474231, 167856571665498613, 1,
15121883417, 1, 113404303, 1, 2071728343, 1227181, 1, 1, 1097490881,
1, 1, 1, 27367889, 1, 7718516532572391937, 1, 712991261, 41178451,
10287491, 1, 1, 1, 367885753, 1604461, 1758063169, 552414241, 1, 1,
196558247, 1, 1, 582153380112268780892543053, 152758451, 1,
3743040013, 1635548081, 11228560151, 1, 1, 1, 1, 1, 207751097,
743891268843592201, 42702377, 1}}
It seems that for more primes (10 billion) there will be even less 1's
Improvements
The two versions below return the list of exponents that lead to GCD=1 (for the selected number of primes). In the second version gcd2
exponents that lead to GCD greater than 1 are dropped quickly. Also there is an additional parameter namely startcluster
in case someone wants to start from greater primes than 2,3,...
ClearAll[gcd];
gcd[list_List, noprimes_: 20000000, noclusters_: 1,
startcluster_: 1] :=
Module[{clusters, pro},
clusters =
Table[{(i - 1)*noprimes/noclusters + 1, i*noprimes/noclusters}, {i,
startcluster, noclusters}];
Pick[list,
Times @@
ParallelTable[pro = Product[i, {i, Prime[Range @@ clusters[[j]]]}];
GCD[func[#], pro] & /@ list, {j, 1, noclusters - startcluster +1}]
, 1]]
I noticed that the code below does not exploit the CPU kernels efficiently so it seems some times inferior than "simple" gcd
above. This happens because some work may left only for one kernel before moving to the next product.
ClearAll[gcd2];
gcd2[list_List, noprimes_: 20000000, noclusters_: 1,
startcluster_: 1] :=
Module[{clusters, pro, res},
clusters =
Table[{(i - 1)*noprimes/noclusters + 1, i*noprimes/noclusters}, {i,
startcluster, noclusters}];
res = Table[1, {Length[list]}];
Pick[list,
Times @@
ParallelTable[pro = Product[i, {i, Prime[Range @@ clusters[[j]]]}];
If[res[[#]] != 1, 1, res[[#]] = GCD[func[list[[#]]], pro]] & /@
Range[Length[list]],
{j, 1, noclusters - startcluster + 1}]
, 1]]
Also tuning the number of clusters is a hard nut and needs some exploration time.
After all the above my approach would be using the new gcd
(not the gcd2
) and construct my clusters progressively (maybe using a Fold
).
GCD[Func[i],Pr]
will be equal to1
if and only ifGCD[Func[i],everyprime]
result will be equal to 1 for every prime of those 20000000. In this way you will save a lot of Memory but maybe will be slower... $\endgroup$p
be a factor ofn
, thenGCD[p,n] != 1
$\endgroup$