Liczby jedynkowe

Liczba jedynkowa^[1] (ang. repunit^[2]) – w rekreacyjnej teorii liczb, liczba naturalna, której zapis dziesiętny składa się z samych jedynek^[1][3]. Liczby jedynkowe spopularyzował (oraz wprowadził angielską nazwę repunit) Albert Beiler w książce Recreations in the Theory of Numbers^[2]. Początkowe liczby jedynkowe to

1, 11, 111, 1111, 11111, 111111 (ciąg A002275 w OEIS).

Alternatywnie ${\displaystyle n}$-tą liczbę jedynkową ${\displaystyle R_{n}}$ można zdefiniować jako sumę ${\displaystyle n}$ początkowych potęg dziesiątki^[3]:

${\displaystyle R_{n}=\sum _{k=0}^{n-1}10^{k}={\frac {10^{n}-1}{9}}}$.

Kwadratem ${\displaystyle n}$-tej liczby jedynkowej jest ${\displaystyle n}$-ta liczba Demlo (ciąg A002477 w OEIS)^[3].

Własności^[1]

• Liczba ${\displaystyle R_{m}}$ jest dzielnikiem liczby ${\displaystyle R_{n}}$ wtedy i tylko wtedy, gdy ${\displaystyle m\mid n}$.
• Największym wspólnym dzielnikiem liczb ${\displaystyle R_{m}}$ i ${\displaystyle R_{n}}$ jest ${\displaystyle R_{d}}$, gdzie ${\displaystyle d=\operatorname {NWD} (m,n)}$. Liczby ${\displaystyle R_{m}}$ i ${\displaystyle R_{n}}$ są względnie pierwsze wtedy i tylko wtedy, gdy względnie pierwsze są liczby ${\displaystyle m}$ i ${\displaystyle n}$.
• Jeśli ${\displaystyle R_{n}}$ jest liczbą pierwszą, to ${\displaystyle n}$ również. Twierdzenie odwrotne nie jest prawdziwe. Kontrprzykład stanowi m.in. ${\displaystyle 111=3\cdot 37}$.
• Liczba pierwsza ${\displaystyle p>5}$ jest dzielnikiem liczby ${\displaystyle R_{p-1}}$. Jest to wniosek z małego twierdzenia Fermata.
• Każda liczba naturalna niepodzielna przez 2 i przez 5 ma wielokrotność będącą liczbą jedynkową.
• Nie wiadomo, czy liczba jedynkowa może być ${\displaystyle n}$-tą potęgą liczby naturalnej dla ${\displaystyle n>1}$. Udowodniono, że to niemożliwe dla ${\displaystyle n=2,3,4,5}$. Problem dla ${\displaystyle n>5}$ pozostaje nierozstrzygnięty.

Liczby pierwsze jedynkowe

Znajdowanie dużych liczb pierwszych jedynkowych, podobnie jak faktoryzacja dużych liczb jedynkowych, nie jest proste. Pomocne bywają metody podobne do tych stosowanych dla liczb Mersenne’a^[2]. Początkowe liczby pierwsze jedynkowe to

${\displaystyle R_{2}}$, ${\displaystyle R_{19}}$, ${\displaystyle R_{23}}$, ${\displaystyle R_{317}}$, ${\displaystyle R_{1031}}$, ${\displaystyle R_{49081}}$ (ciąg A004023 w OEIS).

W 1998 roku Torbjörn Granlund sprawdził komputerowo wszystkie liczby ${\displaystyle R_{n}}$ dla ${\displaystyle n\leq 45000}$ w poszukiwaniu liczb prawdopodobnie pierwszych. Obliczenia zajęły łącznie dwa miesiące czasu procesora. Poszukiwania rozszerzył w 1999 roku Dubner, znajdując prawdopodobnie pierwszą liczbę ${\displaystyle R_{49081}}$. Od tego czasu poznano co najmniej pięć nowych prawdopodobnie pierwszych liczb jedynkowych^[4].

Do 2022 roku liczba ${\displaystyle R_{1031}}$ była największą liczbą jedynkową, o której było wiadomo, że na pewno jest pierwsza (dowód przeprowadzili Williams i Dubner w 1986 roku)^[4]. W 2022 roku Paul Underwood, wykorzystując test pierwszości oparty na krzywych eliptycznych, wykazał, że liczba ${\displaystyle R_{49081}}$ jest pierwsza. Wygenerowanie certyfikatu pierwszości wymagało 20 miesięcy obliczeń na 64-rdzeniowym procesorze AMD 3990x, a sama jego weryfikacja – 13 godzin^[4][5].

Liczby jedynkowe w różnych systemach pozycyjnych

Liczby jedynkowe można uogólnić na dowolny system pozycyjny o podstawie ${\displaystyle b\geq 2}$. Wówczas ${\displaystyle n}$-tą liczbą jedynkową jest^[1]

${\displaystyle R_{n}^{(b)}=(\underbrace {111\dots 1} _{n{\text{ cyfr}}})_{b}=\sum _{k=0}^{n-1}b^{k}={\frac {b^{n}-1}{b-1}}}$.

Gdy ${\displaystyle b=2}$, ${\displaystyle n}$-tą liczbą jedynkową ${\displaystyle R_{n}^{(2)}}$ jest ${\displaystyle n}$-ta liczba Mersenne’a^[3].

Zobacz też

• Liczby Mersenne’a
• Test pierwszości ECPP
• Małe twierdzenie Fermata
• Lemat o zwiększaniu wykładnika p-adycznego

Przypisy