W szczególności PRIMEGAME Conwaya .

Jest to algorytm opracowany przez Johna H. Conwaya w celu generowania liczb pierwszych przy użyciu sekwencji 14 liczb wymiernych:

 A   B   C   D   E   F   G   H   I   J   K   L   M   N
17  78  19  23  29  77  95  77   1  11  13  15  15  55
--  --  --  --  --  --  --  --  --  --  --  --  --  --
91  85  51  38  33  29  23  19  17  13  11  14   2   1

Na przykład F jest ułamkiem 77/29.

Oto jak algorytm znajduje liczby pierwsze. Zaczynając od liczby 2, znajdź pierwszy wpis w sekwencji, który po pomnożeniu razem daje liczbę całkowitą. Tutaj jest to M, 15/2, która produkuje 15. Następnie, dla tej liczby całkowitej 15, znajdź pierwszy wpis w sekwencji, który po pomnożeniu tworzy liczbę całkowitą. To jest ostatni N, lub 55/1, który daje 825. Zapisz odpowiednią sekwencję. (Bystry spośród was może uznać to za program FRACTRAN .)

Po kilku iteracjach otrzymasz:

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4 ...

Zauważ, że ostatni wymieniony element to 4lub 2^2. Oto nasza pierwsza liczba pierwsza ( 2wykładnik) wygenerowana za pomocą tego algorytmu! Ostatecznie sekwencja będzie wyglądać następująco:

2 ... 2^2 ... 2^3 ... 2^5 ... 2^7 ... etc.

W ten sposób uzyskujemy liczby pierwsze. To jest OEIS A007542 .

Wyzwanie

Biorąc pod uwagę liczbę wejściową n, zero lub jedną indeksowaną (do wyboru), albo wypisz pierwsze nliczby z tej sekwencji, albo nwypisz numer th tej sekwencji.

Przykłady

Poniższe przykłady przedstawiają ntermin th sekwencji o indeksie zerowym.

 n   output
 5   2275
19   4
40   408

Zasady

• Jeśli ma to zastosowanie, możesz założyć, że wejście / wyjście będzie pasować do rodzimego typu Integer w twoim języku.
• Dane wejściowe i wyjściowe można podać dowolną dogodną metodą .
• Dopuszczalny jest pełny program lub funkcja. Jeśli funkcja, możesz zwrócić dane wyjściowe zamiast je drukować.
• Standardowe luki są zabronione.
• To jest golf golfowy, więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach).

Python 3 , 173 165 153 145 144 136 135 127 126 125 108 107 104 bajtów

f=lambda n:2>>n*2or[f(n-1)*t//d for t,d in zip(b"NM_M\r7",b"[U3&!\r")if f(n-1)*t%d<1][0]

Wypróbuj online!

• -30 bajtów dzięki Jonathanowi Frechowi!
• -3 bajty dzięki Lynn!

2>>n*2jest 2za n==0i 0inaczej.

103 bajty, jeśli możemy zwrócić liczby zmiennoprzecinkowe.

FRACTRAN , 99 bajtów

17/2821 78/2635 19/1581 23/1178 29/1023 77/899 95/713 77/589 1/527 11/403 13/341 15/434 15/62 55/31

Wypróbuj online!

Program przyjmuje 2*31^njako dane wejściowe, które są używane jako stan początkowy.

Wszystkie frakcje w oryginalnym programie FRACTRAN zostały podzielone przez 31 (pierwszy nieużywany rejestr główny), więc program zatrzymuje się na n-tej iteracji.

Galaretka , 49 43 bajtów

ד×NŒçøM_M¢¿ÆÐÐ7‘“[U3&!øçŒ×Æ¿Ç£¢‘:@xḍɗḢ
2Ç¡

Wypróbuj online!

• -6 bajtów dzięki milom

Python 3 , 107 bajtów

f=lambda n,k=2:n and f(n-1,[k*a//b for a,b in zip(b"NM_M\r7",b"[U3&!\r")if k*a%b<1][0])or k

Wypróbuj online!

Koduje listę ułamków poprzez wprowadzenie zipdwóch bajtów zawierających niedrukowalne znaki o niskim ASCII.

Jeśli nwynosi zero, zwracamy argument k; w przeciwnym razie powracamy z nowymi parametrami. Nasza nowa kto pierwsza wartość k*a//bodpowiadająca pewnej części ułamkowej (a, b)na liście, takiej k*a//bjak liczba całkowita, tj k*a%b<1.

MATL , 50 bajtów

Hi:"'0m26<l~l *,..V'31-*'{uSFA=731-+."!'32-&\w~)1)

Wypróbuj online!

J , 116 110 bajtów

g=.3 :0
((1047856500267924709512946135x%&(96#.inv])5405040820893044303890643137x)([:({.@I.@(=<.){[)*)])^:y 2
)

Wypróbuj online!

0-indeksowane; zwraca n-tą liczbę

Niektóre bajty można zapisać, czyniąc czasownik milczącym, ale mam problemy z ^:działaniem.

Wyjaśnienie:

J opisuje liczby wymierne w postaci NrD, gdzie N jest licznikiem, a D jest mianownikiem, na przykład 17r91 78r85 19r51 23r38...stworzyłem 2 osobne listy dla liczników i mianowników i utworzyłem z nich 2 liczby podstawowe 96.

1047856500267924709512946135x%&(96#.inv])5405040820893044303890643137x konwertuje liczby podstawowe-96 na listy i konstruuje listę ułamków, dzieląc dwie listy.

   1047856500267924709512946135x%&(96#.inv])5405040820893044303890643137x
17r91 78r85 19r51 23r38 29r33 77r29 95r23 77r19 1r17 11r13 13r11 15r14 15r2 55

2 zacznij od 2

^:ypowtórz czasownik po jego lewej stronie n(y jest argumentem funkcji)

] właściwy argument (zaczyna się od 2, a następnie wykorzystuje wynik każdej iteracji)

* pomnóż listę ułamków przez odpowiedni argument

(=<.) są liczbami całkowitymi wyników (porównaj każdą liczbę z jej podłogą)

{.@I.@znajduje indeks I.pierwszej {.z liczb całkowitych

{[ używa indeksu do pobrania numeru

05AB1E ,  44  43 bajty

0-indeksowane

2sF•Ë₁ǝßÌ?ƒ¥"h2ÔδD‡béαA5À>,•тв2ä`Š*s‰ʒθ_}нн

Wypróbuj online!

Wyjaśnienie

2                                             # initialize stack with 2
 sF                                           # input times do:
   •Ë₁ǝßÌ?ƒ¥"h2ÔδD‡béαA5À>,•                  # push a base-255 compressed large number
                            тв                # convert to a list of base-100 digits
                              2ä`             # split in 2 parts to stack
                                 Š            # move denominators to bottom of stack
                                  *           # multiply the last result by the numerators
                                   s‰         # divmod with denominators
                                     ʒθ_}     # filter, keep only those with mod result 0
                                         нн   # get the div result

Pchnięta jest duża liczba 17781923297795770111131515559185513833292319171311140201

Pari / GP , 121 bajtów

n->a=2;for(i=1,n,a=[x|x<-a*[17/91,78/85,19/51,23/38,29/33,77/29,95/23,77/19,1/17,11/13,13/11,15/14,15/2,55],x\1==x][1]);a

Wypróbuj online!

JavaScript (Node.js) , 106 95 bajtów

• dzięki @Arnauld i @Neil za zmniejszenie o 11 bajtów

(n,N=2,I=13,B=Buffer(`[U3&!\rNM_M\r7`))=>n--?f(n,N/B.find(x=>N%x<!!++I)*B[I]):N

Wypróbuj online!

Retina , 213 bajtów

K`17/91¶78/85¶19/51¶23/38¶29/33¶77/29¶95/23¶77/19¶1/17¶11/13¶13/11¶15/2¶1/7¶55/1¶17/91¶78/85¶19/51¶23/38¶29/33¶77/29¶95/23¶77/19¶1/17¶11/13¶13/11¶15/2¶1/7¶55/1¶2
\d+
*
"$+"+`((_+)/(_+)¶(.+¶)*)(\3)+$
$1$#5*$2
r`_\G

Wypróbuj online! Wyjaśnienie:

K`17/91¶78/85¶19/51¶23/38¶29/33¶77/29¶95/23¶77/19¶1/17¶11/13¶13/11¶15/2¶1/7¶55/1¶17/91¶78/85¶19/51¶23/38¶29/33¶77/29¶95/23¶77/19¶1/17¶11/13¶13/11¶15/2¶1/7¶55/1¶2

Zamień dane wejściowe na listę wszystkich ułamków plus początkową liczbę całkowitą.

\d+
*

Przekształć wszystko w jedno.

"$+"+`

Powtórz podstawienie tyle razy, ile podało oryginalne wejście.

((_+)/(_+)¶(.+¶)*)(\3)+$

Znajdź mianownik, który równomiernie dzieli liczbę całkowitą.

$1$#5*$2

Zamień liczbę całkowitą na wynik dzielenia pomnożony przez licznik.

r`_\G

Konwertuj liczbę całkowitą na dziesiętną i wyślij wynik.

Attache , 81 bajtów

Nest<~{Find[Integral,_*&`//=>Chop[Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31,2]]},2~>

Wypróbuj online! Wyprowadza ułamek powyżej 1. Na przykład 5zwraca dane wejściowe 2275/1. Można to naprawić za pomocą 2 bajtów, przygotowując N@program.

Wyjaśnienie

Jest to funkcja curry, która curry Nest z dwoma predefiniowanymi argumentami:

{Find[Integral,_*&`//=>Chop[Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31,2]]}

a 2. Ten ostatni argument jest po prostu początkowym ziarnem, a argumentem przekazywanym do tej funkcji jest liczba iteracji zagnieżdżenia danej funkcji.

Do zakodowania PRIMEGAME służy:

&`//=>Chop[Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31,2]]

Jest to oceniane jako takie:

A> "0zmt2R6E<@l<~6l2 0*,,*.-.!V "
"0zmt2R6E<@l<~6l2 0*,,*.-.!V "
A> Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "
[48, 122, 109, 116, 50, 82, 54, 69, 60, 64, 108, 60, 126, 54, 108, 50, 32, 48, 42, 44, 44, 42, 46, 45, 46, 33, 86, 32]
A> Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31
[17, 91, 78, 85, 19, 51, 23, 38, 29, 33, 77, 29, 95, 23, 77, 19, 1, 17, 11, 13, 13, 11, 15, 14, 15, 2, 55, 1]
A> Chop[Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31,2]
 17 91
 78 85
 19 51
 23 38
 29 33
 77 29
 95 23
 77 19
  1 17
 11 13
 13 11
 15 14
 15  2
 55  1
A> &`//=>Chop[Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31,2]
[(17/91), (78/85), (19/51), (23/38), (29/33), (77/29), (95/23), (77/19), (1/17), (11/13), (13/11), (15/14), (15/2), (55/1)]

Zastąpmy to wyrażenie Gw objaśnieniu. Nasza pierwsza funkcja to:

{Find[Integral,_*G]}

Wykonuje to pojedynczą iterację kodu FRACTRAN _na wejściu funkcji. Jest Findto Integralelement (jeden, który jest liczbą całkowitą) tablicy _*G, która jest wejściem _pomnożonym przez każdy element G. Nestpo prostu stosuje tę transformację określoną liczbę razy.

Attache, 42 bajty

Wdrożyłem części $langsbiblioteki, zainspirowane tym wyzwaniem, dlatego zaznaczam tę część jako niekonkurencyjną.

Needs[$langs]2&FRACTRAN_EXAMPLES.prime.run

To po prostu odpytuje listę, FRACTRAN_EXAMPLESktórą mam. Każdy przykład jest FractranExampleinstancją, która wywołuje wbudowaną FRACTRANfunkcję. primePrzykładem jest PRIMEGAME Conwaya.

F # (mono) , 215 bajtów

let q m=
 let rec i x y=
  if y=m then x 
  else[17;91;78;85;19;51;23;38;29;33;77;29;95;23;77;19;1;17;11;13;13;11;15;14;15;2;55;1]|>List.chunkBySize 2|>List.find(fun[n;d]->x*n%d=0)|>fun[n;d]->i(x*n/d)(y+1)   
 i 2 0

Wypróbuj online!

PHP, 183 bajtów (189 ze znacznikiem „php”)

Gra w golfa:

$t=2;for(;@$i++<$argv[1];){foreach([17/91,78/85,19/51,23/38,29/33,77/29,95/23,77/19,1/17,11/13,13/11,15/14,15/2,55/1]as$n){$a=$t*$n;if(preg_match('/^\d+$/',$a)){$t=$a;break;}}}echo$t;

Nie golfowany:

<?php 
$t=2;
for(;@$i++<$argv[1];){
    foreach([17/91,78/85,19/51,23/38,29/33,77/29,95/23,77/19,1/17,11/13,13/11,15/14,15/2,55/1] as $n){
        $a=$t*$n;
        if(preg_match('/^\d+$/',$a)){
            $t=$a;break;
        }
    }
}
echo $t;

Wypróbuj online!