Циклическое число - Cyclic number

А циклическое число является целое число в котором циклические перестановки цифр идут подряд целые кратные числа. Наиболее широко известно шестизначное число. 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

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

однозначные цифры, например: 5
повторяющиеся цифры, например: 555
повторяющиеся циклические числа, например: 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 /п (куда п является основной ) является

п − 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}}}

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

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

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

Первые значения п для которого эта формула дает циклические числа в десятичный (б = 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, ...

За б = 12 (двенадцатеричный ), эти пs являются (последовательность 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, ...

За б = 2 (двоичный ), эти пs являются (последовательность 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, ...

За б = 3 (тройной ), эти пs являются (последовательность 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, ...

Нет таких пс в шестнадцатеричный система.

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

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

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

Позволять б быть основанием числа (10 для десятичного)
Позволять п быть простым числом, которое не делит б.
Позволять т = 0.
Позволять р = 1.
Позволять п = 0.
петля:

Позволять т = т + 1

Позволять Икс = р · б

Позволять d = int (Икс / п)

Позволять р = Икс мод п

Позволять п = п · б + d

Если р ≠ 1 затем повторите цикл.

если т = п - 1 тогда п - циклическое число.

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

Шаг

п = п · б + d

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

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

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

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

Другие числовые базы

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

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

11 (3) → 01

101 (5) → 0011

1011 (11) → 0001011101

1101 (13) → 000100111011

10011 (19) → 000011010111100101

11101 (29) → 0000100011010011110111001011

100101 (37) → 00000110101011100101111100101010001101

110101 (53) → 00000100101101001111001001101101111101101001011000011011001001

В тройной: (последовательность 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

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

В базе 7: (последовательность 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

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

2 (2) → 6

5 (5) → 27A5

В (11) → 12495BA837

16 (19) → 08B82976AC414A3562

25 (31) → 055B42692C21347C7718A63A0AB985

2В (37) → 0474BC3B3215368A25C85810919AB79642A7

32 (41) → 04177C08322B13645926C8B550C49AA1B96873A6

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

3 (3) → 49

13 (17) → 0B75A9C4D2683419

15 (19) → 0A45C7522D398168BB

19 (23) → 0874391B7CAD569A4C2613

21 (29) → 06A89925B163C0D73544B82C7A1D

3В (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

2В (41) → 0574B51C68BA922DD80AE97A39D286345CC116E4

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

(никто)

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

2 (2) → 8

3 (3) → 5Б

5 (5) → 36ДА

7 (7) → 274E9C

В (11) → 194ADF7C63

16 (23) → 0C9A5F8ED52G476B1823BE

1E (31) → 09583E469EDC11AG7B8D2CA7234FF6

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

5 (5) → 3AE7

В (11) → 1B834H69ED

1В (29) → 0B31F95A9GDAE4H6EG28C781463D

21 (37) → 08DB37565F184FA3G0H946EACBC2G9D27E1H

27 (43) → 079B57H2GD721C293DEBCHA86CA0F14AFG5F8E4365

2H (53) → 0620C41682CG57EAFB3D4788EGHBFH5DGB9F51CA3726E4DA9931

35 (59) → 058F4A6CEBAC3BG30G89DD227GE0AHC92D7B53675E61EH19844FFA13H7

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

2 (2) → 9

7 (7) → 2DAG58

В (11) → 1DFA6H538C

D (13) → 18EBD2HA475G

14 (23) → 0FD4291C784I35EG9H6BAE

1А (29) → 0C89FDE7G73HD1I6A9354B2BF15H

1I (37) → 09E73B5C631A52AEGHI94BF7D6CFH8DG8421

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

3 (3) → 6D

D (13) → 1AF7DGI94C63

H (17) → 13ABF5HCIG984E27

13 (23) → 0H7GA8DI546J2C39B61EFD

1Н (37) → 0AG469EBHGF2E11C8CJ93FDA58234H5II7B7

23 (43) → 0960IC1H43E878GEHD9F6JADJ17I2FG5BCB3526A4D

27 (47) → 08A4522B15ACF67D3GBI5J2JB9FEHH8IE974DC6G381E0H

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

2 (2) → А

J (19) → 1248HE7F9JIGC36D5B

12 (23) → 0J3DECG92FAK1H7684BI5A

18 (29) → 0F475198EA2IH7K5GDFJBC6AI23D

1A (31) → 0E4FC4179A382EIK6G58GJDBAHCI62

2В (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) → В

3 (3) → 7F

5 (5) → 4DI9

Н (17) → 182G59AILEK6HDC4

21 (47) → 0B5K1AHE496JD4KCGEFF3L0MBH2LC58IDG39I2A6877J1M

2D (59) → 08M51CJK65AC1LJ27I79846E9H3BFME0HLA32GHCAL13KF4FDEIG8D5JB7

3К (89) → 05LG6ADG0BK9CL4910HJ2J8I21CF5FHD4327B8C3864EMH16GC96MB2DA1IDLM53K3E4KLA7H759IJKFBEAJEGI8

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

7 (7) → 3A6KDH

В (11) → 248HALJF6D

D (13) → 1L795CM3GEIB

H (17) → 19L45FCGME2JI8B7

17 (31) → 0IDMAK327HJ8C96N5A1D3KLG64FBEH

1D (37) → 0FDEM1735K2E6BG54CN8A91MGKI3L9HC7IJB

1Н (41) → 0E14284G98IHDB2M5KBGN9MJLFJ7EF56ACL1I3C7

В базе 25:

2 (2) → С

(нет других)

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

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

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

дальнейшее чтение

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

внешняя ссылка

[1] Вайсштейн, Эрик В. «Константа Артина». mathworld.wolfram.com.

[1]