Jest to sekwencja A054261
p liczbę pierwszą obudowy jest najniższy numer, który zawiera pierwsze liczb pierwszych jak podciągów. Na przykład liczba jest najniższą liczbą zawierającą pierwsze 3 liczby pierwsze jako podciągi, co czyni ją trzecią liczbą przechowującą pierwszą liczbę.
Trywialne jest stwierdzenie, że pierwsze cztery pierwsze liczby przechowujące to , 23 , 235 i 2357 , ale potem staje się bardziej interesujące. Ponieważ następna liczba pierwsza to 11, kolejnym numerem przechowującym nie jest 235711 , ale 112357, ponieważ jest zdefiniowana jako najmniejsza liczba z właściwością.
Jednak prawdziwe wyzwanie pojawia się, gdy przekroczysz 11. Następna główna liczba przechowalni to . Zauważ, że pod tym numerem podciągi 11
i 13
nachodzą na siebie. Liczba 3
pokrywa się również z liczbą 13
.
Łatwo jest udowodnić, że ta sekwencja rośnie, ponieważ następna liczba musi spełniać wszystkie kryteria liczby przed nią i mieć jeszcze jeden podciąg. Jednak sekwencja nie zwiększa się ściśle, jak pokazują wyniki dla n=10
i n=11
.
Wyzwanie
Twoim celem jest znalezienie jak największej liczby podstawowych pojemników. Twój program powinien wypisywać je w uporządkowany sposób, zaczynając od 2 i przechodząc w górę.
Zasady
- Jesteś dozwolone do liczb ciężko kodowych.
- Nie wolno kodować liczb pierwszych zawierających na stałe (
2
jest to jedyny wyjątek) ani żadnych magicznych liczb, które sprawiają, że wyzwanie jest banalne. Proszę bądź miły. - Możesz używać dowolnego języka. Dołącz listę poleceń, aby przygotować środowisko do wykonania kodu.
- Możesz używać zarówno procesora, jak i karty graficznej i możesz używać wielowątkowości.
Punktacja
Oficjalna ocena będzie od mojego laptopa (Dell XPS 9560). Twoim celem jest wygenerowanie jak największej liczby liczb pierwszych w ciągu 5 minut.
Okular
- Intel Core i7-7700HQ 2,8 GHz (doładowanie 3,8 GHz) 4 rdzenie, 8 wątków.
- 16 GB pamięci RAM DDR4 2400 MHz
- NVIDIA GTX 1050
- Linux Mint 18.3 64-bit
Znalezione do tej pory liczby wraz z ostatnią liczbą pierwszą dodaną do liczby:
1 => 2 ( 2)
2 => 23 ( 3)
3 => 235 ( 5)
4 => 2357 ( 7)
5 => 112357 ( 11)
6 => 113257 ( 13)
7 => 1131725 ( 17)
8 => 113171925 ( 19)
9 => 1131719235 ( 23)
10 => 113171923295 ( 29)
11 => 113171923295 ( 31)
12 => 1131719237295 ( 37)
13 => 11317237294195 ( 41)
14 => 1131723294194375 ( 43)
15 => 113172329419437475 ( 47)
16 => 1131723294194347537 ( 53)
17 => 113172329419434753759 ( 59)
18 => 2311329417434753759619 ( 61)
19 => 231132941743475375961967 ( 67)
20 => 2311294134347175375961967 ( 71)
21 => 23112941343471735375961967 ( 73)
22 => 231129413434717353759619679 ( 79)
23 => 23112941343471735359619678379 ( 83)
24 => 2311294134347173535961967837989 ( 89)
25 => 23112941343471735359619678378979 ( 97)
26 => 2310112941343471735359619678378979 (101)
27 => 231010329411343471735359619678378979 (103)
28 => 101031071132329417343475359619678378979 (107)
29 => 101031071091132329417343475359619678378979 (109)
30 => 101031071091132329417343475359619678378979 (113)
31 => 101031071091131272329417343475359619678378979 (127)
32 => 101031071091131272329417343475359619678378979 (131)
33 => 10103107109113127137232941734347535961967838979 (137)
34 => 10103107109113127137139232941734347535961967838979 (139)
35 => 10103107109113127137139149232941734347535961967838979 (149)
36 => 1010310710911312713713914923294151734347535961967838979 (151)
Dzięki Ardnauld, Ourous i japh za rozszerzenie tej listy.
Zauważ, że n = 10
i n = 11
są tym samym numerem, ponieważ jest najniższą liczbą, która zawiera wszystkie liczby , ale zawiera także .
Dla porównania możesz użyć faktu, że oryginalny skrypt Pythona, który napisałem w celu wygenerowania powyższej listy, oblicza pierwsze 12 terminów w około 6 minut.
Dodatkowe zasady
Po pojawieniu się pierwszych wyników zdałem sobie sprawę, że istnieje duża szansa, że najlepsze wyniki mogą mieć ten sam wynik. W przypadku remisu zwycięzcą będzie ten, który ma najkrótszy czas na wygenerowanie swojego wyniku. Jeśli dwie lub więcej odpowiedzi da równie szybkie wyniki, będzie to po prostu zwycięstwo w remisie.
Ostatnia uwaga
5-minutowy czas pracy jest zapewniany tylko w celu zapewnienia uczciwej punktacji. Byłbym bardzo zainteresowany zobaczeniem, czy możemy popchnąć dalej sekwencję OEIS (teraz zawiera ona 17 liczb). Dzięki kodowi Ourous wygenerowałem wszystkie liczby do n = 26
, ale planuję pozwolić, aby kod działał przez dłuższy czas.
Tablica wyników
- Python 3 + Google OR-Tools : 169
- Scala : 137 (nieoficjalnie)
- Concorde TSP solver : 84 (nieoficjalny)
- Zestaw C ++ (GCC) + x86 : 62
- Czyste : 25
- JavaScript (Node.js) : 24
źródło
n=11
trywialne jest proste, ponieważ musisz tylko sprawdzić, czyn=10
spełnia on również nowy warunek. Twierdziłbym również, że kodowanie na stałe pomaga tylko do momentun=17
, gdy nie znam liczb poza tym punktem, o ile udało mi się to ustalić.[1,22,234,2356,112356,113256,1131724,113171924,1131719234,113171923294,113171923294,1131719237294]
Odpowiedzi:
Python 3 + Google OR-Tools , wynik 169 w 295 sekund (oficjalny wynik)
Jak to działa
Po odrzuceniu zbędnych liczb pierwszych zawartych w innych liczbach pierwszych narysuj skierowany wykres z krawędzią od każdej liczby pierwszej do każdego z jej przyrostków, z odległością zero, i krawędzią do każdej liczby pierwszej z każdego z jej prefiksów, z odległością określoną przez liczbę dodanych cyfr . Szukamy leksykograficznie pierwszej najkrótszej ścieżki przez wykres, zaczynając od pustego prefiksu, przechodząc przez każdą liczbę pierwszą (ale niekoniecznie przez każdy prefiks lub sufiks), a kończąc na pustym sufiksie.
Na przykład, oto krawędzie optymalnej ścieżki ε → 11 → 1 → 13 → 3 → 31 → 1 → 17 → ε → 19 → ε → 23 → ε → 29 → ε → 5 → ε dla n = 11, odpowiadające na łańcuch wyjściowy 113171923295.
W porównaniu z prostą redukcją problemu podróżującego sprzedawcy , zauważ, że łącząc liczby pośrednie przez te dodatkowe węzły sufiksów / prefiksów, zamiast bezpośrednio ze sobą, znacznie zmniejszyliśmy liczbę krawędzi, które musimy wziąć pod uwagę. Ale ponieważ dodatkowe węzły nie muszą być przemierzane dokładnie raz, nie jest to już instancja TSP.
Używamy przyrostowego narzędzia do rozwiązywania ograniczeń CP-SAT Google OR-Tools, najpierw w celu zminimalizowania całkowitej długości ścieżki, a następnie w celu zminimalizowania każdej grupy dodanych cyfr w kolejności. Inicjalizujemy model tylko z lokalnymi ograniczeniami: każda liczba pierwsza poprzedza jeden sufiks i zastępuje jeden prefiks, podczas gdy każda liczba pierwsza / prefiks poprzedza tę samą liczbę liczb pierwszych. Powstały model może zawierać rozłączone cykle; jeśli tak, dynamicznie dodajemy dodatkowe ograniczenia łączności i ponownie uruchamiamy solver.
Kod
Wyniki
Oto pierwsze 1000 liczb pierwszych przechowujących , obliczonych w 1½ dni w systemie 8-rdzeniowym / 16-wątkowym.
źródło
Zestaw C ++ (GCC) + x86, wynik
323662 w 259 sekund (oficjalny)Wyniki obliczone do tej pory. W moim komputerze zabrakło pamięci
65
.Wszystkie one zgadzają się z wynikami solvera opartego na Concorde , więc mają duże szanse na poprawność.
Dziennik zmian:
Błędne obliczenia dla potrzebnej długości kontekstu. Wcześniejsza wersja była o 1 za duża i zawierała błąd. Wynik:
3234Dodano optymalizację grup równych kontekstów. Wynik:
3436Zmieniono algorytm, aby poprawnie używać ciągów bezkontekstowych, a także kilka innych optymalizacji. Wynik:
3662Dodano poprawny opis.
Dodano wariant liczb pierwszych.
Jak to działa
Ostrzeżenie: jest to zrzut mózgu. Przewiń do końca, jeśli chcesz tylko kod.
Skróty:
Ten program zasadniczo wykorzystuje podręcznikowy algorytm programowania dynamicznego dla TSP.
To dużo potencjalnych błędów. Po zabawie z wejściem anselma i nieumiejętności wyciągnięcia z tego niewłaściwych wyników, powinienem przynajmniej udowodnić, że moje ogólne podejście jest prawidłowe.
Chociaż rozwiązanie oparte na Concorde jest (znacznie, znacznie) szybsze, opiera się na tej samej redukcji, więc to wyjaśnienie dotyczy obu. Dodatkowo to rozwiązanie można dostosować do OEIS A054260 , sekwencji pierwszych zawierającej liczby pierwsze; Nie wiem, jak skutecznie to rozwiązać w ramach TSP. To wciąż jest trochę istotne.
Redukcja TSP
Zacznijmy od udowodnienia, że redukcja do TSP jest poprawna. Powiedzmy, że mamy zestaw ciągów
i chcemy znaleźć najmniejszy superstrun, który zawiera te przedmioty.
Wystarczy znać długość
W przypadku PCN, jeśli istnieje wiele najkrótszych ciągów, musimy zwrócić najmniejszy leksykograficznie. Ale przyjrzymy się innemu (i łatwiejszemu) problemowi.
Jeśli potrafimy rozwiązać SCS-Length, możemy zrekonstruować najmniejsze rozwiązanie i uzyskać PCN. Jeśli wiemy, że najmniejsze rozwiązanie zaczyna się od naszego przedrostka, staramy się go rozszerzyć, dodając każdy element w kolejności leksykograficznej i rozwiązując ponownie długość. Kiedy znajdziemy najmniejszy element, dla którego długość rozwiązania jest taka sama, wiemy, że musi to być następny element w najmniejszym rozwiązaniu (dlaczego?), Więc dodaj go i powtórz na pozostałych elementach. Ta metoda osiągnięcia rozwiązania nazywa się samoczynną redukcją .
Zwiedzanie wykresu maksymalnego nakładania się
Załóżmy, że zaczęliśmy ręcznie rozwiązywać SCS dla powyższego przykładu. Prawdopodobnie:
13
a37
ponieważ są już podciągami innych przedmiotów. Każde rozwiązanie, które zawiera137
, na przykład, musi również zawierać13
i37
.113,137 → 1137
,211,113 → 2113
itpTo jest właściwie słuszne, ale udowodnijmy to dla kompletności. Weź dowolne rozwiązanie SCS; na przykład najkrótszy superstring dla
A
toi można go rozłożyć na konkatenację wszystkich elementów w
A
:(Ignorujemy zbędne elementy
13, 37
.) Zauważ, że:Pokażemy, że każdy najkrótszy superstrun można rozłożyć w następujący sposób:
Dla każdej pary sąsiadujących elementów
x,y
,y
zaczyna się i kończy w późniejszych pozycjach niżx
. Jeśli nie jest to prawdą, to albox
jest podciągiem,y
albo odwrotnie. Ale już usunęliśmy wszystkie elementy, które są podciągami, więc tak się nie stanie.Załóżmy, że sąsiednie elementy w sekwencji mają mniej niż maksymalne nakładanie się, np.
21113
Zamiast2113
. Ale to sprawiłoby, że byłoby to1
zbędne. Żaden późniejszy element nie potrzebuje inicjału1
(jak w 2 1 113), ponieważ występuje wcześniej niż113
, a wszystkie elementy, które pojawiają się później,113
nie mogą zaczynać się cyfrą wcześniej113
(patrz punkt 1). Podobny argument zapobiega wykorzystaniu ostatniego dodatkowego1
(jak w 211 1 3) dowolnego elementu wcześniej211
. Ale nasz najkrótszy superstrun z definicji nie będzie zawierał zbędnych cyfr, więc takie nie maksymalne nakładanie się nie wystąpi.Dzięki tym właściwościom możemy przekonwertować dowolny problem SCS na TSP:
x
,y
należy dodać od krawędzix
doy
którego ciężar jest liczbą dodatkowych symboli dodanych przez dodaniey
dox
jej maksymalna nakładania. Na przykład dodalibyśmy krawędź od211
do113
o wadze 1, ponieważ dodajemy jeszcze2113
jedną cyfrę211
. Powtórz dla krawędzi ody
dox
.Każda ścieżka na tym wykresie, od początkowego prefiksu, odpowiada maksymalnemu nakładaniu się wszystkich elementów na tej ścieżce, a całkowita waga ścieżki jest równa długości połączonego łańcucha. Dlatego każda trasa o najniższej wadze, która odwiedza wszystkie przedmioty przynajmniej raz, odpowiada najkrótszemu superstrunowi.
I to jest redukcja z SCS (i SCS-Length) do TSP.
Algorytm programowania dynamicznego
Jest to klasyczny algorytm, ale zmodyfikujemy go nieco, więc oto krótkie przypomnienie.
(Napisałem to jako algorytm SCS-Length zamiast TSP. Są one zasadniczo równoważne, ale słownictwo SCS pomaga, gdy dochodzimy do optymalizacji specyficznych dla SCS.)
Wywołaj zestaw elementów wejściowych
A
i podany prefiksP
. Dla każdegok
-elementowe podzbioruS
wA
, i każdy elemente
zS
, możemy obliczyć długość najkrótszego łańcucha zaczyna sięP
zawiera wszystkoS
, a kończy sięe
. Obejmuje to przechowywanie tabeli od wartości(S, e)
do ich długości SCS.Kiedy dojdziemy do każdego podzbioru
S
, tabela musi już zawierać wynikiS - {e}
dla wszystkiche
wS
. Ponieważ tabela może być dość duża, obliczyć wyniki dla wszystkichk
-elementowe podzbiory, a następniek+1
, itp W tym celu musimy tylko do przechowywania wyników dlak
ik+1
w dowolnym czasie. Zmniejsza to zużycie pamięci około z grubszasqrt(|A|)
.Jeszcze jeden szczegół: zamiast obliczać minimalną długość SCS, faktycznie obliczam maksymalne całkowite nachodzenie na siebie elementów. (Aby uzyskać SCS-Length, wystarczy odjąć całkowite nakładanie się od sumy długości elementów.) Korzystanie z nakładek pomaga w niektórych z następujących optymalizacji.
[2.] Konteksty przedmiotów
Kontekst jest najdłuższym sufiksem od przedmiotu, który może pokrywać się z następujących elementów. Jeśli nasze produkty są
113,211,311
, to11
jest kontekst dla211
i311
. (Jest to także kontekst prefiksu113
, na który przyjrzymy się w części [4.])W powyższym algorytmie DP śledziliśmy rozwiązania SCS kończące się na każdym elemencie, ale tak naprawdę nie obchodzi nas, na którym elemencie kończy się SCS. Wszystko, co musimy wiedzieć, to kontekst. Zatem na przykład, jeśli dwa SCS dla tego samego zestawu kończą się na
23
i43
, każdy SCS, który kontynuuje z jednego, będzie również działał dla drugiego.Jest to znacząca optymalizacja, ponieważ nietrywialne liczby pierwsze kończą się tylko cyframi
1 3 7 9
. Cztery jednocyfrowe konteksty1,3,7,9
(plus pusty kontekst) są w rzeczywistości wystarczające do obliczenia PCN dla liczb pierwszych do131
.[3.] Elementy bezkontekstowe
Inni już zauważyli, że wiele liczb pierwszych zaczyna się od cyfr
2,4,5,6,8
, takich jak23,29,41,43...
. Żaden z nich nie może się pokrywać z poprzedniej sile (oprócz2
a5
, liczby pierwsze nie można zakończyć w tych cyfr,2
i5
będzie już zostały usunięte jako zbędny). W kodzie są one nazywane ciągami bezkontekstowymi .Jeśli nasze dane wejściowe zawierają elementy kontekstowe, każde rozwiązanie SCS można podzielić na bloki
a nakładki w każdym bloku są niezależne od innych bloków. Możemy tasować bloki lub zamieniać elementy między blokami o tym samym kontekście, bez zmiany długości SCS.
Tak więc musimy tylko śledzić możliwe wielokrotne konteksty, po jednym dla każdego bloku.
Pełny przykład: dla liczb pierwszych mniejszych niż 100 mamy 11 pozycji bezkontekstowych i ich konteksty:
Nasz początkowy kontekst wielosetowy:
Kod nazywa je połączonymi kontekstami lub kontekstami . Następnie musimy wziąć pod uwagę tylko podzbiory pozostałych elementów:
[4.] Łączenie kontekstu
Gdy dojdziemy do liczb pierwszych z 3 cyframi lub więcej, jest więcej zwolnień:
Grupy te mają te same konteksty początkowy i końcowy (zwykle - zależy to od tego, które inne liczby pierwsze są na wejściu), więc są nierozróżnialne, gdy nakładają się na inne elementy. Dbamy tylko o nakładanie się, więc możemy traktować liczby pierwsze w tych grupach o równym kontekście jako nierozróżnialne. Teraz nasze podzbiory DP są skondensowane w wiele podzbiorów
(Z tego powodu solver maksymalizuje długość nakładania się zamiast minimalizować długość SCS: ta optymalizacja zachowuje długość nakładania się.)
Podsumowanie: optymalizacje wysokiego poziomu
Uruchomienie z
INFO
wyjściem debugowania spowoduje wydrukowanie statystyk takich jakTa konkretna linia dotyczy SCS-Length pierwszych 62 liczb pierwszych,
2
do293
.1,3,7,11,13,27
plus pusty ciąg.43,47,53,59,61,89,211,223,227,229,241,251,257,263,269,281,283
. Te i podany przedrostek (w tym przypadku pusty ciąg znaków) stanowią podstawę początkowego połączonego kontekstu .N_search
) znajduje się 16 nietrywialnych grup o równym kontekście .Wykorzystując te struktury, obliczanie długości SCS musi sprawdzić tylko 8498336
(multiset, ccontext)
kombinacji. Proste programowanie dynamiczne wymagałoby43×2^43 > 3×10^14
kroków, a brutalne wymuszanie permutacji -6×10^52
kroków. Program nadal musi uruchamiać SCS-Length jeszcze kilka razy, aby zrekonstruować rozwiązanie PCN, ale to nie trwa długo.[5., 6.] Optymalizacje niskiego poziomu
Zamiast wykonywania operacji na łańcuchach, solver SCS-Length pracuje z indeksami pozycji i kontekstów. Obliczam również nakładanie się między każdą kontekstem i parą elementów.
Kod początkowo używał GCC
unordered_map
, które wydają się być tablicą skrótów z połączonymi segmentami list i głównymi rozmiarami skrótów (tj. Drogimi podziałami). Napisałem więc własną tabelę skrótów z sondowaniem liniowym i potęgą dwóch rozmiarów. Zapewnia to 3-krotne przyspieszenie i 3-krotne zmniejszenie pamięci.Każdy stan tabeli składa się z wielu elementów, połączonego kontekstu i liczby nakładania się. Są one pakowane w 128-bitowe wpisy: 8 dla liczby nakładania się, 56 dla zbioru wielosetowego (jako zestaw bitów z kodowaniem długości przebiegu) i 64 dla kontekstu kontekstowego (rozdzielany 1-RLE). Kodowanie i dekodowanie ccontext było najtrudniejszą częścią i skończyło się na tym, że użyłem nowej
PDEP
instrukcji (jest tak nowa, że GCC nie ma jeszcze w sobie żadnej wewnętrznej).Wreszcie dostęp do tabeli skrótów jest naprawdę powolny, gdy
N
staje się duży, ponieważ tabela nie mieści się już w pamięci podręcznej. Ale jedynym powodem, dla którego piszemy do tabeli skrótów, jest aktualizacja najbardziej znanej liczby nakładania się dla każdego stanu. Program dzieli ten krok na kolejkę pobierania wstępnego, a wewnętrzna pętla poprzedza każdą tabelę wyszukując kilka iteracji przed faktyczną aktualizacją tego gniazda. Kolejne 2-krotne przyspieszenie na moim komputerze.Bonus: dalsze ulepszenia
AKA Jak Concorde jest tak szybki?
Nie znam się dużo na algorytmach TSP, więc tutaj jest ogólne przypuszczenie.
Concorde używa metody rozgałęziania do rozwiązywania TSP.
Oczywiste pomysły, które moglibyśmy wypróbować:
Jednak kombinacja rozgałęzień i cięć jest bardzo potężna, więc możemy nie być w stanie pokonać najnowocześniejszego solvera takiego jak Concorde, dla dużych wartości
N
.Premia premiowa: główne prime przechowujące
W przeciwieństwie do rozwiązania opartego na Concorde, program ten można zmodyfikować, aby znaleźć najmniejsze zawierające liczby pierwsze ( OEIS A054260 ). Wymaga to trzech zmian:
Zmodyfikuj kod solwera SCS-Length, aby kategoryzować rozwiązania na podstawie tego, czy ich sumy cyfr są podzielne przez 3. Obejmuje to dodanie kolejnego wpisu, cyfry mod 3 do każdego stanu DP. To znacznie zmniejsza szanse, że główny solver utknie z permutacjami innymi niż pierwotne. Jest to zmiana, której nie mogłem wymyślić, jak przetłumaczyć na TSP. Można go zakodować za pomocą ILP, ale wtedy musiałbym dowiedzieć się o tej rzeczy zwanej „nierównościami subtour” i jak je wygenerować.
Może się zdarzyć, że wszystkie najkrótsze PCN są podzielne przez 3. W takim przypadku najmniejsza liczba pierwsza przechowująca musi być przynajmniej o jedną cyfrę dłuższa niż PCN. Jeśli nasz solver SCS-wykryje to, kod rekonstrukcji rozwiązania ma opcję dodania jednej dodatkowej cyfry w dowolnym momencie procesu. Próbuje dodać każdą możliwą cyfrę
0..9
i każdy pozostały element do bieżącego prefiksu rozwiązania, w kolejności leksykograficznej, jak poprzednio.Dzięki tym zmianom mogę uzyskać rozwiązania do
N=62
. Z wyjątkiem sytuacji47
, w której kod rekonstrukcji zacina się i poddaje po 1 milionie kroków (jeszcze nie wiem dlaczego). Najważniejsze liczby pierwsze to:Kod
Połącz z
W przypadku wersji z liczbą pierwszą należy również połączyć się z GMPlib, np
Ten program korzysta z instrukcji PDEP, która jest dostępna tylko w najnowszych procesorach x86 (Haswell +). Obsługują go zarówno mój komputer, jak i maxb. Jeśli nie, program skompiluje się w wolnej wersji oprogramowania. Ostrzeżenie to zostanie wydrukowane, gdy to nastąpi.
Wypróbuj online!
I jedyna w swoim rodzaju wersja na TIO . Przepraszam, ale nie grałem w golfa w tych programach i istnieje limit długości postu.
źródło
debug_dummy
możesz użyć#define DEBUG(x) void(0)
.debug_dummy
ponieważ chcę, aby argumenty były sprawdzane i oceniane pod kątem typu, nawet gdy debugowanie jest wyłączone.N=32
myślę, że potrzebuje tylko około 500 MB.main
, ale znalazłem go z linku TIO.JavaScript (Node.js) , zdobądź 24 w 241 sekund
Wyniki
Algorytm
Jest to wyszukiwanie rekurencyjne, które wypróbowuje wszystkie możliwe sposoby łączenia liczb i ostatecznie sortuje wynikowe listy w kolejności leksykograficznej, gdy osiągnięty zostanie węzeł liścia.
Na początku każdej iteracji każdy wpis, który można znaleźć w innym wpisie, jest usuwany z listy.
Znaczące przyspieszenie osiągnięto dzięki śledzeniu odwiedzanych węzłów, dzięki czemu możemy wcześnie przerwać, gdy różne operacje prowadzą do tej samej listy.
Niewielkie przyspieszenie zostało osiągnięte poprzez aktualizację i przywracanie listy, gdy to możliwe, zamiast generowania kopii, jak sugeruje
anonimowy użytkownikNeil.Przykład
Kod
Wypróbuj online!
źródło
Concorde TSP solver , zdobądź 84 w 299 sekund
Cóż… Czuję się głupio, że dopiero teraz to zrozumiałem.
Cała ta sprawa jest w zasadzie problemem podróżnego sprzedawcy . Dla każdej pary liczb pierwszych
p
iq
dodaj krawędź, której waga to liczba cyfr dodanych przezq
(usunięcie nakładających się cyfr). Dodaj także początkową krawędź do każdejp
liczby pierwszej , której waga to długośćp
. Najkrótsza podróżna ścieżka sprzedawcy odpowiada długości najmniejszego podstawowego numeru przechowalni.Następnie solver TSP klasy przemysłowej, taki jak Concorde , szybko poradzi sobie z tym problemem.
Ten wpis należy prawdopodobnie uznać za niekonkurujący.
Wyniki
Solver osiąga
N=350
około 20 godzin procesora. Pełne wyniki są za długie dla jednego posta SE, a OEIS i tak nie chce tak wielu terminów. Oto pierwsze 200:Kod
Oto skrypt w języku Python 3, który w kółko wywołuje solver Concorde, dopóki nie skonstruuje rozwiązań.
Concorde jest bezpłatny do użytku akademickiego. Możesz pobrać wykonywalny plik binarny Concorde zbudowany z własnego pakietu programowania liniowego QSopt, lub jeśli masz licencję na IBM CPLEX, możesz zbudować Concorde ze źródła, aby korzystać z CPLEX.
źródło
Czyste , zdobądź 25 w 231 sekund (oficjalny wynik)
Wyniki
1 < n <= 23
w4236 sekund na TIOn = 24 (2311294134347173535961967837989)
lokalnie w3224 sekundyn = 25 (23112941343471735359619678378979)
lokalnie w210160 sekundn = 1
abyn = 25
stwierdzono w 231 sekund na oficjalnej punktacji (edytowany przez maxb)Wykorzystuje to podobne podejście do rozwiązania JS firmy Arnauld, oparte na rekurencyjnym odrzucaniu permutacji, przy użyciu wyspecjalizowanego zestawu drzew w celu uzyskania dużej prędkości.
Dla każdej liczby pierwszej, która musi zmieścić się w liczbie:
Następnie, dla każdej pary podciągów, które dołączyliśmy, usuń wszelkie podciągi tej połączonej pary z listy podciągów i powtórz na niej.
Gdy już więcej podłańcuchów nie będzie można połączyć z innymi podciągami na żadnym ramieniu naszej rekurencji, używamy już zamówionego zestawu drzew, aby szybko znaleźć najniższą liczbę zawierającą podłańcuchy.
Co należy poprawić / dodać:
Nastąpiły znaczne spadki wydajności pomiędzy
19 -> 20
i z24 -> 25
powodu duplikacji obsługi przez etap próbnego scalania i etap odrzucania kandydata, ale zostały one naprawione.Optymalizacje:
removeOverlap
jest zaprojektowany, aby zawsze podawać zestaw podciągów już w optymalnej kolejnościuInsertMSpec
redukuje sprawdzanie, czy jest członkiem i wstawianie nowego członka do jednego zestawu przechodzeniacontainmentNumbersSt
sprawdza, czy poprzednie rozwiązanie działa dla nowego numeruWypróbuj online!
Zapisz
main.icl
i skompiluj za pomocą:clm -fusion -b -IL Dynamics -IL StdEnv -IL Platform main
Spowoduje to utworzenie pliku,
a.out
który należy uruchomić jakoa.out -h <heap_size>M -s <stack_size>M
, gdzie<heap_size> + <stack_size>
jest pamięć, która będzie używana przez program w megabajtach.(Ogólnie ustawiam stos na 50 MB, ale rzadko kiedy programy używają nawet tyle)
źródło
Scala , ocena 137Edytować:
Kod tutaj upraszcza problem.
Dlatego rozwiązanie działa dla wielu danych wejściowych, ale nie dla wszystkich.
Oryginalny post:
Podstawowy pomysł
Prostszy problem
Najpierw generujemy zestaw liczb pierwszych i usuwamy wszystkie, które są już podciągami innych. Następnie możemy zastosować wiele reguł, tzn. Jeśli istnieje tylko jeden ciąg kończący się w sekwencji i tylko jeden zaczynający się od tej samej sekwencji, możemy je scalić. Innym jest to, że jeśli łańcuch zaczyna się i kończy w tej samej sekwencji (jak 101), możemy dopisać go do innego ciągu bez zmiany jego końca. (Reguły te ustępują tylko pod pewnymi warunkami, więc bądź ostrożny, kiedy je stosujesz)
Prawdziwy problem
10103
0
10103
1
Zatem, gdyby reguły powyższego algorytmu były zawsze wystarczające, okazałoby się, że problem nie jest trudny do NP.
findSeq
Wypróbuj online
Kod
Jak zauważył Anders Kaseorg w komentarzach, ten kod może zwracać wyniki nieoptymalne (a więc błędne).
Wyniki
187
188
189
193
źródło
1234
,3423
,2345
, można wygenerować123453423
zamiast optymalnego12342345
.457, 571, 757
(wszystkie liczby pierwsze).findSeq
wróciłbym7574571
po to, ale najkrótsza długość to457571
. Więc twoje podejście bawi się ogniem. Jednak głosowano za śmiałość.