Репьюнит

Числа, содержащие только цифру 1

В развлекательной математике репьюнит — это число вроде 11, 111 или 1111, которое содержит только цифру 1 — более специфический тип репдигит . Термин означает «повторяющаяся единица» и был введен в 1966 году Альбертом Х. Бейлером в его книге « Воспоминания в теории чисел» . ^{[примечание 1]}

Репьюнитное простое число — это репьюнит, который также является простым числом . Простые числа, которые являются репьюнитами в двоичной системе счисления, являются простыми числами Мерсенна . По состоянию на май 2023 года наибольшее известное простое число 2 ^{82 589 933} − 1 , наибольшее вероятное простое число R _8177207 и наибольшее простое число эллиптической кривой R ₈₆₄₅₃ являются репьюнитами в различных системах счисления.

Определение

Репьюниты с основанием b определяются как (этот b может быть как положительным, так и отрицательным)

${\displaystyle R_{n}^{(b)}\equiv 1+b+b^{2}+\cdots +b^{n-1}={b^{n}-1 \over {b-1}}\qquad {\mbox{for }}|b|\geq 2,n\geq 1.}$

Таким образом, число R _n ^{( b )} состоит из n копий цифры 1 в представлении с основанием b . Первые два репьюнита с основанием b для n  = 1 и n  = 2 имеют вид

${\displaystyle R_{1}^{(b)}={b-1 \over {b-1}}=1\qquad {\text{and}}\qquad R_{2}^{(b)}={b^{2}-1 \over {b-1}}=b+1\qquad {\text{for}}\ |b|\geq 2.}$

В частности, десятичные (с основанием 10 ) репьюниты , которые часто называют просто репьюнитами, определяются как

${\displaystyle R_{n}\equiv R_{n}^{(10)}={10^{n}-1 \over {10-1}}={10^{n}-1 \over 9}\qquad {\mbox{for }}n\geq 1.}$

Таким образом, число R _n = R _n ⁽¹⁰⁾ состоит из n копий цифры 1 в десятичной системе счисления. Последовательность репьюнитов в десятичной системе счисления начинается с

1 , 11 , 111 , 1111, 11111, 111111, ... (последовательность A002275 в OEIS ).

Аналогично, репьюниты с основанием 2 определяются как

${\displaystyle R_{n}^{(2)}={2^{n}-1 \over {2-1}}={2^{n}-1}\qquad {\mbox{for }}n\geq 1.}$

Таким образом, число R _n ⁽²⁾ состоит из n копий цифры 1 в представлении с основанием 2. Фактически, репьюниты с основанием 2 являются известными числами Мерсенна M _n  = 2 ⁿ  − 1, они начинаются с

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, ... (последовательность A000225 в OEIS ).

Характеристики

• Любой репьюнит в любой базе, имеющей составное число цифр, обязательно является составным. Например,

  R ₃₅ ^{( б )} = 1111111111111111111111111111111111111 = 11111 × 1000010000100001000010000100001 = 1111111 × 10000001000000100000010000001,

так как 35 = 7 × 5 = 5 × 7. Эта факторизация репьюнита не зависит от основания b, в котором выражен репьюнит.

Только репьюниты (в любой базе), имеющие простое число цифр, могут быть простыми. Это необходимое, но недостаточное условие . Например,

Р ₁₁ ⁽²⁾ = 2 ¹¹ − 1 = 2047 = 23 × 89.

• Если p — нечетное простое число, то каждое простое число q , которое делит R _p ^{( b ),} должно быть либо 1 плюс кратное 2 p , либо множителем b − 1. Например, простым множителем R ₂₉ является 62003 = 1 + 2·29·1069. Причина в том, что простое число p — это наименьшая экспонента, большая 1, такая, что q делит b ^p − 1, потому что p — простое число. Следовательно, если только q не делит b − 1, p делит функцию Кармайкла числа q , которая четна и равна q − 1.
• Любое положительное кратное репьюнита R _n ^{( b )} содержит по крайней мере n ненулевых цифр в системе счисления с основанием b .
• Любое число x является двузначным числом в системе счисления с основанием x − 1.
• Единственные известные числа, которые являются репьюнитами с по крайней мере 3 цифрами в более чем одной системе счисления одновременно, это 31 (111 в системе счисления с основанием 5, 11111 в системе счисления с основанием 2) и 8191 (111 в системе счисления с основанием 90, 1111111111111 в системе счисления с основанием 2). Гипотеза Гурмахти утверждает, что существуют только эти два случая.
• Используя принцип ящика, можно легко показать, что для взаимно простых натуральных чисел n и b существует репьюнит в базе b , кратный n . Чтобы увидеть это, рассмотрим репьюниты R ₁ ^{( b )} ,..., R _n ^{( b )} . Поскольку существует n репьюнитов, но только n −1 ненулевых остатков по модулю n, существуют два репьюнита R _i ^{( b )} и R _j ^{( b )} с 1 ≤ i < j ≤ n, такие, что R _i ^{( b )} и R _j ^{( b )} имеют одинаковый остаток по модулю n . Отсюда следует, что R _j ^{( b )} − R _i ^{( b )} имеет остаток 0 по модулю n , т. е. делится на n . Так как R _j ^{( b )} − R _i ^{( b )} состоит из j − i единиц, за которыми следуют i нулей, R _j ^{( b )} − R _i ^{( b )} = R _{j − i} ^{( b )} × b ⁱ . Теперь n делит левую часть этого уравнения, поэтому оно также делит правую часть, но так как n и b взаимно просты, n должно делить R _{j − i} ^{( b )} .
• Гипотеза Фейта–Томпсона заключается в том, что R _q ^{( p )} никогда не делит R _p ^{( q )} для двух различных простых чисел p и q .
• Используя алгоритм Евклида для определения репьюнитов: R ₁ ^{( b )} = 1; R _n ^{( b )} = R _{n −1} ^{( b )} × b + 1, любые последовательные репьюниты R _{n −1} ^{( b )} и R _n ^{( b )} являются взаимно простыми в любой системе счисления с основанием b для любого n .
• Если m и n имеют общий делитель d , R _m ^{( b )} и R _n ^{( b )} имеют общий делитель R _d ^{( b )} в любой системе счисления b для любых m и n . То есть, репьюниты фиксированной системы счисления образуют сильную последовательность делимости . Как следствие, если m и n взаимно просты, R _m ^{( b )} и R _n ^{( b )} взаимно просты. Алгоритм Евклида основан на gcd ( m , n ) = gcd ( m − n , n ) для m > n . Аналогично, используя R _m ^{( b )} − R _n ^{( b )} × b ^{m − n} = R _{m − n} ^{( b )} , можно легко показать, что gcd ( R _m ^{( b )} , R _n ^{( b )} ) = gcd ( R _{m − n} ^{( b )} , R _n ^{( b )} ) для m > n . Следовательно, если gcd ( m , n ) = d , то gcd ( R _m ^{( b )} , R _n ^{( b )} ) = R _d ^{( b )} .

Факторизация десятичных дробей

(Простые множители, окрашенные в красный цвет, означают «новые множители», т.е. простой множитель делит R _n , но не делит R _k для всех k < n ) (последовательность A102380 в OEIS ) ^[2]

Наименьший простой множитель числа R _n для n > 1 равен

11, 3, 11, 41, 3, 239, 11, 3, 11, 21649, 3, 53, 11, 3, 11, 2071723, 3, 111111111111111111, 11, 3, 11, 1111111111111111111 1111, 3, 41, 11, 3, 11, 3191, 3, 2791, 11, 3, 11, 41, 3, 2028119, 11, 3, 11, 83, 3, 173, 11, 3, 11, 35121409, 3, 239, 11, ... (последовательность A067063 в OEIS )

Репьюнит простые числа

Определение репьюнитов было предложено математиками-любителями, которые искали простые множители таких чисел.

Легко показать, что если n делится на a , то R _n ^{( b )} делится на R _a ^{( b )} :

${\displaystyle R_{n}^{(b)}={\frac {1}{b-1}}\prod _{d|n}\Phi _{d}(b),}$

где - циклотомический многочлен , а d пробегает делители n . Для p простое, ${\displaystyle \Phi _{d}(x)}$ ${\displaystyle d^{\mathrm {th} }}$

${\displaystyle \Phi _{p}(x)=\sum _{i=0}^{p-1}x^{i},}$

который имеет ожидаемую форму репьюнита, когда x заменяется на b .

Например, 9 делится на 3, и, таким образом, R ₉ делится на R ₃ — на самом деле, 111111111 = 111 · 1001001. Соответствующие циклотомические многочлены и — это и , соответственно. Таким образом, для того, чтобы R _n было простым, n обязательно должно быть простым, но этого недостаточно, чтобы n было простым. Например, R ₃  = 111 = 3 · 37 не является простым. За исключением этого случая R ₃ , p может делить R _n на простое n только если p = 2kn + 1 для некоторого k . ${\displaystyle \Phi _{3}(x)}$ ${\displaystyle \Phi _{9}(x)}$ ${\displaystyle x^{2}+x+1}$ ${\displaystyle x^{6}+x^{3}+1}$

Десятичные репьюниты простых чисел

R _n является простым числом для n  = 2, 19, 23, 317, 1031, 49081, 86453 ... (последовательность A004023 в OEIS ). 3 апреля 2007 года Харви Дабнер (который также нашел R ₄₉₀₈₁ ) объявил, что R ₁₀₉₂₉₇ является вероятным простым числом. ^[3] 15 июля 2007 года Максим Возный объявил, что R ₂₇₀₃₄₃ является вероятным простым числом. ^[4] Серж Баталов и Райан Проппер обнаружили, что R _5794777 и R _8177207 являются вероятными простыми числами 20 апреля и 8 мая 2021 года соответственно. ^[5] На момент их открытия каждое из них было наибольшим известным вероятным простым числом. 22 марта 2022 года было окончательно доказано, что вероятное простое число R ₄₉₀₈₁ является простым числом. ^[6] 15 мая 2023 года было окончательно доказано, что вероятное простое число R ₈₆₄₅₃ является простым числом. ^[7]

Было высказано предположение, что существует бесконечно много репьюнитных простых чисел ^[8], и они, по-видимому, встречаются примерно так же часто, как предсказывает теорема о простых числах : показатель степени N- го репьюнитного простого числа обычно приблизительно равен фиксированному кратному показателю ( N −1)-го.

Простые репуниты являются тривиальным подмножеством перестановочных простых чисел , т. е. простых чисел, которые остаются простыми после любой перестановки их цифр.

Конкретные свойства:

• Остаток R _n по модулю 3 равен остатку n по модулю 3. Используя 10 ^a ≡ 1 (mod 3) для любого a ≥ 0,
  n ≡ 0 (mod 3) ⇔ R _n ≡ 0 (mod 3) ⇔ R _n ≡ 0 (mod R ₃ ),
  n ≡ 1 (mod 3) ⇔ R _n ≡ 1 (mod 3) ⇔ R _n ≡ R ₁ ≡ 1 (mod R ₃ ),
  n ≡ 2 (mod 3) ⇔ R _n ≡ 2 (mod 3) ⇔ R _n ≡ R ₂ ≡ 11 (mod R ₃ ).
  Следовательно, 3 | n ⇔ 3 | R _n ⇔ R ₃ | R _n .
• Остаток R _n по модулю 9 равен остатку n по модулю 9. Используя 10 ^a ≡ 1 (mod 9) для любого a ≥ 0,
  n ≡ r (mod 9) ⇔ R _n ≡ r (mod 9) ⇔ R _n ≡ R _r (mod R ₉ ),
  для 0 ≤ r < 9.
  Следовательно, 9 | n ⇔ 9 | R _n ⇔ R ₉ | R _n .

Алгебра разложения обобщенных репьюнитных чисел

Если b — совершенная степень (можно записать как m ⁿ , где m , n целые числа, n > 1) и отличается от 1, то в системе счисления b существует не более одного репьюнита . Если n — степень простого числа (можно записать как p ^r , где p простое число, r целое число, p , r > 0), то все репьюниты в системе счисления b не являются простыми, за исключением R _p и R ₂ . R _p может быть как простым, так и составным числом, в первых примерах b = −216, −128, 4, 8, 16, 27, 36, 100, 128, 256 и т. д., во вторых примерах b = −243, −125, −64, −32, −27, −8, 9, 25, 32, 49, 81, 121, 125, 144, 169, 196, 216, 225, 243, 289 и т. д., а R ₂ может быть простым числом (когда p отличается от 2), только если b отрицательно, является степенью −2, например, b = −8, −32, −128, −8192 и т. д., на самом деле, R2 также может быть составным, например, b = −512, −2048, −32768 и т. д. Если _n не является степенью простого числа, то не существует простого числа, кратного основанию b , например, b = 64, 729 (при n = 6), b = 1024 (при n = 10) и b = −1 или 0 (при n любом натуральном числе). Другая особая ситуация — b = −4 k ⁴ , где k — положительное целое число, которое имеет аурифейлевскую факторизацию , например, b = −4 (при k = 1, тогда R ₂ и R ₃ — простые числа), и b = −64, −324, −1024, −2500, −5184, ... (при k = 2, 3, 4, 5, 6, ...), тогда не существует простого числа с основанием b, репьюнитного. Также предполагается, что когда b не является ни совершенной степенью, ни −4 k ⁴ с положительным целым числом , то существует бесконечно много простых чисел с основанием b, репьюнитных.

Обобщенная гипотеза репанит

Гипотеза, связанная с обобщенными простыми числами репьюнита: ^{[9] [10]} (гипотеза предсказывает, где находится следующее обобщенное простое число Мерсенна , если гипотеза верна, то существует бесконечно много простых чисел репьюнита для всех базисов ) ${\displaystyle b}$

Для любого целого числа , удовлетворяющего условиям: ${\displaystyle b}$

1. ${\displaystyle |b|>1}$.
2. ${\displaystyle b}$не является совершенной степенью . (поскольку, когда является совершенной степенью, можно показать, что существует не более одного значения, такого, что является простым числом, и это значение является самим собой или корнем числа ) ${\displaystyle b}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle {\frac {b^{n}-1}{b-1}}}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle r}$
3. ${\displaystyle b}$не имеет вида . (если да, то число имеет аурифейлевскую факторизацию ) ${\displaystyle -4k^{4}}$

имеет обобщенные репьюнитные простые числа вида

${\displaystyle R_{p}(b)={\frac {b^{p}-1}{b-1}}}$

для простых чисел простые числа будут распределены вблизи линии наилучшего соответствия ${\displaystyle p}$

${\displaystyle Y=G\cdot \log _{|b|}\left(\log _{|b|}\left(R_{(b)}(n)\right)\right)+C,}$

где предел , ${\displaystyle n\rightarrow \infty }$ ${\displaystyle G={\frac {1}{e^{\gamma }}}=0.561459483566...}$

и есть около

${\displaystyle \left(\log _{e}(N)+m\cdot \log _{e}(2)\cdot \log _{e}{\big (}\log _{e}(N){\big )}+{\frac {1}{\sqrt {N}}}-\delta \right)\cdot {\frac {e^{\gamma }}{\log _{e}(|b|)}}}$

основание b перекомпилирует простые числа , меньшие N.

• ${\displaystyle e}$является основанием натурального логарифма .
• ${\displaystyle \gamma }$– постоянная Эйлера–Машерони .
• ${\displaystyle \log _{|b|}}$это логарифм по основанию ${\displaystyle |b|}$
• ${\displaystyle R_{(b)}(n)}$является -м обобщенным репьюнитным простым числом в базе b (с простым числом p ) ${\displaystyle n}$
• ${\displaystyle C}$— константа подгонки данных, которая изменяется в зависимости от . ${\displaystyle b}$
• ${\displaystyle \delta =1}$если , если . ${\displaystyle b>0}$ ${\displaystyle \delta =1.6}$ ${\displaystyle b<0}$
• ${\displaystyle m}$наибольшее натуральное число, представляющее собой степень . ${\displaystyle -b}$ ${\displaystyle 2^{m-1}}$

У нас также есть следующие 3 объекта недвижимости:

1. Число простых чисел вида (где простое число ) меньше или равно примерно равно . ${\displaystyle {\frac {b^{n}-1}{b-1}}}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle e^{\gamma }\cdot \log _{|b|}{\big (}\log _{|b|}(n){\big )}}$
2. Ожидаемое количество простых чисел вида с простыми числами от до составляет около . ${\displaystyle {\frac {b^{n}-1}{b-1}}}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle |b|\cdot n}$ ${\displaystyle e^{\gamma }}$
3. Вероятность того, что число вида является простым (для простого ), составляет около . ${\displaystyle {\frac {b^{n}-1}{b-1}}}$ ${\displaystyle p}$ ${\displaystyle {\frac {e^{\gamma }}{p\cdot \log _{e}(|b|)}}}$

История

Хотя тогда они не были известны под этим названием, репьюниты в десятичной системе счисления изучались многими математиками в девятнадцатом веке в попытке разработать и предсказать циклические закономерности повторяющихся десятичных дробей . ^[11]

Очень рано было обнаружено, что для любого простого числа p, большего 5, период десятичного разложения 1/ p равен длине наименьшего числа репьюнита, делящегося на p . Таблицы периода обратных чисел простых чисел до 60 000 были опубликованы к 1860 году и позволили таким математикам, как Рейшле, факторизовать все репьюниты до R ₁₆ и многие большие числа. К 1880 году были факторизованы даже числа от R ₁₇ до R ₃₆ ^[11] , и любопытно, что, хотя Эдуард Люка не показал, что ни одно простое число ниже трех миллионов имело период девятнадцать , не было никаких попыток проверить ни одно репьюнит на простоту до начала двадцатого века. Американский математик Оскар Хоппе доказал, что R ₁₉ является простым числом в 1916 году ^[12] , а Лемер и Крайчик независимо обнаружили, что R ₂₃ является простым числом в 1929 году.

Дальнейшие успехи в изучении репьюнитов не происходили до 1960-х годов, когда компьютеры позволили найти много новых множителей репьюнитов и исправить пробелы в более ранних таблицах простых периодов. Число R ₃₁₇ было признано вероятным простым числом около 1966 года и было доказано простым числом одиннадцать лет спустя, когда было показано, что R ₁₀₃₁ является единственным возможным простым репьюнитом с менее чем десятью тысячами цифр. Оно было доказано простым числом в 1986 году, но поиски дальнейших простых репьюнитов в последующее десятилетие постоянно терпели неудачу. Однако в области обобщенных репьюнитов наблюдалось крупное побочное развитие, которое произвело большое количество новых простых чисел и вероятных простых чисел.

С 1999 года было обнаружено еще четыре вероятно простых репьюнита, но маловероятно, что какой-либо из них будет доказан как простой в обозримом будущем из-за их огромного размера.

Проект Каннингема направлен на документирование целочисленных факторизаций (среди прочих чисел) репьюнитов по основаниям 2, 3, 5, 6, 7, 10, 11 и 12.

Демло номера

DR Kaprekar определил числа Demlo как конкатенацию левой, средней и правой частей, где левая и правая части должны быть одинаковой длины (до возможного начального нуля слева) и должны в сумме давать число с повторной цифрой, а средняя часть может содержать любое дополнительное число этой повторяющейся цифры. ^[13] Они названы в честь железнодорожной станции Demlo (теперь называемой Dombivili ) в 30 милях от Бомбея на тогдашней железной дороге GIP , где Kaprekar начал их исследовать. Он называет замечательными числами Демло числа вида 1, 121, 12321, 1234321, ..., 12345678987654321. Тот факт, что это квадраты репьюнитов, побудил некоторых авторов называть числами Демло бесконечную последовательность этих чисел ^[14] 1, 121, 12321, ..., 12345678987654321, 1234567900987654321, 123456790120987654321, ..., (последовательность A002477 в OEIS ), хотя можно проверить, что это не числа Демло для p = 10, 19, 28, ...

Смотрите также

• Все один многочлен — Еще одно обобщение
• гипотеза Гурмахти
• Повторяющаяся десятичная дробь
• Repdigit
• Простое число Вагстаффа — можно рассматривать как репьюнитное простое число с отрицательным основанием ${\displaystyle b=-2}$

Сноски

Примечания

1. Альберт Х. Бейлер ввел термин «число повторения» следующим образом:

   Число, состоящее из повторяющейся одной цифры, иногда называют однозначным числом, и для удобства автор использовал термин «число повторения» (повторяющаяся единица) для обозначения однозначных чисел, состоящих исключительно из цифры 1. ^[1]

Ссылки

1. Бейлер 2013, стр. 83
2. Для получения дополнительной информации см. Факторизация чисел репьюнита.
3. Харви Дабнер, New Repunit R(109297)
4. Максим Возный, New PRP Repunit R (270343)
5. Слоан, Н. Дж. А. (ред.). "Последовательность A004023 (Индексы простых повторений: числа n, такие, что 11...111 (с n единицами) = (10^n - 1)/9 является простым числом.)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
6. "PrimePage Простые числа: R(49081)". PrimePage Простые числа . 2022-03-21 . Получено 2022-03-31 .
7. "PrimePage Простые числа: R(86453)". PrimePage Простые числа . 2023-05-16 . Получено 2023-05-16 .
8. Крис Колдуэлл. "repunit". The Prime Glossary . Prime Pages .
9. Вывод гипотезы Вагстаффа-Мерсенна
10. Обобщенная гипотеза Репьюнита
11. Dickson & Cresse 1999, стр. 164–167
12. Фрэнсис 1988, стр. 240–246.
13. Капрекар 1938a, 1938b, Гунджикар и Капрекар 1939
14. Вайсштейн, Эрик В. «Число Демло». MathWorld .

Ссылки

• Бейлер, Альберт Х. (2013) [1964], Развлечения в теории чисел: Королева математики развлекает, Dover Recreational Math (2-е пересмотренное издание), Нью-Йорк: Dover Publications, ISBN 978-0-486-21096-4
• Диксон, Леонард Юджин ; Кресс, Г. Х. (1999), История теории чисел, том I: Делимость и простота (2-е переиздание), Провиденс, Род-Айленд: AMS Chelsea Publishing, ISBN 978-0-8218-1934-0
• Фрэнсис, Ричард Л. (1988), «Математические стога сена: еще один взгляд на числа репьюнита», The College Mathematics Journal , 19 (3): 240–246, doi :10.1080/07468342.1988.11973120
• Гунджикар, КР; Капрекар, Д.Р. (1939), «Теория чисел Демло» (PDF) , Журнал Бомбейского университета , VIII (3): 3–9
• Капрек, DR (1938a), «О замечательных числах Демло», The Mathematics Student , 6 : 68
• Капрек, DR (1938b), "Числа Демло", J. Phys. Sci. Univ. Bombay , VII (3)
• Капрекар, Д.Р. (1948), Числа Демло , Девлали, Индия: Харесвада
• Рибенбойм, Пауло (1996-02-02), Новая книга записей простых чисел, Компьютеры и медицина (3-е изд.), Нью-Йорк: Springer, ISBN 978-0-387-94457-9
• Йейтс, Сэмюэл (1982), Возмездия и повторения, Флорида: Делрей-Бич, ISBN 978-0-9608652-0-8

Внешние ссылки

• Вайсштейн, Эрик В. «Репунит». Математический мир .
• Основные таблицы проекта Каннингема.
• Репьюнит на The Prime Pages Криса Колдуэлла.
• Репьюниты и их простые множители в World!Of Numbers.
• Простые обобщенные репьюниты, содержащие не менее 1000 десятичных цифр, Энди Стюард
• Проект Repunit Primes Страница Джованни Ди Марии о repunit primes.
• Наименьшее нечетное простое число p, такое что (b^p-1)/(b-1) и (b^p+1)/(b+1), является простым для оснований 2<=b<=1024
• Факторизация чисел репанции
• Обобщенные репьюнитные простые числа по основанию от -50 до 50