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

Циклічне число 142857, помножене на числа від 1 до 6

Циклічне число — ціле число, циклічні перестановки цифр якого є добутками цього числа на послідовні числа. Найвідоміший приклад такого числа — Шаблон:Нп:

$142857\times 1=142857$

$142857\times 2=285714$

$142857\times 3=428571$

$142857\times 4=571428$

$142857\times 5=714285$

$142857\times 6=857142$

Подробиці

Щоб число було циклічним, вимагається, щоби множення на послідовні числа давало перестановки цифр числа. Так, число 076923 не вважається циклічним, оскільки, хоча всі циклічні перестановки є добутком числа на деякі цілі множники, ці множники не є послідовними цілими числами:

$076923\times 1=076923$

$076923\times 3=230769$

$076923\times 4=307692$

$076923\times 9=692307$

$076923\times 10=769230$

$076923\times 12=923076$

Як правило, виключаються наступні типові випадки:

1. Окремі цифри, наприклад, 5
2. Повторювані цифри, наприклад, 555
3. Повторювані циклічні числа, як-от 142857142857

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

$\frac{10^6-1}{\mathrm{𝟕}}=142857$ (6 цифр)

$\frac{10^{16}-1}{\mathrm{𝟏}\mathrm{𝟕}}=0588235294117647$ (16 цифр)

$\frac{10^{18}-1}{\mathrm{𝟏}\mathrm{𝟗}}=052631578947368421$ (18 цифр)

$\frac{10^{22}-1}{\mathrm{𝟐}\mathrm{𝟑}}=0434782608695652173913$ (22 цифри)

$\frac{10^{28}-1}{\mathrm{𝟐}\mathrm{𝟗}}=0344827586206896551724137931$ (28 цифр)

$\frac{10^{46}-1}{\mathrm{𝟒}\mathrm{𝟕}}=0212765957446808510638297872340425531914893617$ (46 цифр)

$\frac{10^{58}-1}{\mathrm{𝟓}\mathrm{𝟗}}=0169491525423728813559322033898305084745762711864406779661$ (58 цифр)

$\frac{10^{60}-1}{\mathrm{𝟔}\mathrm{𝟏}}=016393442622950819672131147540983606557377049180327868852459$ (60 цифр)

$\frac{10^{96}-1}{\mathrm{𝟗}\mathrm{𝟕}}=010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567$ (96 цифр)

Зв'язок із повторюваними десятковими числами

Циклічні числа пов'язані з періодичними десятковими дробами часток одиниці. Циклічне число довжини $L$ має десяткове подання $\frac{1}{L+1}$.

Навпаки, якщо десятковий період числа $\frac{1}{p}$ (де $p$ просте) дорівнюєШаблон:Sfn $p-1$, то цифри представляють циклічне число.

Наприклад: $\frac{1}{7}=0.142857142857\dots$

Множення цього дробу дає циклічну перестановку:

$\frac{1}{7}=0.142857142857\dots$

$\frac{2}{7}=0.285714285714\dots$

$\frac{3}{7}=0.428571428571\dots$

$\frac{4}{7}=0.571428571428\dots$

$\frac{5}{7}=0.714285714285\dots$

$\frac{6}{7}=0.857142857142\dots$

Формат циклічних чисел

Використовуючи зв'язок із частками одиниці, можна показати, що циклічні числа мають вигляд Шаблон:Нп $\frac{b^{p-1}-1}{p}$, де $b$ — основа системи числення (10 для десяткової системи), а $p$ — просте, що не ділить $b$ (прості числа $p$, що утворюють циклічні числа за основою $b$, називаються Шаблон:Нп чи довгими простими за основою $b$Шаблон:Sfn).

Наприклад, для $b=10,p=7$ дає циклічне число 142857, а для $b=12,p=5$ дає циклічне число 2497.

Не всі значення $p$ дають циклічні числа згідно з цією формулою. Наприклад, для $b=10,p=13$ дає $076923076923_{10}$, а для $b=12,p=19$ дає $076B45076B45076B45_{12}</sub>$. Ці числа не є циклічними, оскільки складаються з повторюваних послідовностей.

Перші значення $p$, для яких формула дає циклічні числа за десятковою основою ($b=10$) (Шаблон: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,\dots$

Для $b=12$ (дванадцяткова система) ці значення $p$ дорівнюють (Шаблон: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,\dots$

Для $b=2$ (двійкова система) ці значення $p$ дорівнюють (Шаблон: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,\dots$

Для $b=3$ (трійкова система) ці значення $p$ дорівнюють (Шаблон: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,\dots$

Не існує таких чисел $p$ у шістнадцятковій системі.

Відомі схеми таких послідовностей отримуються з алгебраїчної теорії чисел, а саме, ця послідовність є множиною простих $p$, таких що $b$ є первісним коренем за модулем $p$.

Побудова циклічних чисел

Циклічні числа можна отримати наступною процедурою: Нехай $b$ — основа системи числення (10 для десяткових чисел)

1. Нехай $p$ — просте число, що не є дільником $b$
2. Покладемо $t=0$.
3. Покладемо $r=1$.
4. Покладемо $n=0$.
5. Цикл:
   1. Покладемо $t=t+1$
   2. Покладемо $x=r\times b$
   3. Покладемо $d=\left[\frac{x}{p}\right]$
   4. Покладемо $r=xmodp$
   5. Покладемо $n=n\times b+d$
   6. Якщо $r\ne 1$, переходимо до початку циклу.
6. Якщо $t=p-1$, то $n$ є циклічним числом.

Процедура працює шляхом обчислення цифр дробу $\frac{1}{p}$ за основою $b$ за алгоритмом ділення стовпчиком. На кожному кроці $r$ є остачею, а $d$ є черговою цифрою.

Крок $n=n\times b+d$ просто забезпечує додавання цифр числа. Для комп'ютерів, які не мають можливості обчислень із цілими числами дуже великого розміру, ці цифри можна просто надсилати на друк чи додавати іншим способом.

Зауважимо, що при досягненні $t$ границі $\frac{p}{2}$ отримане число повинно бути циклічним і необхідності обчислювати подальші цифри немає.

Властивості циклічних чисел

Примітка: Нижче нижній індекс означає основу. Так, $142_{10}$ означає число 142 з основою 10, а $142_5$ означає число 142 за основою 5 (тобто $47_{10}$).

• Якщо помножити число на генерувальне просте, отримаємо послідовність цифр «$base-1$» (9 у випадку десяткової основи). $142857_{10}\times 7=999999_{10}$.
• Якщо розбити число на групи цифр (по дві, три, чотири і т. д. цифри), а потім додати отримані числа, отримаємо послідовності дев'яток. $14+28+57=99$, $142+857=999$, $1428+5714+2857=9999$ і т. д. (це частковий випадок Шаблон:Нп).
• Всі циклічні числа діляться на «$base-1$» (9 у випадку десяткової основи).

Скільки циклічних чисел?

Кількість циклічних чисел, які не перевищують $10^n$, для натуральних $n$ утворюють послідовність (Шаблон:OEIS):

$1,9,60,467,3617,25883,248881,2165288,19016617\dots$

Було висловлено гіпотезу (поки що не доведену), що існує нескінченна множина циклічних чиселШаблон:Sfn. Згідно з Шаблон:Нп, ця послідовність містить 37,395..% простих чисел (для $b$ з послідовності A085397; Шаблон:OEIS).

Інші системи числення

Використовуючи вищенаведену техніку, можна знайти циклічні числа в інших системах числення.

У двійковій системі послідовність циклічних чисел починається з: (Шаблон:OEIS)

$11_2=3_{10}\to 01_2$

$101_2=5_{10}\to 0011_2$

$1011_2=11_{10}\to 0001011101_2$

$1101_2=13_{10}\to 000100111011_2$

$10011_2=19_{10}\to 000011010111100101_2$

$11101_2=29_{10}\to 0000100011010011110111001011_2$

$100101_2=37_{10}\to 000001101110101100111110010001010011_2$

У трійковій системі: (Шаблон:OEIS)

$2_3=2_{10}\to 1_3$

$12_3=5_{10}\to 0121_3$

$21_3=7_{10}\to 010212_3$

$122_3=17_{10}\to 0011202122110201_3$

$201_3=19_{10}\to 001102100221120122_3$

$1002_3=29_{10}\to 0002210102011122200121202111_3$

$1011_3=31_{10}\to 000212111221020222010111001202_3$

У четвериковій системі циклічних чисел немає.

У п'ятериковій системі: (Шаблон:OEIS)

$2_5=2_{10}\to 2_5$

$3_5=3_{10}\to 13_5$

$12_5=7_{10}\to 032412_5$

$32_5=17_{10}\to 0121340243231042_5$

$43_5=23_{10}\to 0102041332143424031123_5$

$122_5=37_{10}\to 003142122040113342441302322404331102_5$

$133_5=43_{10}\to 002423141223434043111442021303221010401333_5$

У шістковій системі: (Шаблон:OEIS)

$15_6=11_{10}\to 0313452421_6$

$21_6=13_{10}\to 024340531215_6$

$25_6=17_{10}\to 0204122453514331_6$

$105_6=41_{10}\to 0051335412440330234455042201431152253211_6$

$135_6=59_{10}\to 0033544402235104134324250301455220111533204514212313052541_6$

$141_6=61_{10}\to 003312504044154453014342320220552243051511401102541213235335_6$

$211_6=79_{10}\to 002422325434441304033512354102140052450553133230121114251522043201453415503105_6$

У сімковій системі: (Шаблон:OEIS)

$2_7=2_{10}\to 3_7$

$5_7=5_{10}\to 1254_7$

$14_7=11_{10}\to 0431162355_7$

$16_7=13_{10}\to 035245631421_7$

$23_7=17_{10}\to 0261143464055232_7$

$32_7=23_{10}\to 0206251134364604155323_7$

$56_7=41_{10}\to 0112363262135202250565543034045314644161_7$

У вісімковій системі: (Шаблон:OEIS)

$3_8=3_{10}\to 25_8$

$5_8=5_{10}\to 1463_8$

$13_8=11_{10}\to 0564272135_8$

$35_8=29_{10}\to 0215173454106475626043236713_8$

$65_8=53_{10}\to 0115220717545336140465103476625570602324416373126743_8$

$73_8=59_{10}\to 0105330745756511606404255436276724470320212661713735223415_8$

$123_8=83_{10}\to 0061262710366576352321570224030531344173277165150674112014254562075537472464336045_8$

У дев'ятковій системі єдине циклічне число:

$2_9=2_{10}\to 4_9$

В одинадцятковій системі 11: (Шаблон:OEIS)

$2_{11}=2_{10}\to 5_{11}$

$3_{11}=3_{10}\to 37_{11}$

$12_{11}=13_{10}\to 093425A17685_{11}$

$16_{11}=17_{10}\to 07132651A3978459_{11}$

$21_{11}=23_{10}\to 05296243390A581486771A_{11}$

$27_{11}=29_{10}\to 04199534608387A69115764A2723_{11}$

$29_{11}=31_{10}\to 039A32146818574A71078964292536_{11}$

У дванадцятковій системі: (Шаблон:OEIS)

$5_{12}=5_{10}\to 2497_{12}$

$7_{12}=7_{10}\to 186A35_{12}$

$15_{12}=17_{10}\to 08579214B36429A{7}_{12}$

$27_{12}=31_{10}\to 0478AA093598166B74311B28623A55_{12}$

$35_{12}=41_{10}\to 036190A653277397A9B4B85A2B15689448241207_{12}$

$37_{12}=43_{10}\to 0342295A3AA730A068456B879926181148B1B53765_{12}$

$45_{12}=53_{10}\to 02872B3A23205525A784640AA4B9349081989B6696143757B117_{12}$

У тринадцятковій системі: (Шаблон:OEIS)

$2_{13}=2_{10}\to 6_{13}$

$5_{13}=5_{10}\to 27A{5}_{13}$

$B_{13}=11_{10}\to 12495BA837_{13}$

$16_{13}=19_{10}\to 08B82976AC414A3562_{13}$

$25_{13}=31_{10}\to 055B42692C21347C7718A63A0AB985_{13}$

$2B_{13}=37_{10}\to 0474BC3B3215368A25C85810919AB79642A{7}_{13}$

$32_{13}=41_{10}\to 04177C08322B13645926C8B550C49AA1B96873A{6}_{13}$

У 14-ковій системі: (Шаблон:OEIS)

$3_{14}=3_{10}\to 49_{14}$

$13_{14}=17_{10}\to 0B75A9C4D2683419_{14}$

$15_{14}=19_{10}\to 0A45C7522D398168B{B}_{14}$

$19_{14}=23_{10}\to 0874391B7CAD569A4C2613_{14}$

$21_{14}=29_{10}\to 06A89925B163C0D73544B82C7A1D_{14}$

$3B_{14}=53_{10}\to 039AB8A075793610B146C21828DA43253D6864A7CD2C971BC5B{5}_{14}$

$43_{14}=59_{10}\to 03471937B8ACB5659A2BC15D09D74DA96C4A62531287843B21C80D4069_{14}$

У 15-ковій системі: (Шаблон:OEIS)

$2_{15}=2_{10}\to 7_{15}$

$D_{15}=13_{10}\to 124936DCA5B{8}_{15}$

$14_{15}=19_{10}\to 0BC9718A3E3257D64B_{15}$

$18_{15}=23_{10}\to 09BB1487291E533DA67C5D_{15}$

$1E_{15}=29_{10}\to 07B5A528BD6ACDE73949C6318421_{15}$

$27_{15}=37_{10}\to 061339AE2C87A8194CE8DBB540C26746D5A{2}_{15}$

$2B_{15}=41_{10}\to 0574B51C68BA922DD80AE97A39D286345CC116E{4}_{15}$

У шістнадцятковій системі циклічних чисел немає.

У 17-ковій системі: (Шаблон:OEIS)

$2_{17}=2_{10}\to 8_{17}$

$3_{17}=3_{10}\to 5B_{17}$

$5_{17}=5_{10}\to 36D{A}_{17}$

$7_{17}=7_{10}\to 274E9C_{17}$

$B_{17}=11_{10}\to 194ADF7C63_{17}$

$16_{17}=23_{10}\to 0C9A5F8ED52G476B1823B{E}_{17}$

$1E_{17}=31_{10}\to 09583E469EDC11AG7B8D2CA7234FF{6}_{17}$

У 18-ковій системі: (Шаблон:OEIS)

$5_{18}=5_{10}\to 3AE{7}_{18}$

$B_{18}=11_{10}\to 1B834H69E{D}_{18}$

$1B_{18}=29_{10}\to 0B31F95A9GDAE4H6EG28C781463D_{18}$

$21_{18}=37_{10}\to 08DB37565F184FA3G0H946EACBC2G9D27E1H_{18}$

$27_{18}=43_{10}\to 079B57H2GD721C293DEBCHA86CA0F14AFG5F8E4365_{18}$

$2H_{18}=53_{10}\to 0620C41682CG57EAFB3D4788EGHBFH5DGB9F51CA3726E4DA9931_{18}$

$35_{18}=59_{10}\to 058F4A6CEBAC3BG30G89DD227GE0AHC92D7B53675E61EH19844FFA13H{7}_{18}$

У 19-ковій системі: (Шаблон:OEIS)

$2_{19}=2_{10}\to 9_{19}$

$7_{19}=7_{10}\to 2DAG58_{19}$

$B_{19}=11_{10}\to 1DFA6H538C_{19}$

$D_{19}=13_{10}\to 18EBD2HA475G_{19}$

$14_{19}=23_{10}\to 0FD4291C784I35EG9H6BA{E}_{19}$

$1A_{19}=29_{10}\to 0C89FDE7G73HD1I6A9354B2BF15H_{19}$

$1I_{19}=37_{10}\to 09E73B5C631A52AEGHI94BF7D6CFH8DG8421_{19}$

У двадцятковій системі: (Шаблон:OEIS)

$3_{20}=3_{10}\to 6D_{20}$

$D_{20}=13_{10}\to 1AF7DGI94C63_{20}$

$H_{20}=17_{10}\to 13ABF5HCIG984E27_{20}$

$13_{20}=23_{10}\to 0H7GA8DI546J2C39B61EF{D}_{20}$

$1H_{20}=37_{10}\to 0AG469EBHGF2E11C8CJ93FDA58234H5II7B{7}_{20}$

$23_{20}=43_{10}\to 0960IC1H43E878GEHD9F6JADJ17I2FG5BCB3526A4D_{20}$

$27_{20}=47_{10}\to 08A4522B15ACF67D3GBI5J2JB9FEHH8IE974DC6G381E0H_{20}$

У 21-ковій системі: (Шаблон:OEIS)

$2_{21}=2_{10}\to A_{21}$

$J_{21}=19_{10}\to 1248HE7F9JIGC36D5B_{21}$

$12_{21}=23_{10}\to 0J3DECG92FAK1H7684BI5A_{21}$

$18_{21}=29_{10}\to 0F475198EA2IH7K5GDFJBC6AI23D_{21}$

$1A_{21}=31_{10}\to 0E4FC4179A382EIK6G58GJDBAHCI62_{21}$

$2B_{21}=53_{10}\to 086F9AEDI4FHH927J8F13K47B1KCE5BA672G533BID1C5JH0GD9J_{21}$

$38_{21}=71_{10}\to 06493BB50C8I721A13HFE42K27EA785J4F7KEGBH99FK8C2DIJAJH356GI0ID6ADCF1G5D_{21}$

У 22-ковій системі: (Шаблон:OEIS)

$5_{22}=5_{10}\to 48H{D}_{22}$

$H_{22}=17_{10}\to 16A7GI2CKFBE53J{9}_{22}$

$J_{22}=19_{10}\to 13A95H826KIBCG4DJ{F}_{22}$

$19_{22}=31_{10}\to 0FDAE45EJJ3C194L68B7HG722I9KC{H}_{22}$

$1F_{22}=37_{10}\to 0D1H57G143CAFA2872L8K4GE5KHI9B6BJDE{J}_{22}$

$1J_{22}=41_{10}\to 0BHFC7B5JIH3GDKK8CJ6LA469EAG234I5811D92F_{22}$

$23_{22}=47_{10}\to 0A6C3G897L18JEB5361J44ELBF9I5DCE0KD27AGIFK2HH{7}_{22}$

У 23-ковій системі: (Шаблон:OEIS)

$2_{23}=2_{10}\to B_{23}$

$3_{23}=3_{10}\to 7F_{23}$

$5_{23}=5_{10}\to 4DI{9}_{23}$

$H_{23}=17_{10}\to 182G59AILEK6HDC{4}_{23}$

$21_{23}=47_{10}\to 0B5K1AHE496JD4KCGEFF3L0MBH2LC58IDG39I2A6877J1M_{23}$

$2D_{23}=59_{10}\to 08M51CJK65AC1LJ27I79846E9H3BFME0HLA32GHCAL13KF4FDEIG8D5JB{7}_{23}$

$3K_{23}=89_{10}\to 05LG6ADG0BK9CL4910HJ2J8I21CF5FHD4327B8C3864EMH16GC96MB2DA1IDLM53K3E4KLA7H759IJKFBEAJEGI{8}_{23}$

У 24-ковій системі: (Шаблон:OEIS)

$7_{24}=7_{10}\to 3A6KD{H}_{24}$

$B_{24}=11_{10}\to 248HALJF6D_{24}$

$D_{24}=13_{10}\to 1L795CM3GEI{B}_{24}$

$H_{24}=17_{10}\to 19L45FCGME2JI8B{7}_{24}$

$17_{24}=31_{10}\to 0IDMAK327HJ8C96N5A1D3KLG64FBE{H}_{24}$

$1D_{24}=37_{10}\to 0FDEM1735K2E6BG54CN8A91MGKI3L9HC7IJ{B}_{24}$

$1H_{24}=41_{10}\to 0E14284G98IHDB2M5KBGN9MJLFJ7EF56ACL1I3C{7}_{24}$

У 25-ковій системі єдине циклічне число:

$2_{25}=2_{10}\to C_{25}$

Зауважимо, що для трійкової основи ($b=3$) випадок $p=2$ дає 1, що за правилами не є циклічним числом (тривіальний випадок, одна цифра). Тут же цей випадок наведено для повноти теорії, що всі числа отримуються таким способом.

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

Див. також

• Десятковий дріб
• Мала теорема Ферма
• Шаблон:Нп

Джерела

• Шаблон:Cite web
• Шаблон:Cite book
• Шаблон:Cite book; Шаблон:ISBN; Шаблон:УДК; ББК 88.37.

Література

• Dan Kalman. Fractions with Cycling Digit Patterns // The College Mathematics Journal. — 1996. — Март (т. 27, вып. 2). — С. 109—115.
• John Leslie. The Philosophy of Arithmetic: Exhibiting a Progressive View of the Theory and Practice of ….. — Longman, Hurst, Rees, Orme, Brown, 1820. — ISBN 1-4020-1546-1.
• David Wells. The Penguin Dictionary of Curious and Interesting Numbers. — Penguin Press. — ISBN 0-14-008029-5.

Посилання

• Шаблон:MathWorld
• Шаблон:Youtube