Воссоединить

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

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

Простое число повторения — это число повторения, которое также является простым числом . Простые числа, повторяющиеся по основанию 2, являются простыми числами Мерсенна . По состоянию на май 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.}$

Таким образом, число Rn ^{( b )} состоит из n копий цифры 1 в _{представлении} по основанию b . Первые две реединицы base- 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 в десятичном представлении. Последовательность повторений по основанию 10 начинается с

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 ₃₅ ^{( б )} = 1111111111111111111111111111111111 = 11111 × 1000010000100001000010000100001 = 1111111 × 100000010000001000000100000 01,

поскольку 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 ^{( б )} имеют одинаковый остаток по модулю n . Отсюда следует, что R _j ^{( b )} − R _i ^{( b )} имеет вычет 0 по модулю n , т.е. делится на n . Поскольку R _j ^{( б )} - р _я ^{( б )} состоит из j - i единиц, за которыми следует i нулей, R _j ^{( б )} - р _я ^{( б )} знак равно р _{j - я} ^{( б )} × б ^я . Теперь 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 , Rm ^{( b )} и _Rn ^{( b )} имеют общий делитель _{Rd (} ^{b )} в любом основании- b ^для любых m и n . То есть повторения фиксированного основания образуют сильную последовательность делимости . ^Как следствие, если m и n взаимно простые, ^Rm ( ^{b ) и} Rn ₍ ^b ₎ взаимно простые. Алгоритм Евклида основан на НОД ( m , n ) = НОД ( m − n , n ) для m > n . Аналогично, используя R _m ^{( b )} − R _n ^{( b )} × b ^{m - n} = R _{m - n} ^{( b )} , можно легко показать, что НОД ( R _m ^{( b )} , R _n ^{( b )} ) = НОД ( р _{м - п} ^{( б )} , р _п ^{( б )} ) для м > п . Следовательно, если НОД ( m , n ) = d , то НОД ( 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, 1111111111111111111, 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 , то Rn ^{( b )} делится _на Ra ^{( 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 = 2 kn + 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 _270343, вероятно, является простым. ^[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 R3 ₎ ,
  n ≡ 1 (mod 3) ⇔ R _n ≡ 1 (mod 3) ⇔ R _n ≡ R ₁ ≡ 1 (mod R ₃ ),
  n ≡ 2 (mod 3) ⇔ R _n ≡ 2 (по модулю 3) ⇔ _Rn ≡ _R2 ≡ 11 (по модулю _R3 ) . Следовательно, 3 | п ⇔ 3 | р _н ⇔ р ₃ | Р _н .
  
• Остаток от 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 | п ⇔ 9 | р _н ⇔ р ₉ | Р _н .

Алгебра факторизация обобщенных чисел повторения

Если b — совершенная степень (может быть записана как m ⁿ с целыми числами m , n , n > 1) отличается от 1, то в базе- b существует не более одной повторной единицы . Если n является степенью простого числа (может быть записано как p ^r , где p prime, 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 и т. д. Фактически, R ₂ также может быть составным , например, 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 ⁴ с k положительным целым числом, то существует бесконечное количество простых чисел с повторением по основанию b .

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

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

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

1. ${\displaystyle |b|>1}$.
2. ${\displaystyle b}$это не идеальная сила . (поскольку if является совершенной степенью th, можно показать, что существует не более одного такого значения, которое является простым, и это значение является самим собой или корнем ) ${\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}}}$

для prime простые числа будут распределены вблизи линии наилучшего соответствия ${\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|)}}}$

base- b reunit — простые числа меньше 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}$— наибольшее натуральное число, являющееся степенью th. ${\displaystyle -b}$ ${\displaystyle 2^{m-1}}$

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

1. Количество простых чисел вида (с prime ) меньше или равно примерно . ${\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|)}}}$

История

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

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

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

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

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

Числа демло

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

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

• Весь один полином — Еще одно обобщение
• Гипотеза Гурматига
• Повторяющаяся десятичная дробь
• Репцифра
• Простое число Вагстаффа — его можно рассматривать как простое число повторения с отрицательным основанием. ${\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 является простым.)». Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
6. "Простые числа PrimePage: R (49081)" . ПраймПейдж Праймс . 21 марта 2022 г. Проверено 31 марта 2022 г.
7. "Простые числа PrimePage: R (86453)" . ПраймПейдж Праймс . 16 мая 2023 г. Проверено 16 мая 2023 г.
8. Крис Колдуэлл. «репунит». Главный глоссарий . Прайм страницы .
9. Вывод гипотезы Вагстаффа-Мерсенна
10. Обобщенная гипотеза Репунита
11. Dickson & Cresse 1999, стр. 164–167.
12. Фрэнсис 1988, стр. 240–246.
13. Капрекар 1938a, 1938b, Гунджикар и Капрекар 1939
14. Вайсштейн, Эрик В. «Число Демло». Математический мир .

Рекомендации

• Бейлер, Альберт Х. (2013) [1964], Отдых в теории чисел: Королева математики развлекает, Dover Recreational Math (2-е исправленное издание), Нью-Йорк: Dover Publications, ISBN 978-0-486-21096-4
• Диксон, Леонард Юджин ; Кресс, GH (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
• Капрекар, Д. Р. (1938a), «О чудесных числах Демло», Студент-математик , 6 : 68
• Капрекар, Д.Р. (1938b), «Числа Демло», J. Phys. наук. унив. Бомбей , VII (3)
• Капрекар, Д.Р. (1948), Числа Демло , Девлали, Индия: Харесвада
• Рибенбойм, Пауло (2 февраля 1996 г.), Новая книга записей простых чисел, компьютеров и медицины (3-е изд.), Нью-Йорк: Springer, ISBN 978-0-387-94457-9
• Йейтс, Сэмюэл (1982), Повторяет и повторяет, Флорида: Делрей-Бич, ISBN 978-0-9608652-0-8

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

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