# Generating Fermat primes

Given a number n, print the nth prime Fermat number, where the Fermat numbers are of the form 22k+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 22n+1, not all numbers of the form 22n+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 , lowest byte-count wins.

Related: Constructible n-gons

• Am I or are some of the answers misinterpreting the challenge? Aren't we simply writing a program that outputs 2^(2^n) + 1, where n is the input? This lines up with your test cases (which we know are already prime, so there's no need to check). And you don't expect the program to work where n > 4 (and n=5 is the first non-prime). Jul 28, 2017 at 5:40
• The program should theoretically function for n > 4, although that will never work in practice, as we only know of 5 Fermat primes. Jul 28, 2017 at 5:42
• I don't really understand the purpose of theoretically working for all Fermat primes, since there are only 5 known terms. Jul 28, 2017 at 8:26
• @CodyGray The testcases are misleading, because this works for n=1:4. All fermat primes are of the form 2^2^n+1, but that does not mean that all numbers of the form 2^2^n+1 are actually prime. This is the case for n=1:4, but not for n=5 for example.
Jul 28, 2017 at 10:42
• I think that some part of the confusion is that you're saying the input is n and the output must be of the form 2^(2^n)+1. If you use different variables for the input and the exponent then some confusion might be reduced. It might also help if you explicitly state that "n=5 doesn't need to output in reasonable time, but it must not output 4294967297" Jul 28, 2017 at 13:19

# 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!

# 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.

• Oh, so one uses ṛ to clear the result... TIL Jul 28, 2017 at 6:05
• Oh, so one uses ÆẸ instead of 2* for a single integer... TIL Jul 28, 2017 at 9:52

# 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 }  # Mathematica, 56 bytes (t=n=0;While[t<=#,If[(PrimeQ[s=2^(2^n)+1]),t++];n++];s)&  Try it online! # 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. # Pyth, 14 bytes e.f&P_ZsIltZQ3  Try it online! Uses 1-indexing. # 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  # 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  # 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. • Note that it must return the nth prime Fermat number, not just the nth Fermat number. Jul 29, 2017 at 0:46 • @poi830 now the prime check takes up most of the function :( Jul 29, 2017 at 0:56 • i think you can say i<2 instead of i==1 becuase zero is also good here? that should reduce be 2 byte Oct 8, 2017 at 16:38 # 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! ]  # Husk, 11 bytes !fṗmȯ→‼^2N  Try it online! # 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.