Wojciech Guzicki, Jarosław WróblewskiWojciech GuzickiMarcin Mucha
Treść zadaniaOpracowanieProgram wzorcowy


Gorszy Goldbach


W roku 1742 C. Goldbach w liście do L. Eulera napisał, że jego zdaniem każda liczba całkowita n>5 jest sumą trzech liczb pierwszych (Liczba pierwsza to liczba naturalna n>1, która ma tylko dwa dzielniki naturalne: 1 oraz n.).

Euler odpisał, że jest to równoważne temu, że każda liczba parzysta n ge 4 jest sumą dwóch liczb pierwszych. To jednak nie przybliżyło ich do rozwiązania podstawowego problemu: czy tak jest naprawdę.

Dziś wiemy, że jest tak dla liczb aż do 4 cdot 10^(11) (wiemy też dużo więcej, ale cała hipoteza jest nadal problemem otwartym). Nie będziemy tego sprawdzać, postawimy sobie mniej ambitne zadanie. Okazuje się, że każda liczba naturalna n ge 10 jest sumą różnych nieparzystych liczb pierwszych.

Zadanie

Twoje zadanie polega na napisaniu programu, który:

Takich rozkładów może być wiele. Twój program może znaleźć jakikolwiek z nich.

Wejście

W pierwszym wierszu pliku tekstowego gol.in zapisano jedną dodatnią liczbę całkowitą n,
n le 40
. W każdym z kolejnych n wierszy znajduje się jedna liczba całkowita z przedziału [10,...,2 000 000 000].

Wyjście

Rozkład liczby k musi być zapisany w dwóch wierszach. W pierwszym wierszu należy zapisać jedną liczbę całkowitą m ge 1, będącą liczbą składników rozkładu.

W drugim wierszu należy zapisać, w rosnącej kolejności, m różnych nieparzystych liczb pierwszych, których suma jest równa k, pooddzielanych pojedynczymi odstępami. Rozkłady powinny występować w kolejności zgodnej z kolejnością liczb w pliku wejściowym.

Przykład

Dla pliku wejściowego gol.in
2
59
15
poprawną odpowiedzią jest plik wyjściowy gol.out
5
5 7 11 17 19
3
3 5 7

Rozwiązanie

Istnieje bardzo szybki algorytm pozwalający rozwiązać to zadanie. Wskażemy mianowicie 32 nieparzyste liczby pierwsze o tej własności, że każda dopuszczalna liczba n (tzn. z przedziału [10;2 000 000 000]) będzie sumą niektórych z tych liczb. Pokażemy też dokładnie, jak taki rozkład można znaleźć.

Algorytm, który mamy na myśli, można odczytać z dowodu następującego twierdzenia ogólnego, udowodnionego w 1949 roku przez H. E. Richerta.

Twierdzenie. Każda liczba naturalna n ge 10 jest sumą różnych nieparzystych liczb pierwszych.

Dowód. Najpierw przedstawimy każdą liczbą naturalną n spełniającą nierówności

 10 le n le 46
w postaci sumy różnych nieparzystych liczb pierwszych wybranych spośród liczb 3, 5, 7, 11, 13, 17. A oto te rozkłady:

begin(longtable)[c](...

Tych liczb jest 37. Wybieramy teraz największą liczbę pierwszą nie większą od 37. Będzie to sama liczba 37. Teraz do każdego z otrzymanych 37 rozkładów dołączamy liczbę 37. W ten sposób otrzymamy rozkłady liczb od 10+37=47 do 46+37=83 na sumy różnych nieparzystych liczb pierwszych. Łącznie z otrzymanymi wcześniej rozkładami mamy teraz rozkłady 74 liczb: od 10 do 83.

Wybieramy następną liczbę pierwszą: będzie to największa liczba pierwsza nie większa od 74; w naszym przypadku jest to liczba 73. Dołączamy tę liczbę do każdego z dotychczasowych rozkładów, otrzymując w ten sposób rozkłady wszystkich liczb aż do 83+73=156. Mamy więc rozkłady 147 liczb od 10 do 156.

Wybieramy tym razem największą liczbę pierwszą nie większą od 147, dołączamy ją do znalezionych rozkładów i tak dalej.

Jest to bardzo naturalna metoda postępowania. Powstaje jednak pytanie, czy jest ona zawsze skuteczna. Mianowicie mogłoby się okazać, że kolejna wybrana liczba pierwsza (pamiętamy: wybieramy największą liczbę nie większą od liczby tych liczb, dla których już znaleźliśmy rozkład) jest równa poprzednio wybranej liczbie pierwszej. Inaczej mówiąc, mogłoby się okazać, że za ostatnio wybraną liczbą pierwszą występuje tak wiele liczb złożonych, że nie możemy dobrać odpowiednio kolejnej liczby pierwszej. Okazuje się jednak, że tak nie jest i można tego dowieść. Dowód wymaga jednak skorzystania z bardzo znanego twierdzenia z teorii liczb, tzw. twierdzenia Czebyszewa, które zapewne nie jest znane większości uczniów liceum. W naszym zadaniu jednak dowód twierdzenia nie jest potrzebny. Wystarczy bowiem sprawdzić, że taką liczbę można dobrać zawsze do momentu, gdy uzyskamy rozkłady wszystkich liczb nie większych od 2 miliardów. Przykłady takich liczb pierwszych zawarte są w tabeli 2.

W kolumnie pierwszej podajemy największą dotychczas użytą liczbę pierwszą p. W kolumnie drugiej podajemy przedział liczb, w którym ta liczba p jest użyta jako największa liczba rozkładu (z wyjątkiem pierwszego wiersza). Wreszcie w kolumnie trzeciej podajemy, ile liczb ma już znany rozkład (od 10 do największej liczby, dla której mamy znaleziony rozkład). Ta liczba jest o 9 mniejsza od największej liczby, dla której znamy rozkład.

Zwróćmy jeszcze uwagę na to, że w pierwszym wierszu występuje liczba pierwsza 17 jako największa liczba występująca w rozkładach liczb od 10 do 46. To nie znaczy oczywiście, że występuje ona w każdym z tych rozkładów. Rozkłady liczb od 10 do 46 muszą być brane z tabeli pierwszej.

begin(array)(rcrcr)
...

Teraz już można łatwo napisać algorytm:

Dana jest liczba n ge 10.

Dopóki n>46 powtarzaj

    Znajdź w drugiej kolumnie przedział, do którego należy n.

    Zapamiętaj odpowiadającą mu liczbę p z pierwszej kolumny.

    n:=n-p.

Teraz już n le 46.

Zapamiętaj znajdujące się w tabeli pierwszej liczby pierwsze występujące w rozkładzie n.

Zapamiętane liczby wypisz w kolejności rosnącej.


Powróćmy teraz do dowodu twierdzenia. Oznaczmy przez p największą użytą liczbę pierwszą i przez M największą liczbę, dla której znaleźliśmy rozkład. Niech k będzie liczbą tych liczb, dla których taki rozkład znaleźliśmy. Oczywiście wtedy k=M-9.

Na początku mamy p=17, M=46 i k=37. Zauważmy, że

 k ge 2p.

Niech teraz q będzie największą liczbą pierwszą nie większą od k. Wtedy q>p. Wynika to ze znanego twierdzenia Czebyszewa:

Twierdzenie. Dla każdej liczby naturalnej l ge 2 istnieje liczba pierwsza r taka, że l<r<2l.

Dowód twierdzenia Czebyszewa można znaleźć np. w książkach W. Sierpińskiego Arytmetyka teoretyczna lub Teoria liczb, t. II. Z twierdzenia Czebyszewa wynika, że istnieje nieparzysta liczba pierwsza r taka, że:

 p<r<2p le k.
Liczba q, która jest największą liczbą pierwszą nie większą od k, jest więc większa od p. Teraz do q ostatnich otrzymanych liczb dodajemy q:
displaylines(
(M-q+1...
Otrzymaliśmy rozkłady liczb od M+1 do M+q na sumę różnych liczb pierwszych: liczba q jest bowiem większa od wszystkich dotychczas użytych liczb pierwszych. Oczywiście również M+q>M.

Połóżmy teraz

M_1=M+q, quad p_1=q,...
Ponieważ qle k, więc
 2q le k+q = M-9+q=M...
Podstawiamy
 M:=M_1, quad p:=p_1...
i mamy nadal spełniony warunek 2p le k. Możemy więc powtórzyć postępowanie itd.

Ponieważ M1>M, więc za każdym razem dostajemy rozkład co najmniej jednej nowej liczby na sumę różnych nieparzystych liczb pierwszych, co dowodzi, że każda liczba n ge 10 ma taki rozkład. To kończy dowód twierdzenia Richerta.

Można podać wiele innych algorytmów rozwiązujących to zadanie. Najprostszy polega na wybieraniu największej liczby pierwszej p nie większej od n i następnie rozwiązaniu zadania dla liczby n-p zamiast n. Ten algorytm nie zawsze prowadzi do sukcesu. Jeśli np. n=27, to wybierzemy liczbę p=23 i wtedy zadanie nie ma rozwiązania dla n-p=4. Możemy jednak próbować zadbać o to, by otrzymana różnica była co najmniej równa 10: wtedy zadanie dla n-p będzie miało rozwiązanie. To daje bardzo prosty algorytm:

    Dana jest liczba n ge 10.

    Dopóki nge 10 powtarzaj

        Znajdź liczbę pierwszą p taką, że (n over 2)<ple n-10.

        Zapamiętaj liczbę p.

        n:=n-p.

    Zapamiętane liczby pierwsze wypisz w kolejności rosnącej.

Warunek (n over 2)<p gwarantuje, że kolejno znajdowane liczby pierwsze będą różne. Mamy bowiem wtedy

 n-p < (n over 2) < ...
a więc następna liczba pierwsza będzie mniejsza od p.

Ten algorytm jednak nie jest poprawny, gdyż nie dla każdej liczby n istnieje liczba pierwsza p taka, że

 (n over 2) < p le n...
Jednak taka liczba pierwsza p istnieje dla odpowiednio dużych liczb n. Niewielka modyfikacja dowodu twierdzenia Czebyszewa daje następujące wzmocnienie tego twierdzenia:

Twierdzenie. Jeśli nge 21, to w przedziale langle n+1;2n rangle istnieje co najmniej 5 liczb pierwszych.

Z tego twierdzenia wynika łatwo następujący wniosek:

Wniosek. Jeśli n>26, to istnieje liczba pierwsza p taka, że

 (n over 2) < p le n...

Zauważmy, że z tego wniosku wynika natychmiast inny dowód twierdzenia Richerta. Przeprowadzenie tego dowodu pozostawimy jako ćwiczenie dla Czytelnika. Możemy też zmodyfikować algorytm, tak by działał poprawnie dla wszystkich n:

    Dana jest liczba n ge 10.

    Dopóki n>26 powtarzaj

        Znajdź liczbę pierwszą p taką, że (n over 2)<ple n-10.

        Zapamiętaj liczbę p.

        n:=n-p

    Teraz już n le 26.

    Zapamiętaj znajdujące się w tabeli pierwszej liczby pierwsze występujące

    w rozkładzie n.

    Zapamiętane liczby pierwsze wypisz w kolejności rosnącej.

Ten algorytm może jednak działać dość długo. Liczby p najlepiej szukać ,,od góry'': po odjęciu liczby p od n dostaniemy liczbę dość małą i teraz już szybko znajdziemy rozkład tej liczby na sumę różnych liczb pierwszych. Warto jednak odnotować fakt, że znane są długie ciągi kolejnych liczb złożonych, tzw. luki. Luka długości k oznacza, że po liczbie pierwszej p, liczby p+1, ..., p+k-1 są złożone i dopiero liczba p+k jest pierwsza. Oczywiście długości luk muszą być liczbami parzystymi. Znane są luki do długości 778 (dla liczb pierwszych p<72635119999997) i niektóre inne. To oznacza, że poszukiwanie największej liczby pierwszej nie większej od n-10 może potrwać dość długo, tym bardziej, że sprawdzanie, czy dana liczba jest pierwsza, też jest czasochłonne.

Najniżej występującą luką długości 100 jest luka między liczbami pierwszymi 396733 i 396833. Ale istnieją większe luki. Najdłuższa znana ma długość 863:

Po liczbie 6 505 941 701 960 039 występują 863 liczby złożone. Ta liczba jest większa od 2 miliardów, ale na przykład po liczbie 166726367 występują 194 liczby złożone. J. Young i A. Potler opublikowali (First occurrence of prime gaps, Math. Comp., 1989, 52, 221-224) tablicę takich luk. Niektóre testy zostały dobrane w taki sposób, by poszukiwanie liczby pierwszej p trwało długo; do tego celu została wykorzystana wspomniana tabela luk (użyto luk długości do 300).

Można jednak zauważyć, że znaleziona liczba pierwsza p jest ,,dobra'' dla wielu liczb n; dokładniej dla liczb n spełniających nierówności

 p+10 le n < 2p.
Można teraz znaleźć taki zbiór skończony liczb pierwszych p, by przedziały [p+10;2p-1] pokrywały cały przedział [10;2 000 000 000]. Jest wiele metod szukania takich zbiorów. Jeden przykład podaliśmy wcześniej. Inny został wykorzystany w programie wzorcowym. Proponujemy Czytelnikowi jako ćwiczenie zastanowienie się, jak ten przykład został znaleziony.

Testy

Do sprawdzenia rozwiązań użyto 11 testów. Test GOL0.IN to test z treści zadania. Następne trzy testy to testy poprawnościowe (odpowiednio dla małych, średniej wielkości i dużych liczb). Następne testy sprawdzały szybkość działania programu i wykorzystywały wspomniane wcześniej luki. Te testy różniły się między sobą wielkością liczb i usytuowaniem luki po to, by sprawdzić różne sposoby szukania liczby pierwszej p mniejszej od n-10.