2
$\begingroup$

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

I though about something like

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!

$\endgroup$
4
  • 3
    $\begingroup$ 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 $\endgroup$
    – Bill
    Sep 7, 2022 at 18:13
  • $\begingroup$ @Bill Wow, that was a rather cool trick! $\endgroup$ Sep 7, 2022 at 18:15
  • 2
    $\begingroup$ For example: Table[If[PrimeQ[2^(2 k) + 1], {2 k, 2^(2 k) + 1}, Nothing], {k, 1, 10}] $\endgroup$
    – Syed
    Sep 7, 2022 at 18:17
  • 4
    $\begingroup$ Select[Range[0, 100, 4], PrimeQ[2^# + 1] &] $\endgroup$
    – Bob Hanlon
    Sep 7, 2022 at 18:55

1 Answer 1

6
$\begingroup$

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]
  ]
]
$\endgroup$
2
  • $\begingroup$ This is simply WONDERFUL. $\endgroup$ Sep 8, 2022 at 11:19
  • $\begingroup$ @Numb3rs I am delighted that it helped! $\endgroup$
    – MarcoB
    Sep 8, 2022 at 12:24

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.