Как-то классе в 4-ом откопал я в библиотеке книжку под названием «Волшебный двурог». И то, что я прочитал в ней, показалось мне на ступень выше, чем в приключениях Нулика, известной тогда серии книжек по занимательной математике, публикуемых в журнале «Пионер». И одним из чудес «Двурога» было волшебное колесо с цифрами 142857. Оказывается, что если столбиком делить 1 на 7, то получится эта последовательность цифр. Но это не все: если продолжать деление дальше, то опять получится эта же последовательность и так далее, до бесконечности. И мне захотелось сделать еще одно такое колесо…
Не иначе как в учебнике алгебры издания 68 года (автор, кажется, Барсуков) мной был встречен удивлявший уже тогда алгоритм вычисления квадратного корня столбиком. Ну деление – это еще понятно. А как корень-то столбиком, неужели возможно? По причине этих недоумений данный алгоритм, казалось, не имел успеха у публики. Но не для той ее части, для которой математика была частью жизни.
О таких алгоритмах (и для такой публики) – эта статья.
Содержание
«Хорошие» и «плохие» простые числа. Перевод периодических дробей в другую систему счисления. Целочисленное решение уравнений: (Деление. Квадратный корень. Кубический корень. Логарифм: (рекуррентное уравнение, развертка степенных выражений, неожиданные числа Фибоначчи, естественная последовательность)). Аппендикс для корня квадратного.
*«Хорошие» и «плохие» простые числа
Как-то классе в 4-ом откопал я библиотеке книжку под названием «Волшебный двурог». Автора теперь уже и не вспомню, но это точно был не Левин, автор известного тогда цикла произведений о приключениях Нулика – я тоже читывал эти книжки. Но то, что я прочитал в «Волшебном двуроге», показалось мне на ступень выше, чем в приключениях Нулика. И одним из этих чудес было волшебное колесо с цифрами 142857. Оказывается, что если столбиком делить 1 на 7, то получится эта последовательность цифр. Но это не все: если продолжать деление дальше, то опять получится эта же последовательность и так далее до бесконечности. Потом я узнал, что это называется периодическая десятичная дробь, и что записывается это так: 1/7= 0,(142857). Но и это еще не все: если делить не 1, а 2 опять же на 7, то получается последовательность 285714! То есть наше волшебное колесо повернется на 2 деления вперед. Если делить 3 на 7, то получится 428571 в периоде. И так далее, пока наше колесо не побывает во всех положениях.
После этого я сам стал делать подобные эксперименты и очень скоро понял, что непростые числа (к каким не относится число 7) не годятся в том смысле, что периоды они дают всяко короче, чем простые. То ли дело простые! 7 дает 6-членный период, а 17 – вообще 16-членный! Получалось, что количество цифр в периоде на 1 меньше самого простого числа. Представляете: берем простое число где-то рядом с 1000000, и получаем случайную последовательность из миллиона цифр!
Все бы хорошо, но вот обратил я внимание еще на два простых числа – 3 и 9, которые вовсе не укладывались в вышеприведенную схему: 1/3=0,(3), а 1/9= 0,(1). Недалеко от них ушло и число 11, ведь 1/11=0,(09). Но более всего неприятно поразили тоже простые 2 и 5, которые дают вообще конечные десятичные дроби! Все эти «дефектные» простые числа я назвал плохими, в противоположность, разумеется, хорошим: 7, 17, 19, 23, 29 и и тому подобное. Пребывая при этом в полной уверенности, что хороших все-таки больше, чем плохих.
Назвать-то назвал, но это ведь только полдела (хотя уже и начало его). В чем источник дурного нрава простых чисел – вот каков был главный вопрос. Чтобы ответить на него, возьмем на заметку следующее обстоятельство: 1/11= 0,(09) и 1/99= 0,(01). Отсюда уже недалеко до разгадки. Еще не мешает нам взять на заметку и следующие с намеком разложения на простые числа особо построенных чисел:
9= 3^2; 99= 3^2*11; 999= 3^3*37; 9999= 3^2*101; 99999= 3^2*41*271
* Перевод периодических дробей в другую систему счисления
Теперь посмотрим на вопрос с другой стороны. Пусть имеется периодическая дробь 0,(142857). Как перевести ее в другую систему счисления? Как перевести само число 142857 – известно. Нужно делить на основание системы счисления (СС) с остатком, записывать остаток, затем полученный результат деления опять делить на основание СС и записывать остаток, пока не получится число, меньшее основания СС, Последовательность остатков, прочитанная в обратном порядке – это и есть результат конверсии. Если брать основание СС= 11, то получается 98370. Но заключать отсюда, что 0,(142857) (в 10—ичной) = 0,(98370) ( в 11-ичной) – это ошибка.
А что если нам делать полностью обратную описанной выше процедуру конверсии? А именно: умножаем исходную дробь на основание СС, целую часть частного записываем в результат конверсии, а дробную часть – вновь умножаем на основание СС и так далее, пока в результате не начнется второй период. Последовательность целых частей, прочитанная в прямом порядке – это и есть результат конверсии. Проделав это с дробью 0,(142857) в 11-ичной СС, получим 0,(163). Памятуя о том, что 0,(142857)= 1/7, разделим 1 на 7 в 11-ичной СС, понимая на каждом шаге деления под 10 ->11, 40 ->44, 20 ->22 и так далее. В итоге получим то же самое. Следовательно, разработанная процедура конверсии (нет не десятичных. а необыкновенных) дробей работает.
Но взявшись ковертировать то же самое число 0,(142857) в 41-ичную СС, мы вдруг сталкиваемся с эффектом невыхода на начало второго повторения периода. И при этом неожиданно понимаем, что конвертируем-то мы не саму периодическую дробь, а ее усеченное приближение – 1-ый период. И лишь только дополняя 1-ый период началом 2-го периода (или даже многократно повторяя период – это зависит от его длины), удается выйти на действительно периодический результат конверсии. Так, беря для 1/9 приближение 0,111111, мы получаем непериодическую последовательность 0,4 22 31 36 5 14 13 7 35… То же повторяется и в случае приближения 0,(111111111). Решить проблему удается лишь прямым делением 1 на 9 по вышеприведенному методу, когда под 10 подразумевалось 41, под 50 ->5*41= 205, под 70 ->7*41= 287 и так далее. В этом случае наконец-то получается последовательность 0,(4 22 31 36 18 9). Есть и другой способ ее получения, который, однако, впереди.
**
Все эти перипетии имеют и еще один и пожалуй более важный результат –они заставляют нас придти к пониманию, что числа 0,142857 и 0,(142857) – это не одно и то же. Что касается 1-го числа, то здесь все просто:
0,142857= 142857/10**6
Что же касается 2-го, то здесь интереснее:
0,(142857)=0,142857+ 0,000000 142857+ 0,000000 000000 142857+ …= 0,142857* (1+ 0,000001+ 0,000000 000001+ …)
Иначе говоря, получается бесконечная геометрическая прогрессия со знаменателем 10**(-6) и начальным членом 0,142857, сумма которой как известно равна:
0,(142857)= 0,142857* 1/(1- 10**(-6))= 0,1452857* 10**6/(10**6-1)= 142857/999999,
что и требовалось доказать.
Для чего требовалось? А помните приведенные выше разложения чисел из одних девяток? Так вот, если 999= 3**3*37= 27*37, то и 1/37= 3**3/999= 0,(027)(чуть не ошибся, чуть не написал 1/37= 0,(27)!) А если 99999= 3**2*41*271= 2439* 41, то разве не 1/41= 2439/99999= 0,(02439)? Вот и найден источник дурного нрава простых чисел – давать меньше период, чем максимально ожидается. И этот источник – основание применяемой СС, так как все числа, состоящие из одних девяток – это числа вида 10**N-1. И это уже отчасти было продемонстрировано выше. Так, в 41-ичной СС 1/9 – 6-членный период. Также в 41-ичной СС: 1/5= 0,(8), 1/7= 0,(5 35), 1/3= 0,(13 27).
Теперь обещанный 2-ой способ конверсии необыкновенной дроби 1/9= 0,(1) в 41-ичную СС. Он базируется на том, что при анализе 41-ичной системы на предмет разложения чисел из “девяток” обнаруживается, что 41**6-1= 9* 527789360, откуда следует, что 1/9= 527789360/(41**6-1). Остается теперь только преобразовать числитель этой дроби в 41-ичную СС. Что без промедления и дает 527789360 [10]= 4 22 31 36 18 9 [41]. Поэтому 1/9 [41]= 0,( 4 22 31 36 18 9)
* Целочисленное решение уравнений
**Деление
Как успел заметить читатель, предыдущие примеры изобиловали процедурами превращения обыкновенных дробей в необыкновенные (например, в так называемые десятичные). Например, 1/7= 0,(142857) или 1/9 [41]= 0,(4 22 31 36 18 9) Но призадумаемся, из каких шагов состоит уже это привычное превращение? Когда мы делаем первый шаг деления 1/7, мы на самом деле решаем уравнение: 10= 7*y+ x, причем решаем целочисленно. Именно это помогает (однозначно) решить это необычное уравнение с двумя неизвестными: x (=1)становится символом результата деления, а y (=3)– следующим делимым, которое дает следующий символ результата и причем таким образом: 30= 7*y+ x (так что 3 – лишь прообраз следующего делимого), откуда и получается y=4, x=2. Ну и так далее. Главное здесь – что при превращении обыкновенной дроби в необыкновенную мы впервые имеем дело не просто с целочисленным делением, а с целочисленным решением уравнений, в данном случае вида a*x=b. Когда получается 2 результата: собственно результат, который используется для продолжения процедуры (то есть является промежуточным результатом), и остаток, который становится составляющей окончательного результата.
**Корень квадратный
Разовьем эту мысль дальше. Не иначе как в учебнике алгебры 68 года (автор, кажется Барсуков) можно было встретить удивлявший уже тогда алгоритм вычисления квадратного корня столбиком. Ну деление – это еще понятно. А как корень-то столбиком, неужель возможно? По причине этих недоумений данный алгоритм, казалось, не имел успеха у публики. Но не для той ее части, для которой математика была частью жизни.
Забудем, повинуясь воле масс, упомянутый алгоритм, и вспомним, как бы между прочим, формулу возведения двучлена в квадрат: (a+b)**2= a**2+ 2*a*b+ b**2= a**2+ b*(2*a+ b). Но зная о том, что мы работаем в 10-ичной СС, видоизменим ее следующим образом: (10*a+b)**2=100*a**2+ 20*a*b+ b**2= 100*a**2+ b*(20*a+ b), откуда 10*a+ b= 10*sqrt(a**2+ b*(20*a+ b)/100)=> a+ b/10= sqrt(a**2+ b*(20*a+ b)/100)
Из последнего равенства следует, что если найдено a — некое целочисленное (а точнее- конечно-десятично-выраженное) решение уравнения x**2= N, где N приблизительно= a**2+ b*(20*a+ b)/100,то следующий компонент приближенного (десятичного) решения найдется из уравнения b*(20*a+ b)= 100, в результате его целочисленного решения. Это можно квалифицировать и как результат необычного целочисленного деления: b= 100/(20*a+ b).
**Корень кубический
Теперь, когда вычисление квадратного корня столбиком нам по плечу, почему бы не взяться за задачу следующего ранга – вычисление столбиком корня кубического? Народная молва не зря давненько обходит стороной всю эту кубистику, непроста ведь аналитическое решение кубических уравнений хоть и существует, но никто не хочет с ним связываться. Но мы — не лыком шиты, прорвемся.
А для начала пойдем уже проторенным путем, вспомним формулу куба двухчлена: (a+b)**3= a**3+ 3*a*2*b+ 3*a*b*2+ b**3= a**3+ b*(3*a**2+ 3*a*b+ b**2)= a*3+ b*(3*a(a+ b)+ b**2). Поскольку речь идет о вычислених в 10-ичой СС, заменим теперь a на 10*a, и получим (10*a+b)**3= 1000*a**3+ b*(30*a*(10*a+b)+ b**2), откуда 10*a+b=(1000*a**3+ b*(30*a*(10*a+b)+ b**2))**(1/3)=> a+ b/10= (a**3+ b*(30*a*(10*a+ b)+ b**2)/1000))**(1/3). Таким образом, как уже понятно, дело сводится к целочисленному, с остатком, решению необычного уравнения: b*(30*a*(10*a+ b)+ b**2)= 1000. То есть нужно выполнить следующее целочисленное деление b= 1000/(30*a*(10*a+ b)+ b**2). Какова практическая механика решения?
***
Пусть b=0, тогда в 1-ом приближении b= 1000/(300*a**2), по крайней мере не больше. Если полученное значение b не подходит, то есть получается отрицательный остаток, то значение b уменьшается на 1, и процедура повторяется снова, пока не будет найдено значение b, соответствующее минимальному, но положительному остатку.
Продемонстрируем это на конкретном примере. Пусть извлекается кубический корень из 2. Максимальное значение целочисленного куба, не превосходящего 2 – это 1. Итак, на 0-ом шагу a=1, поэтому b*(30*a*(10*a+ b)+ b**2)/1000= 2-1**3= 1. Отсюда получаем уравнение b*(30*(10+b)+ b**2)=1000. Подставляя b=0 в левый сомножитель, получаем bmax= [1000/300]=3. Проверим это значение, подставив в уравнение: 3*(30*(10+3)+3**2)= 1197> 1000. Следовательно, значение b следует уменьшить. Испытаем b=2: 2*(30*(10+2)+2**2)=728< 1000. Следовательно, b=2 – это и есть следующая цифра результата, уже после запятой. Поэтому теперь a=1*10+2, а следующее уравнение b*(30*a*(10*a+ b)+ b**2)/1000= 1000-728= 272. Отсюда b= 272000/(30*12*(120+b)+b**2), а bmax= [272000/300/144]= 6.
(Оговорка: если корень извлекался, например, из 2,173, то данное уравнение следовало бы изменить на 272173/(30*12*(120+b)+b**2). И так же на других шагах: последний остаток умножать на 1000 и прибавлять следующую тройку цифр из подкоренного числа.)
Очевидно, что значение b=6 велико, поэтому сразу проверяем b=5: 5*(360*125+5**2)=225125 < 272000. Итак, следующая цифра результата – это b=5, поэтому a=12*10+5, а следующее уравнение b*(30*125*(1250+b)+b**2)/1000= 272000- 225125= 46875, в итоге bmax= [46875000/300/125**2]= 10 и следующая цифра результата b=9. Общий итог: 2**(1/3)= 1,259…, что может быть проверено на калькуляторе. Но в нашем случае итерации могут быть продолжены и дальше на сколько угодно шагов, то есть данное кубическое уравнение может быть решено со сколь угодно большой точностью. Единственная проблема – далее потребуется работа со все многозначными числами. Но цифры подкоренного числа когда-нибудь исчерпают себя, после чего его значность будет естественным образом уменьшаться в результате деления. **Логарифм ***Рекуррентное уравнение Теперь нам предстоит самая трудная, но и самая увлекательная часть нашего путешествия. Что там корни квадратные столбиком! Что там корни кубические! Нам предстоит сейчас решить (столбиком) показательное уравнение, то есть взять целочисленный логарифм! Итак, пусть требуется найти необыкновенное приближение (=в виде необыкновенной дроби. Такие дроби в десятичной СС называются десятичными. Но было бы несправедливо называть их так в других СС) для решения уравнения: a**x=N, где N и a – целые числа и причем N>0 b a>0 (то есть N и a – натуральные числа)
Пусть tk – k-ое приближение x, тогда
N приблизительно= a**tk= a**(t[k-1]+bk/10**k)= a**t[k-1]* a**(bk/10**k)
Отсюда
N/a**t[k-1]= a**(bk/10**k)=> (N/a**t[k-1])**(10**k)= a**b[k]
Это и есть то самое рекуррентное уравнение, целочисленное решение которого позволит нам шаг за шагом находить цифры приближения решения исходного уравнения.
Пусть теперь N=6, a=2 (то есть нужно вычислить логарифм 6 по основанию 2), тогда очевидно, что t0=2 (нулевое приближение) и поэтому далее решаем (относительно b1) уравнение:
(6/2**2)**10= 2**b1 => (3**10)*(2**10)/2**20= 2**b1 => 3**10= (2**b1)*(2**10) => 3**10= 2**(b1+10) => 59049= 2**(10+b1)
Логарифмируя это уравнение, получаем b1=5, отсюда 2**(10+b1)= 2**15= 32768, поэтому a= 2+ 5/10= 25/10= 5/2 и получаем новое уравнение:
(6/2**(5/2))**(10**2)= 2**b1.
В итоге получаем уравнение:
3**100= 2**(150+ b2) => (3/2)**100/ 2**(50+ b1)= 1
В данном случае мы сталкиваемся впервые с уравнением, которое не может быть решено привычным путем. Ибо левая его часть оценивается как 5,15*10**47, а правая (даже при b2=0) как 3,65*10**47. Что же делать? Как целочисленно получить b2?
Мы будем делать такой процесс: 3 делить на 2, а затем результат умножать на 3 и опять делить на 2, и так 100 раз, а затем то, что получится делить на 2 столько раз, пока не получится число, меньшее 2, но большее 1 (и при этом считать каждое такое деление) Ибо на сколько больше их (делений на 2) получится против положенных (по уравнению) 50, это и получим для значения b2. А получим b2=8, то есть поделится на 2 не 50, а 58 раз.
После этого t2= 2,58= 258/100= 129/50 и следующее уравнение:
(6/ 2**(129/50))**(10*3)= 2** b3 => (3/2)**1000= 2**(580+ b3)
***Свертка и развертка
Что мы теперь можем предпринять для уменьшения разрядности? Идея уже опробована, остается применять. Перенесем все степени 2 в левую часть:
(3/2/2)**580 * (3/2)**420 /2**b3= 1
то есть сколько раз поделится на 2 без получения <1, таково и будет значение b3. А получается… А почему нам бы не продолжить процесс свертки выражения? Тогда получим: (3/2/2*3/2)**420 * (3/2/2)**160 /2**b3= 1 Но и это еще не предел: (3/2/2*3/2*3/2/2)**160 * (3/2/2*3/2)**260= 2**b3 Оценим 1-ый сомножитель и 2-ой: (3**3/ 2**5)**160= 1,56*10**(-12) (3**2/ 2**3)**260= 1,99*10**13 В итоге левая часть равна 31, это где-то не больше 2**4. Отсюда и b4=4. Итоговый результат: log(6)[2]= 2,584… На калькуляторе получается 2,584962501. Однако в нашем случае, как я уже отмечал, процесс вычисления может быть продолжен и дальше, последней цифры калькулятора. И даже дальше последней цифры численного вычисления общепринятых алгоритмов калькуляторов (и компьютеров). ***Неожиданные числа Фибоначчи Но речь сейчас созрела не о том. А о ряде Фибоначчи, который нечаянно (хоть и зримо) получается при моих расчетах. Это особенно видно, если процесс сворачивания уравнения продолжить: (3/2/2*3/2*3/2/2*3/2/2*3/2)**160 * (3/2/2*3/2*3/2/2)**100= 2**b3 То есть получится уже уравнение вида: (3**5/ 2**8)**160 * (3**3/2**5)**100= 2**b3 Если дальше продолжить процесс сворачивания, то ряд Фибоначчи обнаружится уже со всей ясностью: (3**8/ 2**13)**100 * (3**5/ 2**8)**60= 2**b3 Но и это еще не предел: (3**13/ 2**21)**60 * (3**8/ 2**13)**40= 2**b3 =>
(3**21/ 2**34)
***Естественная последовательность
Этот процесс можно продолжать и дальше. И даже интересно, чем он закончится. (не говоря уже о том, что ряд Фибоначчи точно имеет место) Но на горизонте возникают следующие вопросы: как распределить наиболее оптимально умножения и деления, чтобы (текущая) значность результата была минимальной? (желательно равной 1)
Например, нужно (оптимально, то есть нос не ниже травы, но не ниже воды)) вычислить (3**5/ 2**8)**160, как это сделать?
Остается воспользоваться все той же идеей: (3/2)**(5*160) /2**(3*160), и так далее. Отбросив сомножитель в степени 160, получим: оптимально умножать-делить в следующей последовательности: (3/2)**5 /2**3 => (3/2/2)**3 * (3/2)**2 => (3/2/2*3/2)**2 *(3/2/2)**1 => (3/2/2*3/2*3/2/2)*(3/2/2*3/2).
Таким образом, мы пришли к тому, что можно было бы назвать естественной последовательностью вычисления (3**5/ 2**8). Процедуру получения этой последовательности логично назвать разверткой.
(внимательный читатель, очевидно, заметил, что именно такая последовательность у нас получалась и раньше. Но мы перешли на степенное её отображение. Поэтому и потребовалась операция развертки)
Эту последовательность можно было бы получить и методом проб, на каждом шагу определяя, что выгоднее (с точки зрения поддержания результата на уровне 1) – умножать на 3 или делить на 2, параллельно ведя счет этим операциям.
***Окончание свертки
После этого результата возникает идея: а что если прерванный в предыдущем параграфе процесс все-таки продолжить? Мы остановились там на
(3**13/ 2**21)**60 * (3**8/ 2**13)**40= 2**b3
Далее в левой части получим:
(3**21/ 2**34)**40 *(3**13/ 2**21)**20 =>
(3**34/ 2**55)**20 *(3**21/ 2**34)**20 =>
(3**55/ 2**89)**20
На этом процесс свертки заканчивается, как закончился он и в предыдущем параграфе. В итоге получается уравнение
(3**55/ 2**89)**20= 2**b3
Естественно, что никакого возведения в 20-ую степень на самом деле здесь не будет, просто последовательность делений и умножений повторяется 20 раз. С той лишь оговоркой, что остается только свернуть, как мы делали это выше, выражение 3**55/ 2**89 (превратить его в естественную последовательность), и тогда решение уравнения будет полностью оптимизировано.
Впрочем, поскольку b3 по определению <10, можно ввести и еще одно усовершенствование: (3**55/ 2**90)**b3 *(3**55/ 2**90)**(20-b3)=1 Однако здесь возникает вопрос: а как вычислить левую часть, ведь b3 неизвестно? Этот вопрос заставляет нас вернуться к методу проб, на который указано выше: сколько раз, в процессе вычисления (3**55/ 2**89)**20, нам придется вставить дополнительных делений на 2 (исходя из принципа поддержания 1) – этому количеству и равно b3. **Аппендикс для квадратного корня В завершение выведем рекуррентные уравнения для вычисления разобранных выше квадратного и кубического корней. Пусть решается уравнение x**2= N. Пусть tk – k-ое приближение x, тогда N приблизительно= tk**2= (t[k-1]+ bk/10**k)**2. Отсюда получаем уравнение: N= t[k-1]**2+ 2*t[k-1]*bk/10**k+ (bk/10**k)**2=>
N= t[k-1]**2+ bk/10**k* (2*t[k-1]+ bk/10**k)=>
(N- t[k-1]**2)*10**(2*k)= bk* (2*t[k-1]*10**k+ bk)=>
N*10**(2*k)- (t[k-1]*10**k)**2= bk* (2*t[k-1]*10**k+ bk)
Это и есть то самое рекуррентное уравнение, которое (на словах) мы решали, описывая выше алгоритм извлечения квадратного корня. Как нетрудно догадаться, в последнем уравнении t[k-1]*10**k интерпретируется как последовательность цифр, отображающая последнее найденное приближение корня, а N*10**(2*k)- первые 2k цифр подкоренного числа (дополненного, при необходимости нулями)
Вывод же рекуррентного уравнения для вычисления корня кубического мы оставляем заинтересованному читателю.