Период нечетной дроби онлайн. Первые полторы тысяч разложений.

Период нечетной дроби онлайн. Первые полторы тысяч разложений.

Целое число, не более 50 000. Не имеющих множителей 2 и 5.
Период дроби
Цифры периода

В этом материале рассмотрим тему из теории чисел: простые дроби и их свойства. Тема достаточно интересная, не до конца изученная и думаю, будет интересно взглянуть на неё еще раз.

О чем же идет речь?

Как известно любая дробь вида \(\cfrac{1}{N}\), где N - натуральное (целое и положительное) число, и не имеющая в множителях числа 2 и 5 - обладает таким свойством как период.

Например в числах

\(\cfrac{1}{13}=0.07692307692307692307692307692308\)

\(\cfrac{1}{41}=0.02439024390243902439024390243902\)

\(\cfrac{1}{101}=0.00990099009900990099009900990099\)

\(\cfrac{1}{91}=0.01098901098901098901098901098901\)

несложно заметить, что в правой части  числа повторяются

для числа \(13\) это \(076923\), для \(41\) это \(02439\), для \(101\) это \(0099\), для \(91\) это \(010989\)

Это и есть период числа. Основная задача, связанная с нахождением периода дробей - это то что они не подчинены какому то известному правилу.

То есть у дроби числа 17  период равен 16, а период числа 11 уже равен 2. У числа 7 период 6, а у \(7^2\) равен 42.

 

Как же можно определить период простой дроби?

Используем утверждение что для любого простого числа p, кроме 2 и 5, верно утверждение

\(10^{p-1}mod p=1\)

То есть, взяв остаток от десяти в 18 степени при делении его на 19 мы получим единицу (1)

Это работает всегда и на всех числах взаимно простых с десятью. В общем виде это называется - малая теорема Ферма, а мы лишь рассмотрели частный случай где основание равно 10.

Так вот период простой дроби всегда! кратен числу \({p-1}\)

Судите сами

Число 11  \(p-1=10\)  а период равен 2

число 41  \(p-1=40\)  а период равен 5

число 101  \(p-1=100\)  а период равен 4

число 19  \(p-1=18\)  а период равен 18

число 6  \(p-1=6\)  а период равен 6

Кроме этого, обозначив период буквой \(T\) мы легко можем доказать что \(10^{T}mod p=1\)

Таким образом, возводя 10 в степень 1,2,3..... и деля его на заданное простое число мы получаем  остатки.

Как только остаток равен 1 - всё, мы нашли период простой дроби.

Простой перебор хорошо работает на сравнительно небольших числах, а что делать когда когда простая дробь  имеет в своем знаменателе число из десятков цифр?

Необходимо разложить \(p-1\) на множители и перебрать все сочетания множителей, для того что бы подставить значение в степень.

Мы остановимся на полном переборе, только лишь для того  что бы рассчитать не только период, но и определить все цифры в этом периоде.

Как это делаю я?

Представим \(10^{p-1}mod p=1\) как  \(10*M=1+p*K\), где \(K\) и \(M\) - какие  то целые числа.

Получили линейное диофантово уравнение с двумя переменными

Давайте сразу на примере, Возьмем число 41.

Итак первый шаг

\(10M-41P=1\) Заменим \(P\) на \(-P\), да бы избавится от минуса.

Решая уравнение \(10M-41P=1\) мы получим что \(M=37+41R\)

Зная, что \(M\) - это степень десятки - мы можем представить как  \(M=10W\)

то есть \(10W=37+41R\), где \(R\) и \(W\) - какие  то целые числа.

То есть снова получили диофантово уравнение, которое так же решаем.

Не проходя каждый шаг, я Вам напишу какие же числа получаются 1,37,16,18,10,1,37....

Заметили что сделав 5 итераций, мы вернулись к исходной единице? Так вот - это количество и есть период простой дроби.

В принципе пока ничего сложного, более того читатель скажет: "и в чем же смысл, я также могу и  десять возводить в степень и брать остаток, и получится даже быстрее"

Совершенно согласен, но речь идет в материале немного о другом - о более широком понимании простых дробей и их периодов.

Но раз уж захотели брать остатки...

Диофантово уравнение решать на каждом этапе конечно же не очень удобно, а как можно это упростить?

Вычислив первый раз значение остатка 37, нам в принципе решать диофантово уравнение нет необходимости. Мы просто берем остатки от числа 37 в степени,2,3,4.... при делении его на 41

\(37^{0}mod 41=1\) 

\(37^{1}mod 41=37\) 

\(37^{2}mod 41=16\) 

\(37^{3}mod 41=18\) 

\(37^{4}mod 41=10\)

Такая схема уже сравнима с простым перебором как предложил неизвестный читатель.

Что еще можно вытащить из алгоритма что использует диофантовы уравнения?

Например мы можем  узнать все цифры в периоде.

 \(10*M=1+p*K\) решая это уравнение мы нашли чему равно \(M\) но не нашли чему равно \(K\)

при \(p=41\) 

\(K=9\)

Теперь умножая каждый остаток \(1, 37, 16, 18, 10\) на \(K\) и беря последнюю цифру, мы получим значение периода, который "перевернут" то есть читается не справа налево, а слева направо.

в нашем примере это будет \(9, 3, 4, 2, 0\)

то есть период дроби равен 0.(02439) 

Теперь рассмотрим на примере  дроби \(\cfrac{1}{117}\)

1. Решая диофантовое уравнение \(10*M+117*K=1\), получим пару значений \(M=82, K=7\).  Последняя цифра в периоде будет 7

2. \(82^{2}mod 117=55\) , Значит \(M=55\) а предпоследняя цифра в периоде будет  \(82*7mod 10=4\)  4(четыре)

3. \(82^{3}mod 117=64\) , Значит \(M=64\) а предыдущая цифра в периоде будет  \(55*7mod 10=5\)  5(пять)

3. \(82^{4}mod 117=100\) , Значит \(M=100\) а предыдущая цифра в периоде будет  \(64*7mod 10=8\)  8(восемь)

3. \(82^{4}mod 117=10\) , Значит \(M=10\) а предыдущая цифра в периоде будет  \(100*7mod 10=0\)  0(ноль)

3. \(82^{5}mod 117=1\) , Значит \(M=1\) а  и первая цифра в периоде будет  \(10*7mod 10=0\)  0(ноль)

Раз мы достигли \(M=1\)   на 5 шаге, следовательно наш период  равен 6-ти.

И наш ответ \(\cfrac{1}{117}=0.008547008547005847008547.......\)

 Предлагаем  для ознакомления таблицу дробей простых чисел до 1500, и их периодов 

 

Число Период Число Период Число Период
3 1 421 140 947 473
7 6 431 215 953 952
11 2 433 432 967 322
13 6 439 219 971 970
17 16 443 221 977 976
19 18 449 32 983 982
23 22 457 152 991 495
29 28 461 460 997 166
31 15 463 154 1009 252
37 3 467 233 1013 253
41 5 479 239 1019 1018
43 21 487 486 1021 1020
47 46 491 490 1031 103
53 13 499 498 1033 1032
59 58 503 502 1039 519
61 60 509 508 1049 524
67 33 521 52 1051 1050
71 35 523 261 1061 212
73 8 541 540 1063 1062
79 13 547 91 1069 1068
83 41 557 278 1087 1086
89 44 563 281 1091 1090
97 96 569 284 1093 273
101 4 571 570 1097 1096
103 34 577 576 1103 1102
107 53 587 293 1109 1108
109 108 593 592 1117 558
113 112 599 299 1123 561
127 42 601 300 1129 564
131 130 607 202 1151 575
137 8 613 51 1153 1152
139 46 617 88 1163 581
149 148 619 618 1171 1170
151 75 631 315 1181 1180
157 78 641 32 1187 593
163 81 643 107 1193 1192
167 166 647 646 1201 200
173 43 653 326 1213 202
179 178 659 658 1217 1216
181 180 661 220 1223 1222
191 95 673 224 1229 1228
193 192 677 338 1231 41
197 98 683 341 1237 206
199 99 691 230 1249 208
211 30 701 700 1259 1258
223 222 709 708 1277 638
227 113 719 359 1279 639
229 228 727 726 1283 641
233 232 733 61 1289 92
239 7 739 246 1291 1290
241 30 743 742 1297 1296
251 50 751 125 1301 1300
257 256 757 27 1303 1302
263 262 761 380 1307 653
269 268 769 192 1319 659
271 5 773 193 1321 55
277 69 787 393 1327 1326
281 28 797 199 1361 680
283 141 809 202 1367 1366
293 146 811 810 1373 686
307 153 821 820 1381 1380
311 155 823 822 1399 699
313 312 827 413 1409 32
317 79 829 276 1423 158
331 110 839 419 1427 713
337 336 853 213 1429 1428
347 173 857 856 1433 1432
349 116 859 26 1439 719
353 32 863 862 1447 1446
359 179 877 438 1451 290
367 366 881 440 1453 726
373 186 883 441 1459 162
379 378 887 886 1471 735
383 382 907 151 1481 740
389 388 911 455 1483 247
397 99 919 459 1487 1486
401 200 929 464 1489 248
409 204 937 936 1493 373
419 418 941 940 1499 214

 

 

Поиск по сайту