Milenium z 5 liczbami pierwszymi / Delta 7 (422) 2009, zad. M1246

Zadanie ze strony 10, w Delcie 7 (422) 2009, z działu redagowanego przez Waldemara Pompe:

M 1246. Rozstrzygnąć, czy istnieje 1000 kolejnych liczb naturalnych, wśród których znajduje się dokładnie 5 liczb pierwszych.

Nazwałem kiedyś (w 1975 roku) takie zadania "mood improvers" ("poprawiacze humoru"), gdyż mogą kogoś w pierwszym momencie zintymidować, a po chwili widać proste rozwiązanie. Takie naturalne rozwiązanie podane jest w tymże numerze Delty, na stronie 2 (przekażę je we własnych słowach):

ROZWIĄZANIE: Niech t(n) będzie liczbą liczb pierwszych wśród 1000 kolejnych liczb n ... n+999. Wtedy

• t(n+1) ≥ t(n) - 1 dla każdego n = 1 2 ...
  
• t(1) > 5
• t(1001! + 2) = 0

Wynika stąd istnienie liczby naturalnej n < 1001! + 2 takiej, że t(n) = 5.
KONIEC ROZWIĄZANIA

Elegancja takiego podejścia polega na tym, że nie jest konstruktywne; dowodzimy dokładnie to, o co nas pytają, i nie więcej - nikt nie żądał podania konkretnego n, ani nawet nie wymagał ostrego oszacowania. Ale teraz, skoro już mamy rozwiązanie, to chciałoby się wiedzieć więcej.

Hugo Steinhaus powiedziałby, że 5 oraz 1000 są zmiennymi. Faktycznie, w nastroju serio zajmujemy się wypadkiem ogólnym. Na razie nie dajmy sobie zepsuć zabawy i postarajmy się uzyskać możliwie ostre oszacowania z góry takiego n, żeby t(n) = 5.

Wybrałem oznaczenie "t", by przypominało nam o roli tysiąca, 1000, w naszych rozważaniach; możnaby powiedzieć, że

t = t₁₀₀₀

Przede wszystkim, dla zaspokojenia potrzeby psychicznej, zastąpię 1001! przez 999!, pokazując, że:

t(999! + 2) = 0

Faktycznie, n | 999! + n dla n=2 ... 999. Ponadto 2 | 999! + 1000 oraz 11 | 999! + 1001 (bo 1001 jest podzielne przez 11; zachodzi też podzielność przez 7). Koniec dowodu

Wyjdźmy poza psychologię. Podobny argument daje

t(997! + 2) = 0

bo 997 jest największą liczbą pierwszą ≤ 1001. Serio, nie potrzebujemy aż silni, wystarczy iloczyn ppr(m) wszystkich liczb pierwszych ≤ m - oczywiscie:

t(ppr(997) + 2) = 0

jako, że ppr(997) = ppr(1001). Wynika stąd, że

t(ppr(997) - 3) ≤ 5

Odnotujmy nasz pierwszy wynik po staremu (bo poza tym, to powyższe sformułowanie jest lepsze):

TWIERDZENIE 0

Istnieje n ≤ ppr(997) - 3 takie, że t(n) = 5.

Zanim pójdziemy dalej, jakiego oszacowania należy się spodziewać? Rozkład liczb pierwszych podpowiada, że rzędu exp(200). Aż po 997 mamy 168 liczb pierwszych, więc Tw. 0 nie jest tragicznie słabe :-)

Ostatnie 6 liczb pierwszych poniżej 1001 to:

967 971 977 983 991 997

Wynika stąd zaostrzenie:

TWIERDZENIE 1

t(ppr(967) - 1001) ≤ 5

Owszem, zamiast do przodu: ppr(967) + 2, ppr(967) + 3, ..., możemy iść do tyłu:

ppr(967) - 2, ppr(967) - 3, ..., ppr(967) - 1001

Tym razem ppr(967) jest iloczynem tylko (:-) 163 najmniejszych liczb pierwszych.

Zachęcam czytelników do poprawy wyniku Twierdzenia 1.