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

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

142857 × 1 = 142857

142857 × 2 = 285714

142857 × 3 = 428571

142857 × 4 = 571428

142857 × 5 = 714285

142857 × 6 = 857142

Циклическое число 142857, умноженное на числа от 1 до 6

Детали

Чтобы число было циклическим, требуется, чтобы умножение на последовательные числа давала перестановки цифр числа. Так, число 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/(L + 1).

Наоборот, если десятичный период числа 1 /p (где p простое) равен^[1]

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 ^[2]).

Например, для 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, 821, 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, 751, 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, 661, 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, 653, 677, 691, 701, 739, 751, 773, 797, 809, 811, 821, 823, 857, 859, 881, 907, 929, 941, 953, 977, …

Не существует таких чисел p в шестнадцатеричной системе.

Известные схемы таких последовательностей получаются из алгебраической теории чисел, а именно, эта последовательность является множество простых p, таких что b является первообразным корнем по модулю p.

Построение циклических чисел

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

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

Положим t = t + 1

Положим x = r · b

Положим d = целая часть(x / p)

Положим r = x mod p

Положим n = n · b + d

Если r ≠ 1, переходим в начало цикла.

Если t = p − 1, то n является циклическим числом.

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

Шаг

n = n · b + d

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

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

Свойства циклических чисел

Примечание: Ниже нижний индекс означает основание. Так, 142₁₀ означает число 142 по основанию 10, а 142₅ означает число 142 по основанию 5 (то есть 47₁₀).

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

Сколько циклических чисел?

Количество циклических чисел, не превышающих 10ⁿ, для натуральных n образуют последовательность (последовательность A086018 в OEIS):

1, 9, 60, 467, 3617, 25883, 248881, 2165288, 19016617…

Была высказана гипотеза (пока не доказана), что существует бесконечное множество циклических чисел^[2]. Согласно гипотезе Эмиля Артина^[3] эта последовательность содержит 37.395..% простых чисел (для b из последовательности A085397; последовательность A085397 в OEIS).

Другие системы счисления

Используя вышеприведённую технику, можно найти циклические числа в других системах счисления.

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

11₂ =3₁₀ → 01₂

101₂ = 5₁₀ → 0011₂

1011₂ = 11₁₀ → 0001011101₂

1101₂ = 13₁₀ → 000100111011₂

10011₂ =19₁₀ → 000011010111100101₂

11101₂ =29₁₀ → 0000100011010011110111001011₂

100101₂ = 37₁₀ → 000001101110101100111110010001010011₂

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

2₃ =2₁₀ → 1₃

12₃ = 5₁₀ → 0121₃

21₃ = 7₁₀→ 010212₃

122₃ = 17₁₀ → 0011202122110201₃

201₃ =19₁₀ → 001102100221120122₃

1002₃ = 29₁₀ → 0002210102011122200121202111₃

1011₃ = 31₁₀ → 000212111221020222010111001202₃

В четверичной системе:

(циклических чисел нет)

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

2₅ = 2₁₀ → 2₅

3₅ = 3₁₀ → 13₅

12₅ = 7₁₀ → 032412 ₅

32₅ = 17₁₀ → 0121340243231042₅

43₅ = 23₁₀ → 0102041332143424031123₅

122₅ = 37₁₀ → 003142122040113342441302322404331102₅

133₅ = 43₁₀ → 002423141223434043111442021303221010401333₅

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

15₆ = 11₁₀ → 0313452421₆

21₆ = 13₁₀ → 024340531215₆

25₆ = 17₁₀ → 0204122453514331₆

105₆ = 41₁₀ → 0051335412440330234455042201431152253211₆

135₆ = 59₁₀ → 0033544402235104134324250301455220111533204514212313052541₆

141₆ = 61₁₀ → 003312504044154453014342320220552243051511401102541213235335₆

211₆ =79₁₀ → 002422325434441304033512354102140052450553133230121114251522043201453415503105

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

2₇ = 2₁₀ → 3₇

5₇ = 5₁₀ → 1254₇

14₇ = 11₁₀ → 0431162355₇

16₇ = 13₁₀ → 035245631421₇

23₇ = 17₁₀ → 0261143464055232₇

32₇ = 23₁₀ → 0206251134364604155323₇

56₇ = 41₁₀ → 0112363262135202250565543034045314644161₇

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

3₈ = 3₁₀ → 25₈

5₈ = 5₁₀ → 1463₈

13₈ = 11₁₀ → 0564272135₈

35₈ = 29₁₀ → 0215173454106475626043236713₈

65₈ = 53₁₀ → 0115220717545336140465103476625570602324416373126743₈

73₈ = 59₁₀ → 0105330745756511606404255436276724470320212661713735223415₈

123₈ = 83₁₀ → 0061262710366576352321570224030531344173277165150674112014254562075537472464336045₈

В девятеричной системе:

2₉ = 2₁₀ → 4₉

(других нет)

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

2₁₁ = 2₁₀ → 5₁₁

3₁₁ = 3₁₀ → 37₁₁

12₁₁ = 13₁₀ → 093425A17685₁₁

16₁₁ = 17₁₀ → 07132651A3978459₁₁

21₁₁ = 23₁₀ → 05296243390A581486771A₁₁

27₁₁ = 29₁₀ → 04199534608387A69115764A2723₁₁

29₁₁ = 31₁₀ → 039A32146818574A71078964292536₁₁

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

5₁₂ = 5₁₀ → 2497₁₂

7₁₂ = 7₁₀ → 186A35₁₂

15₁₂ = 17₁₀ → 08579214B36429A7₁₂

27₁₂ = 31₁₀ → 0478AA093598166B74311B28623A55₁₂

35₁₂ = 41₁₀ → 036190A653277397A9B4B85A2B15689448241207₁₂

37₁₂ = 43₁₀ → 0342295A3AA730A068456B879926181148B1B53765₁₂

45₁₂ = 53₁₀ → 02872B3A23205525A784640AA4B9349081989B6696143757B117₁₂

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

2₁₃ = 2₁₀ → 6₁₃

5₁₃ = 5₁₀ → 27A5₁₃

B₁₃ = 11₁₀ → 12495BA837₁₃

16₁₃ = 19₁₀ → 08B82976AC414A3562₁₃

25₁₃ = 31₁₀ → 055B42692C21347C7718A63A0AB985₁₃

2B₁₃ = 37₁₀ → 0474BC3B3215368A25C85810919AB79642A7₁₃

32₁₃ = 41₁₀ → 04177C08322B13645926C8B550C49AA1B96873A6₁₃

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

3₁₄ = 3₁₀ → 49₁₄

13₁₄ = 17₁₀ → 0B75A9C4D2683419₁₄

15₁₄ = 19₁₀ → 0A45C7522D398168BB₁₄

19₁₄ = 23₁₀ → 0874391B7CAD569A4C2613₁₄

21₁₄ = 29₁₀ → 06A89925B163C0D73544B82C7A1D₁₄

3B₁₄ = 53₁₀ → 039AB8A075793610B146C21828DA43253D6864A7CD2C971BC5B5₁₄

43₁₄ = 59₁₀ → 03471937B8ACB5659A2BC15D09D74DA96C4A62531287843B21C80D4069₁₄

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

2₁₅ = 2₁₀ → 7₁₅

D₁₅ = 13₁₀ → 124936DCA5B8₁₅

14₁₅ = 19₁₀ → 0BC9718A3E3257D64B₁₅

18₁₅ = 23₁₀ → 09BB1487291E533DA67C5D₁₅

1E₁₅ = 29₁₀ → 07B5A528BD6ACDE73949C6318421₁₅

27₁₅ = 37₁₀ → 061339AE2C87A8194CE8DBB540C26746D5A2₁₅

2B₁₅ = 41₁₀ → 0574B51C68BA922DD80AE97A39D286345CC116E4₁₅

В шестнадцатеричной системе:

(циклических чисел нет)

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

2₁₇ = 2₁₀ → 8₁₇

3₁₇ = 3₁₀ → 5B₁₇

5₁₇ = 5₁₀ → 36DA₁₇

7₁₇ = 7₁₀ → 274E9C₁₇

B₁₇ = 11₁₀ → 194ADF7C63₁₇

16₁₇ = 23₁₀ → 0C9A5F8ED52G476B1823BE₁₇

1E₁₇ = 31₁₀ → 09583E469EDC11AG7B8D2CA7234FF6₁₇

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

5₁₈ = 5₁₀ → 3AE7₁₈

B₁₈ = 11₁₀ → 1B834H69ED₁₈

1B₁₈ = 29₁₀ → 0B31F95A9GDAE4H6EG28C781463D₁₈

21₁₈ = 37₁₀ → 08DB37565F184FA3G0H946EACBC2G9D27E1H₁₈

27₁₈ = 43₁₀ → 079B57H2GD721C293DEBCHA86CA0F14AFG5F8E4365₁₈

2H₁₈ = 53₁₀ → 0620C41682CG57EAFB3D4788EGHBFH5DGB9F51CA3726E4DA9931₁₈

35₁₈ =59₁₀ → 058F4A6CEBAC3BG30G89DD227GE0AHC92D7B53675E61EH19844FFA13H7₁₈

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

2₁₉ = 2₁₀ → 9₁₉

7₁₉ = 7₁₀ → 2DAG58₁₉

B₁₉ = 11₁₀ → 1DFA6H538C₁₉

D₁₉ = 13₁₀ → 18EBD2HA475G₁₉

14₁₉ = 23₁₀ → 0FD4291C784I35EG9H6BAE₁₉

1A₁₉ = 29₁₀ → 0C89FDE7G73HD1I6A9354B2BF15H₁₉

1I₁₉ = 37₁₀ → 09E73B5C631A52AEGHI94BF7D6CFH8DG8421₁₉

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

3₂₀ = 3₁₀ → 6D₂₀

D₂₀ = 13₁₀ → 1AF7DGI94C63₂₀

H₂₀ = 17₁₀ → 13ABF5HCIG984E27₂₀

13₂₀ = 23₁₀ → 0H7GA8DI546J2C39B61EFD₂₀

1H₂₀ = 37₁₀ → 0AG469EBHGF2E11C8CJ93FDA58234H5II7B7₂₀

23₂₀ = 43₁₀ → 0960IC1H43E878GEHD9F6JADJ17I2FG5BCB3526A4D₂₀

27₂₀ = 47₁₀ → 08A4522B15ACF67D3GBI5J2JB9FEHH8IE974DC6G381E0H₂₀

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

2₂₁ = 2₁₀ → A₂₁

J₂₁ = 19₁₀ → 1248HE7F9JIGC36D5B₂₁

12₂₁ = 23₁₀ → 0J3DECG92FAK1H7684BI5A₂₁

18₂₁ = 29₁₀ → 0F475198EA2IH7K5GDFJBC6AI23D₂₁

1A₂₁ = 31₁₀ → 0E4FC4179A382EIK6G58GJDBAHCI62₂₁

2B₂₁ = 53₁₀ → 086F9AEDI4FHH927J8F13K47B1KCE5BA672G533BID1C5JH0GD9J₂₁

38₂₁ = 71₁₀ → 06493BB50C8I721A13HFE42K27EA785J4F7KEGBH99FK8C2DIJAJH356GI0ID6ADCF1G5D₂₁

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

5₂₂ = 5₁₀ → 48HD₂₂

H₂₂ = 17₁₀ → 16A7GI2CKFBE53J9₂₂

J₂₂ = 19₁₀ → 13A95H826KIBCG4DJF₂₂

19₂₂ = 31₁₀ → 0FDAE45EJJ3C194L68B7HG722I9KCH₂₂

1F₂₂ = 37₁₀ → 0D1H57G143CAFA2872L8K4GE5KHI9B6BJDEJ₂₂

1J₂₂ = 41₁₀ → 0BHFC7B5JIH3GDKK8CJ6LA469EAG234I5811D92F₂₂

23₂₂ = 47₁₀ → 0A6C3G897L18JEB5361J44ELBF9I5DCE0KD27AGIFK2HH7₂₂

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

2₂₃ = 2₁₀ → B₂₃

3₂₃ =3₁₀ → 7F₂₃

5₂₃ = 5₁₀ → 4DI9₂₃

H₂₃ = 17₁₀ → 182G59AILEK6HDC4₂₃

21₂₃ = 47₁₀ → 0B5K1AHE496JD4KCGEFF3L0MBH2LC58IDG39I2A6877J1M₂₃

2D₂₃ = 59₁₀ → 08M51CJK65AC1LJ27I79846E9H3BFME0HLA32GHCAL13KF4FDEIG8D5JB7₂₃

3K₂₃ = 89₁₀ → 05LG6ADG0BK9CL4910HJ2J8I21CF5FHD4327B8C3864EMH16GC96MB2DA1IDLM53K3E4KLA7H759IJKFBEAJEGI8₂₃

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

7₂₄ = 7₁₀ → 3A6KDH₂₄

B₂₄ = 11₁₀ → 248HALJF6D₂₄

D₂₄ = 13₁₀ → 1L795CM3GEIB₂₄

H₂₄ = 17₁₀ → 19L45FCGME2JI8B7₂₄

17₂₄ = 31₁₀ → 0IDMAK327HJ8C96N5A1D3KLG64FBEH₂₄

1D₂₄ = 37₁₀ → 0FDEM1735K2E6BG54CN8A91MGKI3L9HC7IJB₂₄

1H₂₄ = 41₁₀ → 0E14284G98IHDB2M5KBGN9MJLFJ7EF56ACL1I3C7₂₄

В 25-ричной системе:

2₂₅ = 2₁₀ → C₂₅

(других нет)

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

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

См. также

• Периодическая дробь
• Малая теорема Ферма
• Циклическая перестановка цифр целых чисел^[англ.]