# Code request for a loop searching for primes with certain condition

I am stuck in trying to understand how to write a code (perhaps a for-cycle, or a do-while?) that returns the values of $$n$$ for which $$2^n + 1$$ is a prime, but searching only amongst the values of $$n$$ that are a multiple of $$4$$.

For example: for $$n = 4, 8, 16$$ we have $$2^n + 1$$ is prime.

So I need a code that search among the $$n = 2k$$ where $$k \in \mathbb{N}$$, in a given range, like all the

Module[{list = {}, k},
For[k = 0, k < 100, k++, If[PrimeQ[2^k + 1], AppendTo[list, k]]];
list]


but this does seach among all the natural $$k$$ in that given range, not among the multiple of $$4$$ only...

Thank you!

• Try changing k++ to k+=4 Do a little experiment with a For loop and print k to confirm that it works as you want
– Bill
Sep 7, 2022 at 18:13
• @Bill Wow, that was a rather cool trick! Sep 7, 2022 at 18:15
• For example: Table[If[PrimeQ[2^(2 k) + 1], {2 k, 2^(2 k) + 1}, Nothing], {k, 1, 10}]
– Syed
Sep 7, 2022 at 18:17
• Select[Range[0, 100, 4], PrimeQ[2^# + 1] &] Sep 7, 2022 at 18:55

The most imperative and idiomatic way has already been proposed in comments by Bob Hanlon:

n= 15000;

Select[Range[0, n, 4], PrimeQ[2^# + 1] &]
(* {0, 4, 8, 16} *)


It is very clean and readable, and it takes a reasonable 44.2 seconds on my machine (all times obtained with AbsoluteTiming).

The equivalent For approach, modified from your code, takes 51.6 seconds:

Module[{k, list = {}},
For[
k = 0, k <= n, k = k + 4,
If[PrimeQ[2^k + 1], AppendTo[list, k]]
]
]


A significant improvement is obtained by replacing AppendTo with the typically better-performing Sow and Reap combination (46.0 seconds):

Module[{k},
Reap[
For[
k = 0, k <= n, k = k + 4,
If[PrimeQ[2^k + 1], Sow[k]]
]
][[2, 1]]
]


Using Do leads to similar timing.

Since your problem is embarrassingly parallel (i.e. each task is completely independent of the others), it should be a good candidate for effective parallelization.

The first example below uses ParallelTable to handle all the complication of distributing work to the kernels and re-assembling the chunks into one result. This takes 23.8 seconds on my 4-core laptop, a significant speedup:

ParallelTable[
If[PrimeQ[2^i + 1], i, Nothing],
{i, 0, n, 4}
]


Similar performance can be obtained with Pick and straightforward parallelization of the primality test (24.7 seconds):

With[{r = Range[0, n, 4]},
Pick[
r,
ParallelMap[PrimeQ, 2^r + 1]
]
]

• This is simply WONDERFUL. Sep 8, 2022 at 11:19
• @Numb3rs I am delighted that it helped! Sep 8, 2022 at 12:24