Циклическое число

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Cyclic number" – news · newspapers · books · scholar · JSTOR (January 2021) (Learn how and when to remove this message)

Циклическое число — это целое число , для которого циклические перестановки цифр являются последовательными целыми кратными числа. Наиболее широко известно шестизначное число 142857 , первые шесть целых кратных которого являются

142857 × 1 = 142857

142857 × 2 = 285714

142857 × 3 = 428571

142857 × 4 = 571428

142857 × 5 = 714285

142857 × 6 = 857142

Чтобы считаться циклическим числом, требуется, чтобы последовательные кратные были циклическими перестановками. Таким образом, число 076923 не будет считаться циклическим числом, потому что, хотя все циклические перестановки являются кратными, они не являются последовательными целыми кратными:

076923 × 1 = 076923

076923 × 3 = 230769

076923 × 4 = 307692

076923 × 9 = 692307

076923 × 10 = 769230

076923 × 12 = 923076

Обычно исключаются следующие тривиальные случаи:

1. однозначные числа, например: 5
2. повторяющиеся цифры, например: 555
3. повторяющиеся циклические числа, например: 142857142857

Если начальные нули не допускаются в числах, то 142857 является единственным циклическим числом в десятичной системе счисления , из-за необходимой структуры, приведенной в следующем разделе. Если допустить начальные нули, последовательность циклических чисел начинается:

(10 ⁶ − 1) / 7 = 142857 (6 цифр)

(10 ¹⁶ − 1) / 17 = 0588235294117647 (16 цифр)

(10 ¹⁸ − 1) / 19 = 052631578947368421 (18 цифр)

(10 ²² − 1) / 23 = 0434782608695652173913 (22 цифры)

(10 ²⁸ − 1) / 29 = 0344827586206896551724137931 (28 цифр)

(10 ⁴⁶ − 1) / 47 = 0212765957446808510638297872340425531914893617 (46 цифр)

(10 ⁵⁸ − 1) / 59 = 0169491525423728813559322033898305084745762711864406779661 (58 цифр)

(10 ⁶⁰ − 1) / 61 = 016393442622950819672131147540983606557377049180327868852459 (60 цифр)

(10 ⁹⁶ − 1) / 97 = 010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567 (96 цифр)

Циклические числа связаны с повторяющимися цифровыми представлениями дробей единиц . Циклическое число длины L является цифровым представлением

1/( Л + 1).

Наоборот, если цифровой период 1/ p (где p — простое число ) равен

р − 1,

тогда цифры представляют собой циклическое число.

Например:

1/7 = 0,142857 142857...

Множества этих дробей демонстрируют циклическую перестановку:

1/7 = 0,142857 142857...

2/7 = 0,285714 285714...

3/7 = 0,428571 428571...

4/7 = 0,571428 571428...

5/7 = 0,714285 714285...

6/7 = 0,857142 857142...

Из соотношения с единичными дробями можно показать, что циклические числа имеют вид частного Ферма

${\displaystyle {\frac {b^{p-1}-1}{p}}}$

где b — основание системы счисления (10 для десятичной системы счисления ), а p — простое число , которое не делит b . (Простые числа p , которые дают циклические числа в системе счисления с основанием b, называются полными обратными простыми числами или длинными простыми числами в системе счисления с основанием b ).

Например, случай b = 10, p = 7 дает циклическое число 142857, а случай b = 12, p = 5 дает циклическое число 2497.

Не все значения p дадут циклическое число, используя эту формулу; например, случай b = 10, p = 13 дает 076923076923, а случай b = 12, p = 19 дает 076B45076B45076B45. Эти неудачные случаи всегда будут содержать повторение цифр (возможно, нескольких).

Первые значения p , для которых эта формула выдает циклические числа в десятичной системе счисления ( b = 10), следующие (последовательность A001913 в OEIS ):

7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577, 593, 619, 647, 659, 701, 709, 727, 743, 811, 1, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983, ...

Для b = 12 ( двенадцатеричная система ) эти p равны (последовательность A019340 в OEIS )

5, 7, 17, 31, 41, 43, 53, 67, 101, 103, 113, 127, 137, 139, 149, 151, 163, 173, 197, 223, 257, 269, 281, 283, 293, 317, 353, 367, 379, 389, 401, 449, 461, 509, 523, 547, 557, 569, 571, 593, 607, 617, 619, 631, 641, 653, 691, 701, 739, 1, 761, 773, 787, 797, 809, 821, 857, 881, 929, 953, 967, 977, 991, ...

Для b = 2 ( двоичный ) эти p равны (последовательность A001122 в OEIS )

3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619, 653, 659, 1, 677, 701, 709, 757, 773, 787, 797, 821, 827, 829, 853, 859, 877, 883, 907, 941, 947, ...

Для b = 3 ( троичный ) эти p равны (последовательность A019334 в OEIS )

2, 5, 7, 17, 19, 29, 31, 43, 53, 79, 89, 101, 113, 127, 137, 139, 149, 163, 173, 197, 199, 211, 223, 233, 257, 269, 281, 283, 293, 317, 331, 353, 379, 389, 401, 449, 461, 463, 487, 509, 521, 557, 569, 571, 593, 607, 617, 631, 641, 3, 677, 691, 701, 739, 751, 773, 797, 809, 811, 821, 823, 857, 859, 881, 907, 929, 941, 953, 977, ...

В шестнадцатеричной системе таких букв «п» нет .

Известная закономерность этой последовательности исходит из алгебраической теории чисел , в частности, эта последовательность представляет собой множество простых чисел p, таких что b является примитивным корнем по модулю p . Гипотеза Эмиля Артина ^[1] заключается в том, что эта последовательность содержит 37,395..% простых чисел (для b в OEIS : A085397 ).

Циклические числа можно построить с помощью следующей процедуры :

Пусть b — основание числа (10 для десятичной системы счисления).
Пусть p — простое число, которое не делит b .
Пусть t = 0.
Пусть r = 1.
Пусть n = 0.
цикл:

Пусть t = t + 1

Пусть х = г ⋅ б

Пусть d = int ( x / p )

Пусть r = x mod p

Пусть n = n ⋅ b + d

Если r ≠ 1, то повторить цикл.

если t = p − 1, то n — циклическое число.

Эта процедура работает путем вычисления цифр числа 1/ p в системе счисления с основанием b путем деления в столбик . r — остаток на каждом шаге, а d — полученная цифра.

Шаг

н = н ⋅ б + d

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

Если t когда-либо превысит p /2, то число должно быть циклическим, без необходимости вычисления оставшихся цифр.

• При умножении на их порождающее простое число результатом является последовательность из b − 1 цифр, где b — основание (например, 10 в десятичной системе). Например, в десятичной системе 142857 × 7 = 999999.
• При разбиении на группы одинаковой длины (из двух, трех, четырех и т. д. цифр) и сложении групп получается последовательность из b - 1 цифр. Например, 14 + 28 + 57 = 99, 142 + 857 = 999, 1428 + 5714+ 2857 = 9999 и т. д. ... Это частный случай теоремы Миди .
• Все циклические числа делятся на b − 1, где b — основание (например, 9 в десятичной системе), а сумма остатка кратна делителю. (Это следует из предыдущего пункта.)

Используя описанную выше технику, циклические числа можно найти в других числовых основаниях. (Не все из них следуют второму правилу (все последовательные кратные являются циклическими перестановками), указанному в разделе «Особые случаи» выше.) В каждом из этих случаев цифры в половине периода складываются в основание минус один. Таким образом, для двоичной системы сумма битов в половине периода равна 1; для троичной — 2 и т. д.

В двоичной системе счисления последовательность циклических чисел начинается так: (последовательность A001122 в OEIS )

11 (3) → 01

101 (5) → 0011

1011 (11) → 0001011101

1101 (13) → 000100111011

10011 (19) → 000011010111100101

11101 (29) → 0000100011010011110111001011

В троичном : (последовательность A019334 в OEIS )

2 (2) → 1

12 (5) → 0121

21 (7) → 010212

122 (17) → 0011202122110201

201 (19) → 001102100221120122

В четвертичном периоде их нет.

В пятеричном : (последовательность A019335 в OEIS )

2 (2) → 2

3 (3) → 13

12 (7) → 032412

32 (17) → 0121340243231042

43 (23) → 0102041332143424031123

122 (37) → 003142122040113342441302322404331102

В шестеричном : (последовательность A167794 в OEIS )

15 (11) → 0313452421

21 (13) → 024340531215

25 (17) → 0204122453514331

105 (41) → 0051335412440330234455042201431152253211

135 (59) → 0033544402235104134324250301455220111533204514212313052541

141 (61) → 003312504044154453014342320220552243051511401102541213235335

В базе 7: (последовательность A019337 в OEIS )

2 (2) → 3

5 (5) → 1254

14 (11) → 0431162355

16 (13) → 035245631421

23 (17) → 0261143464055232

32 (23) → 0206251134364604155323

В восьмеричном формате : (последовательность A019338 в OEIS )

3 (3) → 25

5 (5) → 1463

13 (11) → 0564272135

35 (29) → 0215173454106475626043236713

65 (53) → 0115220717545336140465103476625570602324416373126743

73 (59) → 0105330745756511606404255436276724470320212661713735223415

В девятеричной системе счисления уникальным циклическим числом является

2 (2) → 4

В базе 11: (последовательность A019339 в OEIS )

2 (2) → 5

3 (3) → 37

12 (13) → 093425A17685

16 (17) → 07132651A3978459

21 (23) → 05296243390А581486771А

27 (29) → 04199534608387A69115764A2723

В двенадцатеричной системе : (последовательность A019340 в OEIS )

5 (5) → 2497

7 (7) → 186A35

15 (17) → 08579214B36429A7

27 (31) → 0478AA093598166B74311B28623A55

35 (41) → 036190A653277397A9B4B85A2B15689448241207

37 (43) → 0342295A3AA730A068456B879926181148B1B53765

В троичном ( b = 3) случай p = 2 дает 1 как циклическое число. Хотя отдельные цифры можно считать тривиальными случаями, для полноты теории может быть полезно рассматривать их только тогда, когда они генерируются таким образом.

Можно показать, что ни в одной числовой системе счисления, которая является полным квадратом , то есть с основанием 4, 9, 16, 25 и т. д., не существует циклических чисел (кроме тривиальных однозначных цифр, т. е. p = 2 ).

• Повторяющаяся десятичная дробь
• Малая теорема Ферма
• Циклическая перестановка целых чисел
• Паразитарное число

• Гарднер, Мартин. Математический цирк: больше головоломок, игр, парадоксов и других математических развлечений из Scientific American. Нью-Йорк: Математическая ассоциация Америки, 1979. С. 111–122.
• Калман, Дэн; «Дроби с циклическими цифровыми моделями» The College Mathematics Journal, т. 27, № 2. (март 1996 г.), стр. 109–115.
• Лесли, Джон. «Философия арифметики: демонстрация прогрессивного взгляда на теорию и практику ...» , Лонгман, Херст, Риз, Орм и Браун, 1820, ISBN 1-4020-1546-1 
• Уэллс, Дэвид; « Словарь любопытных и интересных чисел издательства Penguin » , издательство Penguin Press. ISBN 0-14-008029-5 

• Вайсштейн, Эрик В. «Циклическое число». MathWorld .
• Youtube: «Циклические числа - Numberphile»