Hilbert Primes Golf

18

Liczby Hilberta są zdefiniowane jako dodatnie liczby całkowite formularza 4n + 1dla n >= 0. Pierwsze kilka liczb Hilberta to:

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

Sekwencja liczb Hilberta jest podana przez sekwencję OEIS A016813 .

Pokrewną sekwencję liczb, liczby pierwsze Hilberta, definiuje się jako liczby Hilberta H > 1, które nie są podzielne przez żadną liczbę Hilberta, ktaką jak 1 < k < H. Pierwsze kilka liczb pierwszych Hilberta to:

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

Oczywiście OEIS ma również tę sekwencję .

Biorąc pod uwagę liczbę całkowitą ntaką, 0 <= n <= 2^16jak na wejściu, nwyślij pierwszą liczbę pierwszą Hilberta.

Jest to gra w golfa , więc obowiązują standardowe zasady, a wygrywa najkrótszy kod w bajtach.

Tabela liderów

Fragment kodu na dole tego postu generuje tabelę wyników na podstawie odpowiedzi a) jako lista najkrótszych rozwiązań dla każdego języka oraz b) jako ogólna tabela wyników.

Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

## Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

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

Jeśli chcesz umieścić w nagłówku wiele liczb (np. Ponieważ twój wynik jest sumą dwóch plików lub chcesz osobno wymienić kary za flagi tłumacza), upewnij się, że rzeczywisty wynik jest ostatnią liczbą w nagłówku:

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

Możesz także ustawić nazwę języka jako link, który pojawi się we fragmencie:

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

Pokaż fragment kodu

code-golf math number sequence number-theory Mego
źródło
Myślę, że masz na myśli „niepodzielny przez” zamiast „względnie pierwszy z”. 21 i 9 mają wspólny współczynnik 3.
xnor

Odpowiedzi:

3

Pyth, 21 bajtów

Lh*4bye.fqZf!%yZyT1hQ

Wypróbuj online: pakiet demonstracyjny lub testowy

Wyjaśnienie:

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
źródło
11

Haskell, 46 bajtów

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

Anonimowa funkcja.

Rdzeń polega na foldr(\a b->a:[x|x<-b,mod x a>0])[][5,9..]iteracji poprzez postęp arytmetyczny 5,9,13,..., usuwając wielokrotności każdego z listy po prawej stronie. To tworzy nieskończoną listę liczb pierwszych Hilberta. Następnie !!bierze nelement th.

Próbowałem zrobić (\a b->a:[x|x<-b,mod x a>0])bezcelowe, ale nie znalazłem krótszej drogi.

xnor
źródło
3
Przekształcenie foldrw inną listę pozwala zaoszczędzić dwa znaki:([x|x<-[5,9..],all((>0).mod x)[5,9..x-1]]!!)
nimi
@nimi Ładne rozwiązanie. Powinieneś to opublikować, to inna metoda. Przykro mi, że jest krótszy, ponieważ jest bardziej bezpośredni do definicji, a powtarzanie listy jest mniej ładne.
xnor
4

CJam, 36 33 32 23 bajtów

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

Wypróbuj online

Najnowsza wersja jest w rzeczywistości o wiele bardziej @ MartinBüttnera niż moja. Kluczową ideą w jego sugerowanym rozwiązaniu jest użycie dwóch zagnieżdżonych pętli w celu znalezienia n-tej wartości spełniającej warunek. Myślałem, że jestem sprytny, używając tylko jednej pętli w moim oryginalnym rozwiązaniu, ale okazuje się, że dodatkowa logika kosztuje więcej niż zaoszczędziłem, nie używając drugiej pętli.

Wyjaśnienie

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
źródło
2

Minkolang 0,14 , 46 37 32 bajtów

Nie zdawałem sobie sprawy, że gosub był całkowicie niepotrzebny ...> _>

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

Wypróbuj tutaj i sprawdź tutaj wszystkie przypadki testowe .

Wyjaśnienie

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.

Rejestr służy do przechowywania indeksu docelowego. Zewnętrzna pętla while oblicza każdą liczbę Hilberta i wykonuje księgowość. Wewnętrzna pętla while sprawdza pierwszeństwo każdej liczby Hilberta. Jeśli liczba Hilberta nie jest liczbą pierwszą Hilberta, cel jest zwiększany, tak że zewnętrzna pętla while musi się powtarzać (przynajmniej) jeszcze raz, skutecznie pomijając kompozyty Hilberta.

El'endia Starman
źródło
2

Mathematica, 65 bajtów

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

Generuje całą listę i wybiera z niej element.

LegionMammal978
źródło
1

Rubinowy, 60 bajtów

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

Sprawdza tylko czynniki pierwsze Hilberta.

MegaTom
źródło
0

JavaScript (ES6), 73 bajty

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

Po prostu sprawdzaj liczby Hilberta jeden po drugim, aż dotrzemy do n-tej liczby pierwszej Hilberta. Podzielność według liczby Hilberta jest obsługiwana przez regex.

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
źródło
0

Matlab, 74 83 bajtów

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

Dzięki Tom Carpenter za usunięcie 9 bajtów!

Przykładowe zastosowanie:

>> H(20)
ans =
   101
Luis Mendo
źródło
@TomCarpenter Thanks! Teraz ta odpowiedź jest bardziej twoja niż moja :-)
Luis Mendo
Nie ma za co :). To wciąż twoja logika, po prostu zastosowałem kilka sztuczek, których nauczyłem się po drodze.
Tom Carpenter,
0

Julia, 73 bajty

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

Dzięki Alex A. za uratowanie 11 bajtów! Używa tego samego algorytmu, co odpowiedzi Matlab i Ruby. Ponieważ tablice Julii mają jeden indeks, zaczyna się od f(1) == 5.

Moja pierwsza próba, używając pakietu Lazy, to 106 bajtów . Jeśli planujesz uruchomić to w REPL, pamiętaj o dodaniu średników na końcach linii, aby stłumić nieskończone wyjście. I zadzwoń, Pkg.Add("Lazy")jeśli jeszcze go nie masz.

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 mówi Przywróć Monikę
źródło
1
73 bajty: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
Możesz zaoszczędzić trochę więcej, używając endofzamiast lengthi x%kzamiast mod(x,k).
Alex A.,