Zadanie polega na n
znalezieniu najmniejszej liczby pierwszej, rozpoczynającej się od NAJMNIEJ n
liczby 2
na początku liczby. To sekwencja, którą znalazłem w OEIS ( A068103 ).
Pierwsze 17 liczb w sekwencji podano poniżej, jeśli chcesz więcej, będę musiał wdrożyć sekwencję, co nie mam nic przeciwko.
0 = 2
1 = 2
2 = 223
3 = 2221
4 = 22229
5 = 2222203
6 = 22222223 # Notice how 6 and 7 are the same!
7 = 22222223 # It must be **AT LEAST** 6, but no more than necessary.
8 = 222222227
9 = 22222222223 # Notice how 9 and 10 are the same!
10 = 22222222223 # It must be **AT LEAST** 9, but no more than necessary.
11 = 2222222222243
12 = 22222222222201
13 = 22222222222229
14 = 222222222222227
15 = 222222222222222043
16 = 222222222222222221
Pomyślałem, że byłoby to fajne połączenie manipulacji ciągiem, detekcji liczby pierwszej i sekwencji. To jest golf golfowy , najniższa liczba bajtów zostanie ogłoszona zwycięzcą prawdopodobnie pod koniec miesiąca.
x
. Na przykład, jeśli Twój język obsługuje tylko 32-bitowe liczby całkowite, możesz to wyjaśnić.Odpowiedzi:
Brachylog ,
1211 bajtówWypróbuj online!
To zaskakująco bezpośrednio przekłada się na Brachylog. Jest to funkcja, a nie pełny program (chociaż podanie interpretera
Z
jako argumentu wiersza poleceń powoduje, że dodaje on odpowiednie opakowanie, aby przekształcić funkcję w program; to właśnie zrobiłem, aby łącze TIO działało). Jest to również dość niefortunne, żej
wydaje się być indeksowane -1 i wymaga korekty, aby to umożliwić.Możesz uzasadnić argument, że
=
nie jest to konieczne, ale myślę, że biorąc pod uwagę sposób sformułowania problemu, jest on; bez, funkcja opisuje zbiór wszystkich liczb pierwszych, które zaczynają się od podanej liczby2
s, i bez jakiejś wyraźnej instrukcji, że program powinien zrobić coś z tym opisem (w tym przypadku generując pierwszą wartość), prawdopodobnie nie zgodne ze specyfikacją.Wyjaśnienie
Gdy jest używana jako funkcja zwracająca liczbę całkowitą, nic nigdy nie żąda wartości przekraczających pierwszą, więc pierwszą musimy się martwić.
Jedna subtelność (wskazana w komentarzach):
:Acb
ib:Ac
są matematycznie równoważne (jak jedna usuwa się od początku, a druga dodaje do końca, a region pomiędzy nimi nigdy się nie nakłada); Wcześniej miałemb:Ac
, co jest bardziej naturalne, ale psuje się na wejściu 0 (zgaduję, ponieważc
odmawia połączenia pustej listy z czymkolwiek; wiele wbudowanych Brachylog z jakiegoś powodu ma tendencję do łamania się na pustych listach).:Acb
zapewnia, żec
nigdy nie musi widzieć pustej listy, co oznacza, że przypadek wejścia 0 może teraz również działać.źródło
0
bez wyraźnego powodu (Brachylog z jakiegoś powodu wydaje się być uczulony na zera; podejrzewam, żec
jest odpowiedzialny). To powiedziawszy, dość łatwo to naprawić, więc naprawię to teraz.b:Ac
nie działa, ponieważ dla danych wejściowych0
otrzymujesz2b:Ac
:2b
daje0
i nie możesz używaćc
z wiodącym zerem. Powodem tego jest unikanie nieskończonych pętli w ogólnym przypadku, w którym zawsze można było wstawić zero i uzyskać takie same wyniki.:2rj
zamiast,2:?j
r
; to tylko zwykła poprawa. Rozumiem, co się dziejec
(nie chcesz nieskończenie wielu wyników, gdy biegniesz wstecz); jednak prawdopodobną poprawą jest niedopuszczenie zdegenerowanych danych wejściowych tylko wtedy, gdy są one niezwiązane, jednocześnie umożliwiając je, gdy dane wejściowe są już powiązane z wartością zdegenerowaną.Java (OpenJDK 8) ,
164110 bajtówDzięki @FryAmTheEggman za garść bajtów!
Wypróbuj online!
źródło
new String(new char[i]))
tworzy jednoargumentowy ciąg długości równy liczbie. Następnie wyrażenie regularne dopasowuje liczby złożone, sprawdzając, czy powtórzenie zestawu cyfr pasuje do całego łańcucha (w zasadzie podział próbny). Jeśli mam rację, oznacza to, że powinieneś być w stanie zagrać w golfa w drugiej części, a nie mieć?
, dam ci znać, kiedy dojdę do komputera.Pyth, 12 bajtów
W pseudokodzie:
Pętle
lambda
rozpoczynając odT=1
, zwiększając o 1, aż warunek zostanie spełniony. Łańcuch2
s musi być podciągiem od początku łańcucha, tzn. Metoda indeksu musi zwrócić0
. Jeśli podciąg nie zostanie znaleziony, zwraca,-1
co dogodnie jest również zgodne z prawdą, więc nie ma wyjątkowego przypadku.Możesz spróbować online tutaj , ale serwer pozwala tylko na wejście
4
.źródło
Perl, 50 bajtów
49 bajtów kodu +
-p
flaga.Podaj dane wejściowe bez końcowej nowej linii. Na przykład:
To zajmuje chwilę, aby uruchomić liczby większe niż 4, ponieważ testuje każdą liczbę (są 2 testy: pierwszy
/^2{$_}/
sprawdza, czy na początku jest wystarczająca liczba 2, a drugi(1x$\)!~/^1?$|^(11+)\1+$/
sprawdza pierwotność (z bardzo słabymi wynikami)).źródło
Haskell, 73 bajty
Przykład użycia:
f 3
->2221
.Brutalna siła.
[1..n]>>"2"
tworzy listęn
2
s, która jest porównywana z pierwszymin
znakami w reprezentacji ciągu bieżącej liczby pierwszej.źródło
Mathematica, 103 bajty
Nienazwana funkcja przyjmująca nieujemny argument liczby całkowitej
#
i zwracająca liczbę całkowitą. Dosłownie testuje kolejno wszystkie dodatnie liczby całkowite, aż znajdzie taki, który zaczyna się od#
2s i jest liczbą pierwszą. Strasznie wolne dla wejść powyżej 5.poprzedni wynik: Mathematica, 155 bajtów
Mathematica byłaby lepsza do gry w golfa, gdyby nie była tak mocno napisana; musimy jawnie przełączać się między typami liczb całkowitych / list / ciągów.
Dziwnie, ten algorytm działa na listach cyfr , zaczynając od
{2,...,2,1}
. Dopóki nie są to cyfry liczby pierwszej, dodaje jedną cyfrę do ostatniej cyfry, korzystając z reguły{j___,k_}/;!PrimeQ@d@{j,k}:>({j,k+1}
... a następnie ręcznie implementuje przenoszenie jednej do następnej cyfry, o ile dowolna z cyfry równe 10, przy użyciu reguły{a__,b_,10,c___}->{a,b+1,0,c}
... a następnie, jeśli zaszliśmy tak daleko, że ostatni z wiodących2
s zmienił się w a3
, zaczyna od nowa z kolejną cyfrą na końcu, używając reguły{a,b+1,0,c}/.{a:Repeated[2,#-1],3,b:0..}->{a,2,0,b}
. Na/. 23->2
końcu naprawiono specjalny przypadek, w którym dane wejściowe to1
: większość liczb pierwszych nie może się kończyć2
, ale2
może. (Kilka błędów jest wypluwanych na wejściach0
i1
, ale funkcja znajduje właściwą odpowiedź).Ten algorytm jest dość szybki: na przykład na moim laptopie obliczenie, że pierwsza liczba pierwsza zaczyna się od 1000
2
s, zajmuje mniej niż 3 sekundy22...220521
.źródło
Pyth, 17 bajtów
Wydaje się, że nie można rozwiązać tego w
n = 4
Internecie, ale teoretycznie jest to poprawne.Wyjaśnienie
źródło
Perl 6 , 53 bajtów
Spróbuj
Rozszerzony:
źródło
Galaretka , 14 bajtów
Bardzo nieefektywne. Wypróbuj online!
źródło
Pyke, 14 bajtów
Wypróbuj tutaj!
12 bajtów po poprawce błędu i nowej funkcji
Wypróbuj tutaj!
źródło
Sage,
6968 bajtówUżywa generatora do znalezienia pierwszego (a więc najmniejszego) z nieskończenie wielu terminów.
źródło
Japt, 20 bajtów
Przetestuj online! Kończy się w ciągu dwóch sekund na moim komputerze dla wszystkich danych wejściowych do 14, a następnie naturalnie traci precyzję (JavaScript ma tylko całkowitą dokładność do 2 53 ).
Ogromne podziękowania dla @obarakon za pracę nad tym :-)
Wyjaśnienie
W najnowszej wersji Japt może to być 12 bajtów:
Przetestuj online! Kończy się w ciągu pół sekundy na moim komputerze dla wszystkich danych wejściowych do 14.
źródło
2222203
, tylko222223
wkrótce potem2222210
. Nie udaje się również na żadnym wejściu, które wymaga trzech lub więcej dodatkowych cyfr po ciągu2
s, takich jak wejście 15.PHP, 76 bajtów
pobiera dane wejściowe z argumentu wiersza poleceń. Uruchom z
-r
.awaria
źródło
Bash (+ coreutils), 53 bajty
Działa do 2 ^ 63-1 (9223372036854775807) , zajmuje dużo czasu, aby zakończyć dla N> 8.
Grał w golfa
Test
źródło
Python 3, 406 bajtów
kod testowy
wyjście testowe
Zdecydowałem się na szybkość w dość dużym zakresie, zamiast wielkości bajtów. :) Używam deterministycznego testu pierwotności Millera-Rabina, który jest gwarantowany do 3317044064679887385961981 z tym zestawem świadków. Większe liczby pierwsze zawsze pomyślnie przejdą test, ale niektóre kompozyty mogą również przejść, chociaż prawdopodobieństwo jest bardzo niskie. Jednak przetestowałem również liczby wyjściowe dla i> 22 za pomocą programu Pecec i programu faktoryzacji krzywej eliptycznej i wydaje się, że są one pierwsze.
źródło
p()
wezwanie ... OTOH, że byłoby trudno napisać znacznie mniejszy program, który może dać poprawny wynik za I> 20 w ramach drugiego (który nie „oszukiwać” przez wywołanie wbudowany sprawdzanie pierwotności). :)Python 3, 132 bajty
Wszelkie nadzieje na wydajność zostały poświęcone dla mniejszej liczby bajtów.
źródło
Java, 163 bajty
kod testowy
wydajność:
582,5858 milisekund
Objaśnienie: zapętla liczby całkowite i dodaje je jako ciągi do ciągu głównego, który jest danym ciągiem „2”, i sprawdza, czy jest liczbą pierwszą, czy nie.
źródło
isProbablePrime
ma sporadyczne wyniki fałszywie dodatnie . To unieważniłoby odpowiedź, ponieważ istnieją okoliczności, w których zwraca ona niewłaściwą wartość.