Вероятно, читатель знает (а если нет ещё лучше: он узнает это из нашей статьи), что всякая обыкновенная дробь представляется периодической десятичной дробью (конечную десятичную дробь мы можем считать периодической с Но вряд ли многие представляют, сколько неожиданностей заключает в себе эта периодическая дробь. Рассмотрим три примера:
7
12
13
Мы видим, что у чисел 1 / 7 и 1 / 13 период начинается сразу после запятой и состоит из шести цифр (142857 и 076923 соответственно), а у он начинается с третьей позиции после запятой и состоит из единственной Внимательное рассмотрение периодов позволяет заметить ещё одно обстоятельство. Именно, положим (период и будем последовательно умножать
2 N = 285714, | 3 N = 428571, |
4 N = 571428, | 5 N = 714285, |
6 N = 857142, | 7 N = 999999. |
Мы видим, что первые пять из этих чисел получаются из числа N «круговой перестановкой» цифр: цифр из конца числа переезжает в начало; а состоит из одних девяток. Теперь проделаем то же с периодом
2 N = 153846, | 3 N = 230769, |
4 N = 307692, | 5 N = 384615, |
6 N = 461538, | 7 N = 538461, |
8 N = 615384, | 9 N = 692307, |
10 N = 769230, | 11 N = 846153, |
12 N = 923076, | 13 N = 999999. |
Здесь дело обстоит несколько иначе, но всё равно интересно: пять из выписанных 4 N , 9 N , получаются из числа N круговой перестановкой цифр, другие шесть 5 N , 6 N , 7 N , получаются круговой перестановкой цифр друг из друга и, наконец, состоит из одних девяток.
Можно заметить ещё вот что. Если взять любое из выписанных выше шестизначных чисел, кроме числа 999999, «разломить» его на два трёхзначных числа и вычислить сумму этих половинок, то получится 999; например,
Как видите, с периодическими десятичными дробями связано немало загадок. Некоторые из этих загадок остаются не разгаданными по сей день, несмотря на многочисленные попытки, предпринимавшиеся на протяжении нескольких веков математиками из разных стран, как великими, так и более «скромными». Всё же об этом мы можем рассказать.
Хобби Иоганна Бернулли
Оставим на время периоды и перенесёмся в Швейцарию конца XVIII века. Мы наблюдаем странную картину: маститый математик Иоганн III Бернулли, представитель знаменитой математической семьи Бернулли, удостоившейся, подобно королевским династиям, присоединения порядковых номеров к именам, занимается, можно сказать, детской игрой! Он разлагает на простые множители числа, записываемые одними единицами: 11 = 11, В 1773 году Бернулли помещает в трудах Берлинской академии таблицу простых делителей чисел, составленных из до Несмотря на то, что ему не удалось найти делители для некоторых чисел этого вида 17, 29), а для трёх чисел 25, 27) разложение не доведено до простых множителей, несмотря на допущенные им ошибки (для 24, 26), мы сегодня можем только преклоняться перед гигантским трудом по вычислению простых множителей этих огромных чисел. Можно предположить, что автором таблицы двигала не только исследовательская жилка учёного, но и подлинная эстетическая страсть художника, вдохновлённого удивительным притягательным миром этой загадочной вереницы единиц. Свои сомнения в правильности разложения в отдельных случаях И. Бернулли отражает звёздочкой.
Рис. 1.
В течение первых ста лет, прошедших со времени опубликования таблицы И. Бернулли, в неё не было внесено особой ясности. В 1838 году Вестерберг разложил на простые множители число из и это всё. В 1879 году французский математик Эдуард Люка находит простые делители для и признаёт, что цепочка из не поддаётся разложению. В 1895 году в Париже выходит его книга «Занимательная арифметика», содержащая приведённую ниже таблицу.
Таблица | |
111 = | 3 · 37 |
1111 = | 11 · 101 |
11111 = | 41 · 271 |
111111 = | 3 · 7 · 11 · 13 · 37 |
1111111 = | 239 · 4649 |
11111111 = | 11 · 73 · 101 · 137 |
111111111 = | 3² · 37 · 333667 |
1111111111 = | 11 · 41 · 271 · 9091 |
11111111111 = | 1121649 · 513239 |
111111111111 = | 3 · 7 · 11 · 13 · 37 · 101 · 9901 |
1111111111111 = | 53 · 79 · 265371653 |
11111111111111 = | 11 · 239 · 4649 · 909091 |
111111111111111 = | 3 · 31 · 37 · 41 · 271 · 2906161 |
1111111111111111 = | 11 · 17 · 73 · 101 · 137 · 5882353 |
11111111111111111 = | 2071723 · 5363222357 |
111111111111111111 = | 3² · 7 · 11 · 13 · 19 · 37 · 52579 · 333667 |
Угасший было интерес к числам, составленным из единиц, вновь возрос в последние годы, особенно в связи с развитием теории арифметических кодов, служащей основой для реализации методов помехоустойчивого кодирования в компьютерной технике (см., например, книгу Ю. Г. Дадаева «Теория арифметических кодов», изданную в Москве в 1981 г.). Наши загадочные числа, спустя почти двести лет после опубликования первой таблицы их делителей, приобретают, наконец, собственное имя. В «Занимательной теории чисел» 1964 г.) её автор А. Бейлер, посвятив этим числам целую главу под названием «111. 1111», вводит для них термин «repunit» (сокращение английского repeated unit повторенная единица). Русского слова «репьюнит» ещё не найти в словарях, но оно уже появляется в рефератах к зарубежным статьям, приобретая силу нового международного термина.
Математики продолжают штурмовать таблицу делителей репьюнитов, и к n в таблице уже достигает 3000 (С. Ейтс), однако в ней ещё достаточно много пробелов. (К настоящему времени часть этих пробелов ликвидирована и найдены делители. репьюнитов включительно). Отдельный интерес представляют простые репьюниты, поиск которых также продолжается. Уже доказано, что и репьюниты простые.
Нас, однако, репьюниты интересуют не сами по себе, а в связи с периодами десятичных дробей. Существование связи между теми и другими предвидел и Бернулли, который одновременно с уже упоминавшейся таблицей делителей репьюнитов опубликовал обзор известных к тому времени результатов о периодах десятичных дробей, включавший в себя пространную таблицу этих периодов В действительности, эта связь, как мы сейчас увидим, лежит на поверхности.
Рис. 2.
Делители репьюнитов и
представление обыкновенных дробей десятичными
Начнём с трёх простых наблюдений.
Наблюдение 1 . Предположим, что число 999. 999, составленное из n девяток, делится на данное натуральное Запишем частное от деления в виде числа :
999. 999 |
a 1 a 2 a 3 . a n
( где несколько первых цифр a i могут быть нулями ). Тогда
m
Наблюдение 2 . Если число m не делится на 3, то делимость на m числа, составленного из равносильна делимости числа, составленного из
Наблюдение 3 . Если число m не делится на 2 и на 5, то найдётся репьюнит, делящийся
Доказательство . Будем последовательно находить остатки от деления чисел 1, 11, 111 Последовательность этих остатков бесконечна, но в то же время для них имеется только значений Поэтому найдутся два разных репьюнита с одинаковыми остатками от деления («принцип Дирихле»!). Разность этих репьюнитов делится в то же время она имеет вид произведением некоторого репьюнита на некоторую степень Но взаимно просто значит, последний репьюнит делится
Теперь мы можем сформулировать Важный Результат.
Теорема 1 . Если натуральное число m не делится на 2 и на 5, то период десятичной дроби , начинается сразу после запятой. Его длина равна наименьшему n, при котором число, составленное из делится Сам период равен частному от деления этого числа из девяток записанному как число ( возможно, с нулями в начале ). Если m не делится и на 3, то можно также сказать, что длина периода равна номеру первого репьюнита, делящегося на m .
Всё это нами уже доказано. Между прочим, из этой теоремы вытекает следующий, довольно неожиданный результат.
Следствие . Если m не делится на 2, 3 и 5, то период десятичной дроби , делится на 9.
Действительно, если m не делится на 3, то число делится на 9.
Утверждения о периодах в случаях, не охватываемых мы приведём в качестве упражнений.
Упражнение 1 . Пусть m = 2 a 5 b m’ , где m’ не делится ни ни и пусть Тогда период десятичной дроби, начинается с позиции после запятой и имеет такую же длину, как период
Доказательство этого утверждения опирается на лемму: если р и q взаимно просты, то найдутся целые положительные A и B такие, что
Упражнение 2 . Если р и q взаимно просты, то период десятичной дроби, имеет такую же длину, как период десятичной
Наконец, можно усилить наше следствие.
Упражнение 3 . Если q не делится на 3, то при период десятичной дроби, делится на 9.
Теперь мы приступаем к изучению зависимости длин периодов от знаменателей. В этом изучении нам поможет, наряду с теоремой 1,
Малая теорема Ферма
В отличие от своей «Великой теоремы» малую теорему Пьер Ферма снабдил доказательством: он изложил его в в одном из писем. Теорема формулируется так:
Если p простое число и a произвольное натуральное число, не делящееся на p, то делится на p .
Мы не приводим доказательства этой теоремы (хотя читатель, который проделает все упражнения к этой статье, вероятно сможет её доказать). Её доказательство имеется в популярной литературе (см., например, книгу Р. Куранта и Г. Роббинса «Что такое математика?», переизданную в Москве в 1976 г.). Нас эта теорема интересует, главным образом, как средство доказательства фундаментального свойства периодов.
Длина периода дроби с простым знаменателем
Теорема 2 . Если p есть простое число, отличное от 2 и 5, то длина периода является делителем числа
Доказательство . Согласно теореме 1, длина периода есть наименьшее такое, что число, составленное из делится В то же время в силу малой теоремы Ферма число т.е. число, составленное из девяток, делится Мы должны доказать, что делится Если то доказывать нечего; предположим, что Числа, составленные из и n девяток, делятся дополним второе из них нулями до числа и составим разность полученных чисел:
| 999. 999 999. 999 999. 999 000. 000 |
999. 999 |
Это число составлено из p 1 n девяток, и оно тоже делится Проделав ещё одно подобное вычитание, мы находим, что делится число, составленное из девяток, потом из девяток В конце концов мы придём к числу, в котором девяток меньше, и тут есть две возможности. Либо это число вообще будет нулём, но это как раз и значит, что делится Либо в этом числе девяток будет но а это противоречит тому, что n наименьшая возможная длина числа из девяток, которое делится Теорема доказана.
Обозначим для числа m через L ( m ) длину периода десятичной дроби, Мы доказали, что если p простое число, то есть делитель числа Но какой? Посмотрим на таблицу И. Бернулли (рис. 2). Мы видим, что Ясности не много.
С точки зрения соотношения между длиной периода и все простые подразделяются на три категории:
- «полнопериодные» простые, у которых длина периода меньше знаменателя:
- «неполнопериодные» простые с нечётной длиной периода:
- «неполнопериодные» простые с чётной длиной периода:
Кропотливая работа математиков по выявлению какой-нибудь закономерности в расположении этих групп среди всех простых чисел увенчалась неожиданным результатом. Было обнаружено достаточно устойчивое отношение численностей этих групп в пропорции при этом были использованы таблицы длин периодов для простых знаменателей до 1 370 471 включительно (С. Ейтс, 1975 г.). Были получены и другие общие результаты, причём оказалось, что большое значение при определении длины периода с имеет остаток от деления Например, если этот остаток 27, 31, 39, то нечётно, а если то чётно. Всё же задача вычисления чисел для видимо, далека от решения.
Случай непростого знаменателя
Упражнение 4 . Если p 1 и p 2 взаимно просты между собой и то есть наименьшее общее кратное чисел и
Поскольку всякое натуральное число есть произведение степеней простых, которые между собой взаимно просты, последнее утверждение сводит задачу вычисления длины периода к случаю, когда знаменатель есть степень простого числа. А здесь снова нет ясности: например,
Теперь нам пора оставить длины периодов и обратиться к объяснению феноменов, обнаруженных в начале статьи.
Эффект круговой перестановки
Напомним, в чём он состоит. Мы видели, что шестизначный период при умножении 3, 4, подвергается круговой перестановке: цифр из конца числа переезжает в начало. Несколько иначе ведёт себя при умножении на различные числа шестизначный период Впрочем, что именно с ним происходит, читатель может вспомнить, заглянув в начало статьи, а мы сейчас докажем теорему, более или менее объясняющую это явление.
Теорема 3 . Пусть N есть период дроби 1/ m ( записанный как число, возможно, начинающееся одним или несколькими нулями ), где m взаимно просто с 10, и пусть l есть остаток от деления Тогда получается из перестановкой из начала числа в конец .
Доказательство . Пусть M есть целая часть числа т.е. Умножим десятичную при этом запятая переедет на влево. Целая часть получившегося числа Отбросим целую часть. Получится число
10 k | 1 |
m
Это периодическая десятичная дробь, период которой получается из периода круговой перестановкой цифр: переезжает из начала в конец; но в то же время это число больше а значит, и его период больше периода Теорема доказана.
Если число 1/ m имеет ( m 1 )-значный период, то доказанная теорема всё объясняет. Действительно, круговыми перестановками цифр из периода можно получить чисел (включая его самого), и все эти числа различны. С другой стороны, умножая период мы тоже получаем чисел; значит, это в точности те же числа. Если же период короче, то круговые перестановки цифр не исчерпывают всех чисел с Всё, что можно сказать в этом случае это что круговая перестановка цифр всегда приводит к числу это доказывается точно так же, как теорема 3.
Интересно, что теорема 3 в некотором смысле обращается:
Теорема 4 . Пусть N есть целое число ( запись которого, возможно, начинается нулём или несколькими нулями ), и пусть A есть число, составляемое последними Предположим, что при перенесении из конца в начало оно превращается в где Тогда периодическая десятичная равна ( Последняя дробь может оказаться сократимой .)
Доказательство . Пусть n число знаков При перенесении из конца в начало оно превращается в число
10 k
10 k
N A + A ·1 0 n = l N ·1 0 k ,
N (10 n k l 1) |
A
0, NNN . · | 10 n k l 1 |
A
что нам и требуется.
Сами того не желая, мы научились решать один тип олимпиадных задач. Вот пример.
Задача . Найти все шестизначные числа, которые увеличиваются в целое число раз при перенесении последней цифры из конца в начало . (Мы будем считать, как это обычно делается, что число начинается не с нуля; задачу мы можем и без этого предположения, но ответ будет чересчур громоздок: он будет включать в себя числа 000001, 000009, 000011, Мы будем также понимать слово «увеличивается» буквально, т.е. исключим случай, когда число остаётся при перенесении цифры неизменным; в противном случае в ответ вошли бы числа 111111, 999999.)
Решение . Пусть A последняя цифра нашего числа, и пусть при её перенесении в начало число увеличивается в Таким образом, В силу теоремы 4 наше число есть шестизначный период (возможно, сократимой) дроби Знаменатель этой дроби до сокращения может быть одним из 29, 89; после сокращения на однозначное число знаменатель может превратиться ещё в Так как период дроби шестизначный, знаменатель должен быть делителем числа Это оставляет для него только три возможности: 7, 13, 39. Таким образом, При наша дробь где (дробь должна быть поскольку период не должен начинаться с нуля). Период такой дроби есть (период есть 025641). При дробь и должна сокращаться что оставляет для неё единственную период равен 142857. Итак,
Ответ : 102564, 128205, 142857, 153846, 179487, 205128, 230769.
Упражнение 5 . Решите аналогичную задачу для чисел.
Указание . Воспользуйтесь таблицей делителей репьюнитов.
Теорема 5 . Пусть q простое число, большее 5, и пусть Предположим, что период есть Далее, обозначим число, образуемое первыми периода, и число, образуемое его последними Тогда
Доказательство . По условию,
N = 10 n N 1 + N 2 , | p |
10 2 n 1
Поскольку 2 n есть наименьшее k , при котором делится не делится а так как q простое число, то взаимно просто Значит, делится на Но в то же время это числа, которые не оба состоят из одних девяток. Значит, и, таким образом, что и требовалось доказать.
Заметим, что простота q использовалась нами только в одном месте: мы вывели из неё, что взаимно просто Разумеется, эта взаимная простота может наступить и при так что заключение нашей теоремы справедливо и при многих непростых знаменателях.
Ещё один эффект
Рассмотрим снова период дроби 1 / 7 : N = 142857. Возведём его в квадрат отделим последние шесть цифр и сложим с тем, что останется:
122449 + 20408 = 142857.
Получился снова наш период. Проделаем подобное с периодом
Получился, правда, не наш исходный период, но число, отличающееся от него на круговую перестановку цифр. Аналогичное для периода
10 февраля 2012
Помните, как в самом первом уроке про десятичные дроби я говорил, что существуют числовые дроби, не представимые в виде десятичных (см. урок «Десятичные дроби»)? Мы еще учились раскладывать знаменатели дробей на множители, чтобы проверить, нет ли там чисел, отличных от 2 и 5.
Так вот: я наврал. И сегодня мы научимся переводить абсолютно любую числовую дробь в десятичную. Заодно познакомимся с целым классом дробей с бесконечной значащей частью.
— это любая десятичная дробь, у которой:
- Значащая часть состоит из бесконечного количества цифр;
- Через определенные интервалы цифры в значащей части повторяются.
Набор повторяющихся цифр, из которых состоит значащая часть, называется дроби, а количество цифр в этом наборе — . Остальной отрезок значащей части, который не повторяется, называется .
Поскольку определений много, стоит подробно рассмотреть несколько таких дробей:
Эта дробь встречается в задачах чаще всего. Непериодическая часть: 0; периодическая часть: 3; длина периода: 1.
Непериодическая часть: 0,58; периодическая часть: 3; длина периода: снова 1.
Непериодическая часть: 1; периодическая часть: 54; длина периода: 2.
Непериодическая часть: 0; периодическая часть: 641025; длина периода: 6. Для удобства повторяющиеся части отделены друг от друга пробелом — в настоящем решении так делать не обязательно.
Непериодическая часть: 3066; периодическая часть: 6; длина периода: 1.
Как видите, определение периодической дроби основано на понятии значащей части числа. Поэтому если вы забыли что это такое, рекомендую повторить — см. урок «Умножение и деление десятичных дробей».
Переход к периодической десятичной дроби
Рассмотрим обыкновенную дробь Разложим ее знаменатель на простые множители. Возможны два варианта:
- В разложении присутствуют только множители 2 и 5. Эти дроби легко приводятся к десятичным — см. урок «Десятичные дроби». Такие нас не интересуют;
- В разложении присутствует что-то еще, кроме 2 и 5. В этом случае дробь непредставима в виде десятичной, зато из нее можно сделать периодическую десятичную дробь.
Чтобы задать периодическую десятичную дробь, надо найти ее периодическую и непериодическую часть. Как? Переведите дробь в неправильную, а затем разделите числитель на знаменатель «уголком».
При этом будет происходить следующее:
- Сначала разделится целая часть, если она есть;
- Возможно, будет несколько чисел после десятичной точки;
- Через некоторое время цифры начнут повторяться.
Вот и все! Повторяющиеся цифры после десятичной точки обозначаем периодической частью, а то, что стоит спереди — непериодической.
Задача. Переведите обыкновенные дроби в периодические десятичные:
Все дроби без целой части, поэтому просто делим числитель на знаменатель «уголком»:
Как видим, остатки повторяются. Запишем дробь в «правильном» виде:
В итоге получается дробь:
Записываем в нормальном виде:
Переход от периодической десятичной дроби к обыкновенной
Рассмотрим периодическую десятичную дробь Требуется перевести ее в классическую «двухэтажную». Для этого выполним четыре простых шага:
- Найдите период дроби, т.е. подсчитайте, сколько цифр находится в периодической части. Пусть это будет
- Найдите значение выражения Это равносильно сдвигу десятичной точки на полный период вправо — см. урок «Умножение и деление десятичных дробей»;
- Из полученного числа надо вычесть исходное выражение. При этом периодическая часть «сжигается», и остается обычная дробь;
- В полученном уравнении найти X . Все десятичные дроби переводим в обыкновенные.
Задача. Приведите к обыкновенной неправильной дроби числа:
Работаем с первой дробью:
В скобках содержится лишь одна цифра, поэтому период Далее умножаем эту дробь Имеем:
10 X = 10 · 9,6666 . = 96,666 .
Вычитаем исходную дробь и решаем уравнение:
10 X − X = 96,666 . − 9,666 . = 96 − 9 = 87;
9 X = 87;
X = 87/9 = 29/3.
Теперь разберемся со второй дробью. Итак,
Период k = 2, поэтому умножаем все
100 X = 100 · 32,393939 . = 3239,3939 .
Снова вычитаем исходную дробь и решаем уравнение:
100 X − X =
99 X = 3207;
X = 3207/99 = 1069/33.
Приступаем к третьей дроби: Схема та же самая, поэтому я просто приведу выкладки:
Период k = 1 ⇒ умножаем все на 10 k = 10 1 = 10;
10 X = 10 · 0,30555 . = 3,05555 .
10 X − X =
9 X = 11/4;
X = (11/4) : 9 = 11/36.
Наконец, последняя дробь: Опять же, для удобства периодические части отделены друг от друга пробелами. Имеем:
k = 4 ⇒
10 000 X = 10 000 · 0,2475 2475 = 2475,2475 .
10 000 X − X = 2475,2475 . − 0,2475 2475 . = 2475;
9999 X = 2475;
X = 2475 : 9999 = 25/101.
Задача : на вход в функцию подается два целых числа (int(a), int(b)) . Вернуть нужно частное a/b , причем повторяющиеся числа (период) нужно взять в скобки.
Подошел к решению задачи методом брутфорса. Перебирал дробную часть , искал совпадения. Но в случае 1/117 в период входит более 90 чисел и перебор чисел занимает больше времени, чем позволено в задаче.
Как по-другому решить эту задачу? Может есть более элегантное решение?
3 ответа 3
Для поиска периода рационального числа существует отдельный алгоритм. Перебираем одну за другой степени числа 10: 10, 100, 1000, 10000 и т.д. Смотрим на остаток от деления этого числа на знаменатель. Если остаток от деления равняется 1, значит степень числа 10, это длина периода. Например, если в знаменателе стоит 13, то:
Получается, период равен 6. Этот период не зависит от того, что стоит в числителе (если дробь сокращена).
Метод не работает, если знаменатель делится на 5 или 2. В таком случае его нужно делить на 2, или 5, пока получится число, которое не делится на 2, 5.
В общем случае (как для вашего примера 1/117), придется использовать длинную арифметику.
Алгоритм ищет только длину периода, что бы получить сам период, нужно делить самому.