10
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – jstnthms Jul 28 '17 at 5:40
  • \$\begingroup\$ The program should theoretically function for n > 4, although that will never work in practice, as we only know of 5 Fermat primes. \$\endgroup\$ – poi830 Jul 28 '17 at 5:42
  • \$\begingroup\$ I don't really understand the purpose of theoretically working for all Fermat primes, since there are only 5 known terms. \$\endgroup\$ – Mr. Xcoder Jul 28 '17 at 8:26
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – JAD Jul 28 '17 at 10:42
  • 3
    \$\begingroup\$ 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" \$\endgroup\$ – Kamil Drakari Jul 28 '17 at 13:19

10 Answers 10

6
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Oh, so one uses to clear the result... TIL \$\endgroup\$ – Leaky Nun Jul 28 '17 at 6:05
  • \$\begingroup\$ Oh, so one uses ÆẸ instead of 2* for a single integer... TIL \$\endgroup\$ – Erik the Outgolfer Jul 28 '17 at 9:52
2
\$\begingroup\$

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
}
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 56 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Pyth, 14 bytes

e.f&P_ZsIltZQ3

Try it online!

Uses 1-indexing.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Note that it must return the nth prime Fermat number, not just the nth Fermat number. \$\endgroup\$ – poi830 Jul 29 '17 at 0:46
  • \$\begingroup\$ @poi830 now the prime check takes up most of the function :( \$\endgroup\$ – SuperStormer Jul 29 '17 at 0:56
  • \$\begingroup\$ i think you can say i<2 instead of i==1 becuase zero is also good here? that should reduce be 2 byte \$\endgroup\$ – DanielIndie Oct 8 '17 at 16:38
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!   
                                                  ]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.