Génération de nombres premiers de Fermat

10

Étant donné un nombre n, imprimez le nième nombre de Fermat premier , où les nombres de Fermat sont de la forme 2 2 k +1. Ce code devrait théoriquement fonctionner pour tout n (c'est-à-dire ne pas le coder en dur), bien qu'il ne devrait pas se terminer pour n> 4. (Il ne devrait pas retourner 4294967297 pour n = 5, car 4294967297 n'est pas un nombre premier.)

Notez que si tous les nombres premiers de Fermat sont de la forme 2 2 n +1, tous les nombres de la forme 2 2 n +1 ne sont pas premiers. Le but de ce défi est de rendre le nième nombre premier.

Cas de test

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

Règles

  • Les failles standard ne sont pas autorisées.
  • L'indexation 0 et l'indexation 1 sont toutes deux acceptables.
  • Il s'agit du , le plus petit nombre de victoires d'octets.

Connexes: n-gons constructibles

poi830
la source
1
Suis-je ou certaines des réponses interprètent-elles mal le défi? N'écrivons-nous pas simplement un programme qui sort 2^(2^n) + 1, où nest l'entrée? Cela correspond à vos cas de test (que nous savons déjà excellents, il n'est donc pas nécessaire de vérifier). Et vous ne vous attendez pas à ce que le programme fonctionne où n> 4 (et n = 5 est le premier non premier).
jstnthms
Le programme devrait théoriquement fonctionner pour n> 4, bien que cela ne fonctionnera jamais en pratique, car nous ne connaissons que 5 nombres premiers de Fermat.
poi830
Je ne comprends pas vraiment le but de travailler théoriquement pour tous les nombres premiers de Fermat, car il n'y a que 5 termes connus.
M. Xcoder
2
@CodyGray Les testcases sont trompeurs, car cela fonctionne pour n=1:4. Tous les nombres premiers fermat sont de la forme 2^2^n+1, mais cela ne signifie pas que tous les nombres de la forme 2^2^n+1sont réellement premiers. C'est le cas n=1:4, mais pas n=5par exemple.
JAD
3
Je pense qu'une partie de la confusion est que vous dites que l'entrée est net que la sortie doit être de la forme 2^(2^n)+1. Si vous utilisez différentes variables pour l'entrée et l'exposant, une certaine confusion peut être réduite. Cela peut également aider si vous déclarez explicitement que "n = 5 n'a pas besoin de sortir dans un délai raisonnable, mais qu'il ne doit pas sortir 4294967297"
Kamil Drakari

Réponses:

3

Gelée , 13 11 octets

ÆẸ⁺‘©ÆPµ#ṛ®

Utilise l'indexation basée sur 1.

Essayez-le en ligne!

Comment ça fonctionne

ÆẸ⁺‘©Æ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.
Dennis
la source
Oh, alors on utilise pour effacer le résultat ... TIL
Leaky Nun
Oh, donc on utilise ÆẸau lieu de 2*pour un seul entier ... TIL
Erik the Outgolfer
2

Perl 6 ,  45  42 octets

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

Essayez-le

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

Essayez-le

Étendu:

{  # 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
}
Brad Gilbert b2gills
la source
1

Mathematica, 56 octets

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

Essayez-le en ligne!

J42161217
la source
0

Pyth , 14 octets

Lh^2^2byfP_yTQ

Essayez en ligne.

Idée principale "empruntée" à la réponse de xnor dans une autre 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
allégations
la source
0

05AB1E , 8 octets

Code:

Les résultats sont indexés 1.

µN<oo>Dp

Utilise l' encodage 05AB1E . Essayez-le en ligne!

Explication:

µ              # 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
Adnan
la source
0

Javascript, 12 46 octets

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

La plupart du code est repris par le chèque principal, qui est d' ici .

SuperStormer
la source
Notez qu'il doit retourner le nième nombre de Fermat premier , pas seulement le nième nombre de Fermat.
poi830
@ poi830 maintenant la vérification principale occupe la majeure partie de la fonction :(
SuperStormer
je pense que vous pouvez dire que je <2 au lieu de i == 1 parce que zéro est également bon ici? qui devrait réduire à 2 octets
DanielIndie
0

Dyalog APL (29 caractères)

Je suis presque certain que cela peut être amélioré.

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

Il s'agit d'une fonction récursive qui vérifie le nombre de diviseurs de 1 + 2 ^ 2 ^ ⍵, où ⍵ est le bon argument de la fonction. Si le nombre de diviseurs est 2, le nombre est premier, et il le renvoie, sinon, il appelle à nouveau la fonction avec ⍵ + 1 comme argument de droite.

Exemple

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

Ici, j'appelle la fonction sur chacun de ⍳4 (les nombres 1-4). Il l'applique tour à tour à chaque numéro.

James Heslip
la source
0

Haskell , 61 octets

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

Essayez-le en ligne!

Index basé sur 0

Explication

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!   
                                                  ]
SEJPM
la source