Najwyższe liczby zawsze fascynowały ludzi. 2300 lat temu Euclid napisał w „Elementach”

Liczba pierwsza to liczba mierzona przez samą jednostkę.

co oznacza, że ​​liczba pierwsza jest podzielna tylko przez 1(lub sama).

Ludzie zawsze szukali relacji między liczbami pierwszymi i wymyślali jakieś dziwne (jak w „interesujących”) rzeczach.

Na przykład liczba pierwsza Sophie Germain jest liczbą pierwszą, pdla której 2*p+1jest również liczba pierwsza.

Bezpieczny prime jest podstawowym p, dla którego (p-1)/2jest również pierwszą, która jest dokładnie stan wstecz o sile Sophie Germain.

Są one związane z tym, czego szukamy w tym wyzwaniu.

Cunningham łańcuch typu I jest ciągiem liczb pierwszych, w których każdy element z wyjątkiem ostatniego jeden jest główny Sophie Germain , a każdy element z wyjątkiem pierwszego jest bezpieczny prime . Liczba elementów w tym łańcuchu nazywa się jego długością .

Oznacza to, że zaczynamy od liczby pierwszej pi obliczamy q=2*p+1. Jeśli qjest również liczbą pierwszą, mamy łańcuch Cunnighama typu I o długości 2. Następnie testujemy 2*q+1i tak dalej, aż do wygenerowania kolejnej wygenerowanej liczby.

Łańcuchy Cunninghama typu II są skonstruowane według prawie tej samej zasady, z tą różnicą, że sprawdzamy je 2*p-1na każdym etapie.

Łańcuchy Cunninghama mogą mieć długość 1 , co oznacza, że ​​ani 2 * p + 1, ani 2 * p-1 nie są pierwsze. Nie jesteśmy nimi zainteresowani .

Kilka przykładów łańcuchów Cunninghama

2rozpoczyna łańcuch typu I o długości 5.

2, 5, 11, 23, 47

Następna skonstruowana liczba byłaby liczbą 95pierwszą.
To także mówi nam, że 5, 11, 23a 47nie uruchomić dowolny łańcuch typu I , ponieważ byłoby to elementy poprzedzającego.

2rozpoczyna również łańcuch typu II o długości 3.

2, 3, 5

Dalej byłoby 9, co nie jest liczbą pierwszą.

Spróbujmy 11dla typu II (wcześniej wykluczyliśmy go z typu I ).
Cóż, 21byłby następny, który nie jest liczbą pierwszą, więc mielibyśmy długość 1 dla tego „łańcucha”, którego nie liczymy w tym wyzwaniu.

Wyzwanie

Napisz program lub funkcję, która podając liczbę njako dane wejściowe, zapisuje / zwraca numer początkowy n-tego łańcucha Cunninghama typu I lub II o długości co najmniej 2 , następnie spację, a następnie typ łańcucha, który zaczyna ( I lub II ), a następnie dwukropek, a następnie długość tego typu łańcucha. W przypadku, gdy liczba pierwsza rozpoczyna oba typy łańcuchów (typ I i typ II), łańcuch typu I jest liczony jako pierwszy.

Przykład: 2 I:5

Pamiętaj, że nmoże to być część wcześniej rozpoczętego łańcucha dowolnego typu, w którym to przypadku nie powinna być traktowana jako liczba początkowa łańcucha tego typu.

Zobaczmy, jak to się zacznie

Zaczynamy od 2. Ponieważ jest to pierwsza liczba pierwsza, możemy być pewni, że nie ma łańcucha rozpoczynającego się od dolnej liczby pierwszej zawierającej 2.
Następną liczbą w łańcuchu typu byłbym 2*2+1 == 5. 5jest liczbą pierwszą, więc mamy już łańcuch o długości co najmniej 2.
Liczymy to jako pierwszy łańcuch. Co z typem II? Kolejny numer to 2*2-1 == 3. 3jest liczbą pierwszą, więc łańcuch o długości co najmniej 2 również dla typu II.
Liczymy to jako drugi łańcuch. I gotowe 2.

Następna liczba pierwsza to 3. Tutaj powinniśmy sprawdzić, czy jest w łańcuchu, który rozpoczął niższą liczbę pierwszą.
Sprawdź, typ I: (3-1)/2 == 1. 1nie jest liczbą pierwszą, więc 3 może być punktem wyjścia dla łańcucha typu I.
Sprawdźmy to. Dalej byłoby 3*2+1 == 7. 7jest liczbą pierwszą, więc mamy łańcuch typu I o długości co najmniej 2. Liczymy to jako trzeci łańcuch.
Teraz sprawdzamy, czy 3pojawia się w łańcuchu typu II, który rozpoczął niższą liczbę pierwszą. (3+1)/2 == 2. 2jest liczbą pierwszą, więc 3 nie może być uważane za liczbę początkową dla łańcucha typu II. Nie jest to więc liczone, nawet jeśli będzie to kolejna liczba po 3tym łańcuchu5, jest liczbą pierwszą. (Oczywiście, że już to wiedzieliśmy i możesz i powinieneś oczywiście pomyśleć o własnej metodzie wykonywania tych kontroli).

I tak dla sprawdzenia 5, 7, 11i tak dalej, aż do liczenia znaleźć ntą Cunningham łańcuch o długości minimum 2.

Następnie (a może jakiś czas wcześniej ;)) musimy określić całkowitą długość znalezionego łańcucha i wydrukować wynik we wcześniej wspomnianym formacie.

Nawiasem mówiąc: w moich testach nie znalazłem żadnej 2liczby pierwszej poza tym, że zaczynał oba typy łańcuchów o długości większej niż 1.

Przykłady wejścia / wyjścia

Wejście

1

Wynik

2 I:5

Wejście

10

Wynik

79 II:3

Wejście

99

Wynik

2129 I:2

Wyjścia dla wejść 1..20

2 I: 5
2 II: 3
3 I: 2
7 II: 2
19 II: 3
29 I: 2
31 II: 2
41 I: 3
53 I: 2
79 II: 3
89 I: 6
97 II: 2
113 I: 2
131 I: 2
139 II: 2
173 I: 2
191 I: 2
199 II: 2
211 II: 2
229 II: 2

Lista pierwszych 5000 wyjść znajduje się tutaj .

To jest kod golfowy. W danych wyjściowych dozwolona jest dowolna biała spacja, ale typ i liczby powinny być oddzielone pojedynczą spacją i dwukropkiem, jak pokazano w przykładach. Korzystanie żadnych luk nie jest dozwolone, a zwłaszcza uzyskanie wyników z internetu jest nie dozwolone.

Powodzenia :)

JavaScript, 236 208 bajtów

Zapisano 28 bajtów:

p=(n,i=n)=>n%--i?p(n,i):i==1;f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:`+eval(`for(j=1;p(k=2*k+l);j++);j`))}

Zapisane 9 bajtów pfunkcji z: p=(n,i=n)=>n%--i?p(n,i):i==1
The tfunkcji został zastąpiony przez eval(...)oświadczenie bezpośrednio w ffunkcji.

Poprzednie rozwiązanie:

p=n=>{for(i=n;n%--i&&i;);return 1==i};t=(n,m)=>{for(j=1;p(n=2*n+m);j++);return j};f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:${t(k,l)}`)}

Przykład: f(6)

Wynik: 29 I:2

Wyjaśnienie
Używam 3 funkcji

1 p : wiedzieć, czy n jest liczbą pierwszą: p=n=>{for(i=n;n%--i&&i;);return 1==i}

2) t : znać długość łańcucha Cunninghama zaczynając od n typu I lub II w zależności od parametru m , który będzie wynosił 1 lub -1: t=(n,m)=>{for(j=1;p(n=2*n+m);j++);return j}

3) f : zlicza łańcuchy ( dla pętli ), a następnie wyświetla wynik

f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:${t(k,l)}`)}

dla pętli : dla każdej liczby łańcuch Cunninghama (I, w razie potrzeby II,) jest ważny, jeśli

• liczba jest liczbą pierwszą
• poprzednik nie jest liczbą pierwszą
• następca jest najważniejszy