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ą, p
dla której 2*p+1
jest również liczba pierwsza.
Bezpieczny prime jest podstawowym p
, dla którego (p-1)/2
jest 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 p
i obliczamy q=2*p+1
. Jeśli q
jest również liczbą pierwszą, mamy łańcuch Cunnighama typu I o długości 2. Następnie testujemy 2*q+1
i 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-1
na 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
2
rozpoczyna łańcuch typu I o długości 5.
2, 5, 11, 23, 47
Następna skonstruowana liczba byłaby liczbą 95
pierwszą.
To także mówi nam, że 5
, 11
, 23
a 47
nie uruchomić dowolny łańcuch typu I , ponieważ byłoby to elementy poprzedzającego.
2
rozpoczyna 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 11
dla typu II (wcześniej wykluczyliśmy go z typu I ).
Cóż, 21
był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ę
n
jako 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 n
moż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
. 5
jest 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
. 3
jest 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
. 1
nie 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
. 7
jest 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 3
pojawia się w łańcuchu typu II, który rozpoczął niższą liczbę pierwszą.
(3+1)/2 == 2
. 2
jest 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 3
tym ł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
, 11
i 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 2
liczby 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 :)
źródło
2
i3
są jedynymi liczbami pierwszymip
, dla których oba2p-1
i2p+1
są liczbami pierwszymi, więc2
to jedyny premier, który rozpoczyna nietrywialne łańcuchy Cunningham obu typów.:)
2
podwójną długością łańcucha większą niż 1. Oto dowód eliminacji.Odpowiedzi:
JavaScript,
236208 bajtówZapisano 28 bajtów:
Zapisane 9 bajtów
p
funkcji z:p=(n,i=n)=>n%--i?p(n,i):i==1
The
t
funkcji został zastąpiony przezeval(...)
oświadczenie bezpośrednio wf
funkcji.Poprzednie rozwiązanie:
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
dla pętli : dla każdej liczby łańcuch Cunninghama (I, w razie potrzeby II,) jest ważny, jeśli
źródło