Hilbert Primes Golf

18

Hilbert-Zahlen sind als positive ganze Zahlen der Form 4n + 1für definiert n >= 0. Die ersten Hilbert-Zahlen sind:

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

Die Hilbert-Nummernfolge ergibt sich aus der OEIS-Folge A016813 .

Eine verwandte Zahlenfolge, die Hilbert-Primzahlen, sind als die Hilbert-Zahlen definiert H > 1, die durch keine Hilbert-Zahl teilbar sind, kso dass 1 < k < H. Die ersten Hilbert-Primzahlen sind:

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

Natürlich hat OEIS auch diese Reihenfolge .

Bei einer nsolchen Ganzzahl wird 0 <= n <= 2^16als Eingabe die nth-Hilbert-Primzahl ausgegeben .

Dies ist Codegolf , daher gelten Standardregeln, und der kürzeste Code in Bytes gewinnt.

Bestenliste

Das Stapel-Snippet am Ende dieses Beitrags generiert die Rangliste aus den Antworten a) als Liste der kürzesten Lösungen pro Sprache und b) als Gesamtrangliste.

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

## Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

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

Wenn Sie mehrere Zahlen in Ihre Kopfzeile aufnehmen möchten (z. B. weil Ihre Punktzahl die Summe von zwei Dateien ist oder wenn Sie die Strafen für Interpreter-Flags separat auflisten möchten), stellen Sie sicher, dass die tatsächliche Punktzahl die letzte Zahl in der Kopfzeile ist:

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

Sie können den Namen der Sprache auch als Link festlegen, der dann im Snippet angezeigt wird:

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

Code-Snippet anzeigen

code-golf math number sequence number-theory Mego
quelle
Ich denke du meinst "nicht teilbar durch" anstatt "relativ primitiv mit". 21 und 9 teilen sich einen gemeinsamen Faktor von 3.
xnor

Antworten:

3

Pyth, 21 Bytes

Lh*4bye.fqZf!%yZyT1hQ

Probieren Sie es online aus: Demo oder Test Suite

Erläuterung:

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
quelle
11

Haskell, 46 Bytes

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

Eine anonyme Funktion.

Der Kern ist foldr(\a b->a:[x|x<-b,mod x a>0])[][5,9..], der die arithmetische Abfolge durchläuft und 5,9,13,...jeweils ein Vielfaches aus der Liste rechts davon entfernt. Dies ergibt die unendliche Liste der Hilbert-Primzahlen. Dann !!nimmt man das nth-Element.

Ich habe versucht, (\a b->a:[x|x<-b,mod x a>0])pointfree zu machen, aber keinen kürzeren Weg gefunden.

xnor
quelle
3
Wenn Sie das foldrin ein anderes Listenverständnis ([x|x<-[5,9..],all((>0).mod x)[5,9..x-1]]!!)
nimi
@ nimi Schöne Lösung. Sie sollten das posten, es ist eine andere Methode. Ich bin traurig, dass es kürzer ist, weil es direkter mit der Definition zusammenhängt und die Wiederholung der Liste weniger hübsch ist.
xnor
4

CJam, 36 33 32 23 Bytes

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

Probieren Sie es online aus

Die neueste Version ist eigentlich viel mehr bei MartinBüttner als bei mir. Die Schlüsselidee in seiner vorgeschlagenen Lösung besteht darin, zwei verschachtelte Schleifen zu verwenden, um den n-ten Wert zu finden, der die Bedingung erfüllt. Ich dachte, ich wäre schlau, wenn ich in meiner ursprünglichen Lösung nur eine einzige Schleife verwenden würde, aber es stellte sich heraus, dass die zusätzliche Logik mehr kostet, als ich gespart habe, wenn ich keine zweite Schleife verwendet habe.

Erläuterung

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
quelle
2

Minkolang 0.14 , 46 37 32 Bytes

Ich wusste nicht, dass der Gosub völlig unnötig ist ...> _>

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

Probieren Sie es hier aus und überprüfen Sie alle Testfälle hier .

Erläuterung

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.

Das Register wird zum Speichern des Zielindex verwendet. Die äußere while-Schleife berechnet jede Hilbert-Zahl und führt eine Buchhaltung durch. Die innere while-Schleife prüft jede Hilbert-Nummer auf Primalität. Wenn eine Hilbert-Zahl keine Hilbert-Primzahl ist, wird das Ziel inkrementiert, sodass die äußere while-Schleife (mindestens) ein weiteres Mal wiederholt werden muss, wodurch Hilbert-Komposite effektiv übersprungen werden.

El'endia Starman
quelle
2

Mathematica, 65 Bytes

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

Erzeugt die gesamte Liste und wählt das Element aus.

LegionMammal978
quelle
1

Ruby, 60 Bytes

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

Prüft nur Hilbert-Primfaktoren.

MegaTom
quelle
0

JavaScript (ES6), 73 Byte

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

Überprüfen Sie einfach die Hilbert-Nummern nacheinander, bis wir die n-te Hilbert-Primzahl erreichen. Die Teilbarkeit durch die Hilbert-Zahl wird von Regex übernommen.

n̴̖̋h̴̖̋ã̷͉h̷̭̿d̷̰̀ĥ̷̳
quelle
0

Matlab, 74 83 Bytes

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

Vielen Dank an Tom Carpenter für das Entfernen von 9 Bytes!

Beispiel Verwendung:

>> H(20)
ans =
   101
Luis Mendo
quelle
@TomCarpenter Danke! Jetzt ist diese Antwort mehr deine als meine :-)
Luis Mendo
Bitte :). Es ist immer noch Ihre Logik, ich habe nur ein paar Tricks angewendet, die ich auf dem Weg gelernt habe.
Tom Carpenter
0

Julia, 73 Bytes

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

Vielen Dank an Alex A. für das Speichern von 11 Bytes! Dies verwendet den gleichen Algorithmus wie die Matlab- und Ruby-Antworten. Da Julia-Arrays einindiziert sind, beginnt dies mit f(1) == 5.

Mein erster Versuch mit dem Lazy-Paket ist 106 Bytes . Wenn Sie dies in REPL ausführen möchten, müssen Sie an den Zeilenenden Semikolons einfügen, um die unendliche Ausgabe zu unterdrücken. Und rufen Pkg.Add("Lazy")Sie an, wenn Sie es noch nicht installiert haben.

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 sagt Reinstate Monica
quelle
1
73 Bytes: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
Sie können etwas mehr sparen, indem Sie endofanstelle von lengthund x%kanstelle von verwenden mod(x,k).
Alex A.