Liczby jedynkowe

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

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

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

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

Kwadratem $n$-tej liczby jedynkowej jest $n$-ta liczba Demlo (ciąg A002477 w OEIS).

Własności

• Liczba $R_{m}$ jest dzielnikiem liczby $R_{n}$ wtedy i tylko wtedy, gdy $m\mid n$.
• Największym wspólnym dzielnikiem liczb $R_{m}$ i $R_{n}$ jest $R_{d}$, gdzie $d=\operatorname {NWD} (m,n)$. Liczby $R_{m}$ i $R_{n}$ są względnie pierwsze wtedy i tylko wtedy, gdy względnie pierwsze są liczby $m$ i $n$.
• Jeśli $R_{n}$ jest liczbą pierwszą, to $n$ również. Twierdzenie odwrotne nie jest prawdziwe. Kontrprzykład stanowi m.in. $111=3\cdot 37$.
• Liczba pierwsza $p>5$ jest dzielnikiem liczby $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ć $n$-tą potęgą liczby naturalnej dla $n>1$. Udowodniono, że to niemożliwe dla $n=2,3,4,5$. Problem dla $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. Początkowe liczby pierwsze jedynkowe to

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

W 1998 roku Torbjörn Granlund sprawdził komputerowo wszystkie liczby $R_{n}$ dla $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ę $R_{49081}$. Od tego czasu poznano co najmniej pięć nowych prawdopodobnie pierwszych liczb jedynkowych.

Do 2022 roku liczba $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). W 2022 roku Paul Underwood, wykorzystując test pierwszości oparty na krzywych eliptycznych, wykazał, że liczba $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.

Liczby jedynkowe w różnych systemach pozycyjnych

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

$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 $b=2$, $n$-tą liczbą jedynkową $R_{n}^{(2)}$ jest $n$-ta liczba Mersenne’a.

Zobacz też

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