Generating Fermat primes

Question

Given a number n, print the nth prime Fermat number, where the Fermat numbers are of the form 2^2k+1. This code should theoretically work for any n (i.e. don't hardcode it), although it is not expected to terminate for n > 4. (It should not return 4294967297 for n=5, as 4294967297 is not a prime number.)

Do note that while all Fermat primes are of the form 2²ⁿ+1, not all numbers of the form 2²ⁿ+1 are prime. The goal of this challenge is to return the n-th prime.

Test cases

0 -> 3
1 -> 5
2 -> 17
3 -> 257
4 -> 65537

Rules

• Standard loopholes are disallowed.
• 0-indexing and 1-indexing are both acceptable.
• This is code-golf, lowest byte-count wins.

Related: Constructible n-gons

Answer 1

Python 2, 53 bytes

k=input();F=2
while k:F*=F;k-=3**(F/2)%-~F/F
print-~F

Try it online!

Uses Pépin's test.

---

Python 2, 54 bytes

f=lambda k,F=4:k and f(k-3**(F/2)%-~F/F,F*F)or F**.5+1

Try it online!

Answer 2

Jelly, 13 11 bytes

ÆẸ⁺‘©ÆPµ#ṛ®

Uses 1-based indexing.

Try it online!

How it works

ÆẸ⁺‘©ÆPµ#ṛ®  Main link. No argument.

        #    Read an integer n from STDIN and call the chain to the left with
             arguments k = 0, 1, 2, ... until n matches were found.
ÆẸ           Find the integer with prime exponents [k], i.e., 2**k.
  ⁺          Repeat the previous link, yielding 2**2**k.
   ‘         Increment, yielding 2**2**k+1 and...
    ©        copy the result to the register.
     ÆP      Test the result for primality.
          ®  Yield the value from the register, i.e., the n-th Fermar prime.
         ṛ   Yield the result to the right.

Answer 3

Perl 6,  45  42 bytes

{({1+[**] 2,2,$++}...*).grep(*.is-prime)[$_]}

Try it

{({1+2**2**$++}...*).grep(*.is-prime)[$_]}

Try it

Expanded:

{  # bare block lambda with implicit parameter ｢$_｣

  (  # generate a sequence of the Fermat numbers

    {
      1 +
      2 ** 2 **
        $++            # value which increments each time this block is called
    }
    ...                # keep generating until:
    *                  # never stop

  ).grep(*.is-prime)\  # reject all of the non-primes
  [$_]                 # index into that sequence
}

Answer 4

Mathematica, 56 bytes

(t=n=0;While[t<=#,If[(PrimeQ[s=2^(2^n)+1]),t++];n++];s)&

Try it online!

Answer 5

Dyalog APL (29 Characters)

I'm almost certain this can be improved.

{2=+/0=(⍳|⊢)a←1+2*2*⍵:a⋄∇⍵+1}

This is a recursive function which checks the number of divisors of 1+2^2^⍵, where ⍵ is the right argument of the function. If the number of divisors is 2, the number is prime, and it returns it, otherwise, it calls the function again with ⍵+1 as a right argument.

Example

{2=+/0=(⍳|⊢)a←1+2*2*⍵:a ⋄ ∇ ⍵+1}¨⍳4
      5 17 257 65537

Here I call the function on each of ⍳4 (the numbers 1-4). It applies it to every number in turn.

Answer 6

Pyth, 14 bytes

e.f&P_ZsIltZQ3

Try it online!

Uses 1-indexing.

Answer 7

Pyth, 14 bytes

Lh^2^2byfP_yTQ

Try online.

Main idea "borrowed" from xnor's answer in another question

Lh^2^2byfP_yTQ

L                    define a function with name y and variable b, which:
 h^2^2b                returns 1+2^2^b
       y             call the recently defined function with argument:
        f    Q         the first number T >= Q (the input) for which:
         P_yT            the same function with argument T returns a prime
                     and implicitly print

Answer 8

05AB1E, 8 bytes

Code:

Results are 1-indexed.

µN<oo>Dp

Uses the 05AB1E encoding. Try it online!

Explanation:

µ              # Run the following n succesful times..
 N             #   Push Nn
  oo           #   Compute 2 ** (2 ** n)
    >          #   Increment by one
     D         #   Duplicate
      p        #   Check if the number is prime
               # Implicit, output the duplicated number which is on the top of the stack

Answer 9

Javascript, 12 46 bytes

k=>eval('for(i=n=2**2**k+1;n%--i;);1==i&&n')

Most of the code is taken up by the prime check, which is from here.

Answer 10

Haskell, 61 bytes

p n=2^2^n;f=(!!)[p x+1|x<-[0..],all((>)2.gcd(p x+1))[2..p x]]

Try it online!

0-based index

Explanation

p n=2^2^n;                                          -- helper function 
                                                    -- that computes what it says
f=                                                  -- main function
  (!!)                                              -- partially evaluate 
                                                    -- index access operator
      [p x+1|                                       -- output x-th fermat number
             x<-[0..],                              -- try all fermat number indices
                      all                 [2..p x]  -- consider all numbers smaller F_x
                                                    -- if for all of them...
                         ((>)2                      -- 2 is larger than...
                              .gcd(p x+1))          -- the gcd of F_x 
                                                    -- and the lambda input 
                                                    -- then it is a Fermat prime!   
                                                  ]

Answer 11

Husk, 11 bytes

!fṗmȯ→‼`^2N

Try it online!

Answer 12

GolfScript, 26 bytes

~3\{{(.*).,(;{*}*)1$%}do}*

Try it online!

0-indexed

~                            # Parse n to a number
 3                           # Push 3
  \{                    }*   # Execute this block n times, this block gets the next Fermat prime
    {                }do     # While the number is composite
     (.*)                    # Go to the next Fermat number
         .,(;                # Make an array from 1 to (F_n)-1
             {*}*            # Multiply the numbers to get ( (F_n)-1 )!
                 )           # Increment it
                  1$%        # This will be 0 iff the Fermat number is prime

The primality test used here is Wilson's theorem.