Hilbert Primes Golf

18

Les nombres de Hilbert sont définis comme des entiers positifs de la forme 4n + 1pour n >= 0. Les premiers nombres de Hilbert sont:

1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97

La séquence des nombres de Hilbert est donnée par la séquence OEIS A016813 .

Une séquence de nombres apparentés, les nombres premiers de Hilbert, sont définis comme les nombres de Hilbert H > 1qui ne sont pas divisibles par un nombre de Hilbert ktel que 1 < k < H. Les premiers nombres premiers de Hilbert sont:

5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, 141, 149, 157, 161, 173, 177, 181, 193, 197

Naturellement, OEIS a également cette séquence .

Étant donné un entier ntel qu'en 0 <= n <= 2^16entrée, sortez le npremier Hilbert premier.

Il s'agit de code-golf , donc les règles standard s'appliquent et le code le plus court en octets l'emporte.

Classement

L'extrait de pile au bas de cet article génère le classement à partir des réponses a) comme une liste des solutions les plus courtes par langue et b) comme un classement général.

Pour vous assurer que votre réponse s'affiche, veuillez commencer votre réponse avec un titre, en utilisant le modèle Markdown suivant:

## Language Name, N bytes

où Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores dans le titre, en les barrant. Par exemple:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Si vous souhaitez inclure plusieurs nombres dans votre en-tête (par exemple, parce que votre score est la somme de deux fichiers ou que vous souhaitez répertorier les pénalités de drapeau d'interprète séparément), assurez-vous que le score réel est le dernier numéro de l'en-tête:

## Perl, 43 + 2 (-p flag) = 45 bytes

Vous pouvez également faire du nom de la langue un lien qui apparaîtra ensuite dans l'extrait de code:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

Afficher l'extrait de code

code-golf math number sequence number-theory Mego
la source
Je pense que vous voulez dire "non divisible par" au lieu de "relativement premier avec". 21 et 9 partagent un facteur commun de 3.
xnor

Réponses:

3

Pyth, 21 octets

Lh*4bye.fqZf!%yZyT1hQ

Essayez-le en ligne: démonstration ou suite de tests

Explication:

Lh*4bye.fqZf!%yZyT1Q    implicit: Q = input number
L                       define a function y(b), which returns
 h*4b                      4*b + 1
                        this converts a index to its Hilbert number
       .f          hQ   find the first (Q+1) numbers Z >= 1, which satisfy:
           f      1        find the first number T >= 1, which satisfies:
            !%yZyT            y(Z) mod y(T) == 0
         qZ                test if the result is equal to Z 

                        this gives a list of indices of the first Q Hilbert Primes
      e                 take the last index
     y                  apply y and print
Jakube
la source
11

Haskell, 46 octets

(foldr(\a b->a:[x|x<-b,mod x a>0])[][5,9..]!!)

Une fonction anonyme.

Le noyau est foldr(\a b->a:[x|x<-b,mod x a>0])[][5,9..], qui itère à travers la progression arithmétique 5,9,13,..., en supprimant les multiples de chacun de la liste à sa droite. Cela produit la liste infinie des nombres premiers de Hilbert. Ensuite, !!prend le nth élément.

J'ai essayé de faire sans (\a b->a:[x|x<-b,mod x a>0])point mais je n'ai pas trouvé de moyen plus court.

xnor
la source
3
Transformer le foldren une autre compréhension de la liste sauve deux byes:([x|x<-[5,9..],all((>0).mod x)[5,9..x-1]]!!)
nimi
@nimi Nice solution. Vous devriez poster ça, c'est une méthode différente. Je suis triste mais c'est plus court car c'est plus direct vers la définition et la répétition de la liste est moins jolie.
2015 à 5h07
4

CJam, 36 33 32 23 octets

5ri{_L+:L;{4+_Lf%0&}g}*

Essayez-le en ligne

La dernière version est en réalité bien plus @ MartinBüttner que la mienne. L'idée clé de sa solution suggérée est d'utiliser deux boucles imbriquées pour trouver la nième valeur qui remplit la condition. Je pensais que j'étais intelligent en n'utilisant qu'une seule boucle dans ma solution d'origine, mais il s'avère que la logique ajoutée coûte plus cher que ce que j'ai économisé en n'utilisant pas une deuxième boucle.

Explication

5       Push first Hilbert prime.
ri      Get input n and convert to integer.
{       Loop n times.
  _       Push a copy of current Hilbert prime.
  L       Push list of Hilbert primes found so far (L defaults to empty list).
  +       Prepend current Hilbert prime to list.
  :L      Store new list of Hilbert primes in variable L.
  ;       Pop list off stack.
  {       Start while loop for finding next Hilbert prime.
    4+      Add 4 to get next Hilbert number.
    _       Copy candidate Hilbert number.
    L       Push list of Hilbert primes found so far.
    f%      Element wise modulo of Hilbert number with smaller Hilbert primes.
    0&      Check for 0 in list of modulo values.
  }g      End while loop.
}*      End loop n times.
Reto Koradi
la source
2

Minkolang 0,14 , 46 37 32 octets

Je ne savais pas que le gosub était totalement inutile ...> _>

n$z(xxi4*5+d(4-$d%)1=,z+$ziz-)N.

Essayez-le ici et vérifiez tous les cas de test ici .

Explication

n$z                                 Take number from input and store it in the register
   (                                Open while loop
    xx                              Dump the stack
      i4*5+                         Loop counter times 4 plus 5 (Hilbert number)
           d                        Duplicate
            (                       Open while loop
             4-                     Subtract 4
               $d                   Duplicate stack
                 %                  Modulo
                  )                 Exit while loop when top of stack is 0
                   1=,              0 if 1, 1 otherwise
                      z             Push register value
                       +            Add
                        $z          Pop and store in register
                          iz-       Subtract z from loop counter
                             )      Exit while loop when top of stack is 0
                              N.    Output as number and stop.

Le registre est utilisé pour stocker l'index cible. La boucle while externe calcule chaque nombre de Hilbert et effectue une certaine comptabilité. La boucle while intérieure vérifie la primauté de chaque nombre Hilbert. Si un nombre de Hilbert n'est pas un nombre premier de Hilbert, alors la cible est incrémentée de sorte que la boucle while externe doit se répéter (au moins) une fois de plus, en ignorant efficacement les composites Hilbert.

El'endia Starman
la source
2

Mathematica, 65 octets

Select[4Range[4^9]+1,Divisors[#][[2;;-2]]~Mod~4~FreeQ~1&][[#+1]]&

Génère la liste entière et en sélectionne l'élément.

LegionMammal978
la source
1

Rubis, 60 octets

h=->i{n=[];x=5;n.any?{|r|x%r<1}?x+=4: n<<x until e=n[i-1];e}

Vérifie uniquement les facteurs premiers de Hilbert.

MegaTom
la source
0

JavaScript (ES6), 73 octets

n=>{for(i=0,t=2;i<=n;)i+=!/^(.(....)+)\1+$/.test(Array(t+=4));return t-1}

Il suffit de vérifier les numéros de Hilbert un par un jusqu'à ce que nous atteignions le nième nombre de Hilbert. La divisibilité par nombre de Hilbert est gérée par l'expression régulière.

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
la source
0

Matlab, 74 83 octets

function t=H(n)
x=5;t=x;while nnz(x)<n
t=t+4;x=[x t(1:+all(mod(t,x)))];end

Merci à Tom Carpenter d'avoir supprimé 9 octets!

Exemple d'utilisation:

>> H(20)
ans =
   101
Luis Mendo
la source
@TomCarpenter Merci! Maintenant, cette réponse est plus la vôtre que la mienne :-)
Luis Mendo
Vous êtes les bienvenus :). C'est toujours ta logique, viens d'appliquer quelques astuces que j'ai apprises en cours de route.
Tom Carpenter
0

Julia, 73 octets

n->(a=[x=5];while length(a)<n;x+=4;all(k->mod(x,k)>0,a)&&push!(a,x)end;x)

Merci Alex A. pour avoir économisé 11 octets! Cela utilise le même algorithme que les réponses Matlab et Ruby. Étant donné que les tableaux Julia sont à un index, cela commence par f(1) == 5.

Ma première tentative, en utilisant le package Lazy, est de 106 octets . Si vous prévoyez d'exécuter cela dans le REPL, assurez-vous d'ajouter des points-virgules aux extrémités des lignes pour supprimer la sortie infinie. Et appelez Pkg.Add("Lazy")si vous ne l'avez pas déjà installé.

using Lazy
r=range
h=r(1,Inf,4)
p=@>>r() filter(n->n!=1&&all(map(x->mod(h[n],h[x])<1,2:n-1)))
f=n->h[p[n]]
Andrew dit de réintégrer Monica
la source
1
73 octets:n->(a=[x=5];while length(a)<n x+=4;all(k->mod(x,k)>0,a)&&push!(a,x)end;x)
Alex A.
1
Vous pouvez en économiser davantage en utilisant endofau lieu de lengthet x%kau lieu de mod(x,k).
Alex A.