ПОЛИНОМЫ И СИСТЕМЫ СЧИСЛЕНИЯ

МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ  

УЧРЕЖДЕНИЕ ГИМНАЗИЯ №14 ИМ. С.С.КЛИПОВОЙ

ПОЛИНОМЫ

И

СИСТЕМЫ СЧИСЛЕНИЯ

Подготовил

                                                                                                                                                     Борисов  Владислав          Романович,                                                                         

10а класс

ПРОВЕРИЛА

Воронецкая Марина Михайловна,  учитель информатики и математики 

г.ВЫКСА,2021

Содержание

Часть 1 «Из одной системы счисления в другую»                                                        3

     Гипотеза №1                                                                                                                          5

     Гипотеза №2                                                                                                                          9

Часть 2. «Элементарные операции в системе счисления»                                   10

Часть 3. «Более сложные операции и разбор гипотез»                                          14

     Доказательство Гипотезы №1                                                                                      16      Доказательство Гипотезы №2                                                                                      19

Полином - это сумма членов (слагаемых), у которых задана общая закономерность, с помощью которой их можно пронумеровать

Обычно закономерность такова, что каждый член полинома отличается от другого степенью множителя x и множителем a (коэффициентом), cответствующим степени x (но у разных членов может быть одинаковый коэффициент)

P(x)=anxn+an-1xn-1+an-2xn-2+…+a1x1+a0x0

Если мы заменим переменную x на постоянную q, а число а_n на b_n, то мы получим полиномиальную запись числа в системе счисления с основанием q.

bn…b2b1b0 q= bnqn+bn-1qn-1+bn-2qn-2+…+b2q2 + b1q1+b0q0

Все коэффициенты меньше основания системы счисления, которое больше единицы. Коэффициенты, основание и n- это целые числа

q – основание системы счисления, b – коэффициент,n – порядок коэффициента  ОБЯЗАТЕЛЬНЫЕ условия для системы счисления, отличающие её от обычного полинома   где n,0b_n<q, q>1   b_n,q,n

Если q больше 10, то, для того чтобы b_n могло всё так же играть роль цифры в левой части,  начинают использовать буквы английского алфавита 10=A,11=B,12=C,13=D,14=E,15=F… и так далее

Часть 1. «Из одной системы счисления в другую»

Есть два способа перевести число из одной системы счисления в другую.

A) Полный                                                                B) По частям

(n → 10 → k)                                                          (qⁿ  → q^k )

Cначала приводим к основанию 10,            работает только в том случае, если а потом в систему  счисления с                       основание, из которого переводим, нужным нам основанием                                 и  основание, в которое переводим,- это

                                                                                     степени одного и того же числа

Давайте проанализируем каждый

Число = Целая часть числа + Дробная часть числа

A) Полный

(Перевод для целой части)

Перевести в десятичную систему счисления очень просто. Достаточно разложить это число в полином и просто посчитать.

N - Это натуральное число

Но как переводить из десятичной системы в другую систему счисления? Вы, скорее всего, уже знаете этот алгоритм, но мне хотелось бы показать вам откуда он берётся (мне кажется, что этому уделяют слишком мало внимания).      b_nqⁿ+b_n-1q^n-1+ …+b₂q² + b₁q+b₀ = N

Перед нами стоит задача - найти значения всех коэффициентов. Давайте найдём сначала наименьший коэффициент.

(bnqn-1+bn-1qn-2 +…+b2q + b1)q+b0 = N

Дано: N = 234, q=8 Вычислено: b0=2,   bnqn-1+bn-1qn-2 +…+b2q + b1 = 29

Так как ни один  из коэффициентов не делится на q, то и b₀ не  будет делиться на q Мы можем найти b₀ как остаток от деления N на q нацело. Что мы и делаем в одном очень известном алгоритме. Пример:

  234|  8

  232|29

       2(ост.)

Как мы видим, у нас получился немного другой полином, но коэффициенты остались теми же. 

Теперь мы можем, используя тот же алгоритм, найти коэффициент b₁. 

Несложно понять, что с каждым повторением этого алгоритма мы будем получать полином  с уменьшенным количеством членов и  с пониженной высшей степенью q.

Это говорит о том, что повторяя этот алгоритм конечное количество раз, мы можем найти все коэффициенты исходного полинома, включая нужные нам для записи числа ненулевые. Именно отсюда и берутся известные вам с уроков информатики ступеньки (рис. 1).

 

(Перевод для дробной части)

Если в предыдущем алгоритме мы делили на q (понижали степень), то в этом алгоритме мы будем её повышать

Дробная часть  числа с основанием q

  b-1q-1+b-2q-2+ …+bnqn + bn-1qn-1+… = N 

Теперь давайте умножим на q , чтобы появился коэффициент b_-1

     b-1q-1 +b-2q-2+ …+bnqn + bn-1qn-1+… = N   |×q      b-1 +b-2q-1+ …+bnqn+1 + bn-1qn+… = N ×q

 b_-1 –это целая часть N×q   b_-2q^-1+ …+b_nqⁿ⁺¹ + b_n-1qⁿ+…  - это дробная часть N×q

Пример:

Дано: N=0,345;q=8 Вычислено: b-1=2 ,b-2q-1+ …+bnqn+1 + bn-1qn+… = 0,760

     0,345

 ×                 8

     2,760

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

Примечание:

                           Одна и та же дробь может оказаться конечной в одной системе счисления и бесконечной периодичной¹ в другой системе счисления. 

Пример:   1/3=0,(3)₁₀ ,1/3=0,4₁₂  

    

¹Гипотеза №1

Иррациональное число непериодично в любой системе счисления Рациональное число периодично в любой системе счисления

B) По частям

 (Перевод для целой части)

А) q→qⁿ

-Применима ли к полиному замена?

-Конечно же!

Давайте, для начала, разберём одно очень важное неравенство для замены одного основания на другое в  полиномиальной записи системы счисления.

bnqn+bn-1qn-1+ …+b2 q2 + b1q1+b0q0 < qn+1

              Доказательство

Давайте возьмем максимально возможное значение левой части

Для этого пусть все коэффициенты примут своё максимально возможное значение, а именно q-1.

Тогда мы получим другое неравенство 

(q-1)qⁿ+(q-1)q^n-1+ …+(q-1)q² + (q-1)q¹+(q-1)q⁰ < qⁿ⁺¹

                              Вынесем общий множитель

(q-1)(qn+qn-1+qn-2+….+q1+q0)<qn+1

(Те, кто изучал геометрическую прогрессию, уже знают, что мы получили слева. Ну а       для тех, кто не изучал геометрическую прогрессию, мы сейчас убьём двух зайцев ) Давайте сначала умножим все члены на q, а потом на -1 и получим разность двух

рядов

                               _  qn+1 + qn+qn-1+qn-2+….+q1                                                     Итого: qn+1 –q0 < qn+1    или qn+1 –1 < qn+1       

                qn+qn-1+qn-2+….+q1+q0                                                                                                                           Что верно

                                                                          qⁿ⁺¹ –q⁰                                           < qⁿ⁺¹                                                                                ч.т.д.

Кстати, мы только что доказали, что (qⁿ⁺¹ –1)/(q-1)= qⁿ+q^n-1+q^n-2+….+q¹+1

Вот вам и формула суммы первых членов геометрической прогрессии =)

Теперь давайте сделаем замену и поймем, зачем нам нужно это неравенство.

Для перевода из системы счисления с основанием q в систему счисления с основанием q^m  нам понадобиться замена

q^m=t,  b_m-1+mnq^m-1+ …+b_2+mnq² + b_1+mnq¹+b_mn=a_n |=> a_n<t (по одному доказанному неравенству)   

Приготовьтесь, сейчас будут очень большие вычеты

(m, k, n , c –целые положительные числа, с<m)

bkm+cqkm+c +…+bkm+1qkm+1 +bkmqkm+bkm-1qkm-1+…+b5m+1q5m+1 +b5mq5m+b5m-1q5m-1+    …    +b4m+1q4m+1 +b4mq4m+b4m-1q4m-1+…+b3m+1q3m+1 +b3mq3m+b3m-1q3m-1+    …    +b2m+1q2m+1

+b2mq2m+b2m-1q2m-1+    …    +bm-1qm-1 + bmqm+bm-1qm-1+bm-2qm-2+     …    +b2q2 + b1q1+b0q0

(bkm+cqc +…+bkm+1q1 +bkm)qkm+…+( …+b5m+1q1 +b5m)q5m+

(b5m-1qm-1+…+b4m+1q1 +b4m)q4m+  (b4m-1qm-1+…+b3m+1q1 +b3m)q3m+ (b3m-1qm-1+…+b2m+1q1 +b2m)q2m+  (b2m-1qm-1+…+bm+1q1 + bm) qm+ bm-1qm-1+…+b2q2 + b1q1+b0q0

(bc+kmqc +…+b1+kmq1 +bkm)qmk +…+(…+b1+5mq1 +b5m)qm5+

(bm-1+4mqm-1+…+b1+4mq1 +b4m)qm4 +  (bm-1+3mqm-1+…+b1+3mq1 +b3m)qm3+ (bm-1+2mqm-1+…+b1+2mq1 +b2m)qm2+  (bm-1+mqm-1+…+b1+mq1 + bm) qm+ bm-1qm-1+…+b2q2 + b1q1+b0q0

aktk+…+a5t5 + a4t4 + a3t3 + a2t2 + a1t+a0=a5a4a3a2a1a0 t или a5a4a3a2a1a0 qm где a_n<t, что является необходимым условием для любой системы счисления

А теперь мы выведем общий алгоритм перевода из q c/c в q^m  с/с. ( q с/с   -  система счисления с основанием q )

1)    Разбиваем наше число (в q c/c) на ячейки в левую сторону по m символов, (коэффициентов b_n) начиная с  b₀ ;

2)    Переводим эти ячейки, как полноценные числа из q c/c в q^m  с/с.

(на каждую ячейку будет приходиться по одному коэффициенту a_n);

3)    Объединяем все коэффициенты a_n по порядку, чтобы получить наше число в q^m  с/с.

Несложно догадаться, что этот алгоритм может работать и в обратную сторону                                     

N=…b7m|b7m-1…b6m|b6m-1…b5m|b5m-1…b4m|b4m-1…b3m|b3m-1…b2m|b2m-1…bm|bm-1…b0I q

              |               |                 |                 |                  |                 |                 |           I          a₇  |    a₆               |   a₅            |   a₄            |   a₃              |   a₂             |    a₁          |   a₀            I

N=…a7a6a5a4a3a2a1a0 qm

Если количество коэффициентов не кратно m, то вы можете добавить недостающее количество коэффициентов, НО! добавленные коэффициенты обязаны равняться нулю, иначе значение переводимого числа изменится.

Пример:                 789|       |000789| 

Б) (qⁿ  → q^k )

У есть перевода по частям есть, одно очень большое преимущество и недостаток. + Мы можем, разбив число на небольшие  кусочки, перевести число сразу в нужную нам систему.

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

То есть,  c основания 7 на основание 8 таким образом перевести не получится  Из уроков алгебры вы уже наверняка знаете, что показательная функция растёт ОЧЕНЬ быстро   ну а если вы не знакомы, то приведу вам очень яркий пример:

7⁰=1,  7¹=7,  7²=49,  7³=343 , 7⁴=2401,  7⁵=16807 и т.д. ,для числа больше семи рост будет идти ещё быстрее

Поэтому этот метод перевода в основном применяется в основном для степеней двойки и иногда тройки (3 →9, 9→3)

Ну а теперь к самой сути. Давайте возьмём предыдущий алгоритм сразу для двух переводов и уберём лишнюю строчку.

N=  ...b6mIb6m-1   ...b5mIb5m-1    ...b4mIb4m-1    ...b3mIb3m-1   ...b2mIb2m-1    ...bmIbm-1...b0Iqⁿ   

                                                                                                                             

N=...c6nmIc6nm-1...c5nmIc5nm-1...c4nmIc4nm-1...c3nmIc3nm-1...c2nmIc2nm-1...cnmIcnm-1...c0Iq

                                                                                                                                         

N=  ...a6nIa6n-1       ...a5nIa5n-1      ...a4nIa4n-1       ...a3nIa3n-1        ...a2nIa2n-1       ...anIan-1   ...a0Iq^m

Как мы видим, на каждые m коэффициентов в верхней  строчке приходится n коэффициентов в нижней строчке. Итого, мы можем просто взять и убрать среднюю строчку и переводить сразу из qⁿ в q^m.

N=  ...b6mIb6m-1   ...b5mIb5m-1    ...b4mIb4m-1    ...b3mIb3m-1   ...b2mIb2m-1    ...bmIbm-1...b0Iqⁿ

                                                                                                                              

N=  ...a6nIa6n-1       ...a5nIa5n-1      ...a4nIa4n-1         ...a3nIa3n-1      ...a2nIa2n-1     ...anIan-1   ...a0Iq^m

(Перевод для дробной части)

У перевода по частям есть ещё одно очень прекрасное свойство.

Переводы дробной и целой части практически не отличаются.

Просто при переводе дробной части ячейки разбиваются не в левую сторону, а в правую, и первая ячейка начинается не с b₀, а с b_-1

И недостающие коэффициенты добавляются в обратную сторону

Пример: |234      |23400000|

Примеры использования перевода по частям

                                                                                                                                                           2

        нам нужно перевести в 4 _{или 2} , поэтому в           ячейках будет по 2 цифры (коэффициента)

5613041707,2228 или 23  

        На 2 цифры в системе счисления с          основанием ₂3 будет приходится 3 цифры в

                                                                                        системе счисления с основанием  ₂2  

|568     |138     |048    |178    |078     |,|228     |208      |

                                                                                                                                                     

|232₄|023₄|010₄|101₄|013₄|,|102₄|100₄|

Промежуточные вычисления

56₈ = 232₄        13₈  = 023₄       04₈  =  010₄       17₈ =  101₄

07₈ =  013₄       22₈ =  102₄        20₈ =  100₄

Теперь давайте уберём эти ячейки и получим запись нашего числа в системе счисления с основанием 4.

5613041707,222₈=232023010101013,102100₄ или 

                            232023010101013,1021₄

Как мы видим, число цифр увеличилось практически в полтора раза, потому что мы переводили из системы счисления с основанием ₂³ в систему с основанием ₂² , а

3/2=1,5

Давайте обозначим одну зависимость функцией

G_q(N)= Количество цифр в  записи числа N(натуральное число) в системе счисления с основанием q.

|G_q^m(N)/ G_qⁿ(N) - n/m| ( Если N стремиться к бесконечности)

Если мы это запишем немного по-другому, то я смогу сформулировать ещё одну гипотезу¹

|G_q^m(N)/ G_qⁿ(N) - log_q^m(qⁿ)| ( Если N стремиться к бесконечности)

¹Гипотеза №2

|G_n (N)/ G_m (N) – log_nm| ( Если N стремиться к бесконечности)

для любого n и m (натуральные числа),n0, m0. На языке математического анализа

 

Часть 2. «Элементарные операции в системе счисления»

                   Всего есть четыре элементарных операции над числами. Вы их уже знаете, но всё равно стоит их обозначить.

Все числа, над которыми производятся операции, обязаны быть в одной системе счисления

1.Сложение

2.Вычитание (обратное сложение)

3.Умножение (многократное сложение)

4.Деление (обратное умножение)  Давайте начнём с первой операции.

Сложение.

-Можем ли мы просто взять и сложить два полинома? -Да, можем.

    bnqn+bn-1qn-1+bn-2qn-2+…+b2q2 + b1q1+b0q0

                                +anqn+an-1qn-1+an-2qn-2+…+a2q2 + a1q1+a0q0    cn=an+bn

   c_nqⁿ+c_n-1q^n-1+c_n-2q^n-2+…+c₂q² + c₁q¹+c₀q⁰  - полиномиальная запись суммы Да, всё выглядит очень просто, но есть небольшой нюанс. Мы же помним, что все коэффициенты должны быть меньше основания. Но что делать если одна или несколько c(коэффициентов) оказались по значению больше основания?

…+cnqn+cn-1qn-1+…

Если коэффициент c_n-1q, то мы можем его разложить на слагаемые

A:=B   (A присваивает значение B)

                  …+c_nqⁿ+(a×q+c`<sub>n-1)</sub>q<sup>n-1</sup>+…                   …+(c<sub>n</sub>+a)q<sup>n</sup>+ c`_n-1q^n-1+…

                          c_n-1:= c`_n-1     , c_n:= c_n+a

                  …+c_nqⁿ+ c_n-1q^n-1+…

Если теперь c_nq, то мы можем сделать с ним  то же самое, что и с c_n-1 И так до тех пор пока все коэффициенты не станут меньше q.

Одним словом                                                              

 Мы можем уменьшить  значение коэффициента на          a*q, увеличив значение следующего коэффициента на            a. Значение всего числа

при этом не поменяется.

Примеры  такого сложения:

  70620218                                                                          5016

             ⁺15578                                                                                   ⁺5236

Обратите внимание на то, что в ходе понижения значения коэффициентов их количество может увеличиться

706357(8)|промежуточные               (10)24

70635(8)0|строчки                                  1424₆

 7063600₈                  

Вычитание.

cn= bn -an

    _bnqn+bn-1qn-1+bn-2qn-2+…+b2q2 + b1q1+b0q0       anqn+an-1qn-1+an-2qn-2+…+a2q2 + a1q1+a0q0        c_nqⁿ+c_n-1q^n-1+c_n-2q^n-2+…+c₂q² + c₁q¹+c₀q⁰ - полиномиальная запись разности Если с (коэффициент) меньше нуля, то мы можем увеличить его значение ,уменьшив значение более старшего коэффициента. 

Если же  самый старший ненулевой коэффициент отрицателен, то и разность отрицательна

… + cn+1qn+1+cnqn+ …

Пусть c_n+1 >0, a c_n  0 тогда 

… + c_n+1qⁿ⁺¹-|c_n|×qⁿ+ …

… + (c_n+1-1)×qⁿ⁺¹ +q×qⁿ -|c_n|)×qⁿ+ …

… + (c_n+1-1)×qⁿ⁺¹ +(q-|c_n|)×qⁿ+ … c_n+1 := c_n+1-1 ; c_n:= q-|c_n|

… + cn+1qn+1+cnqn+ …

Теперь значение c_n увеличилось, а c_n+1 уменьшилось.

Если же и c_n+1 изначально был меньше или равен, то мы могли бы увеличить его,

уменьшив значение c_n+2

И т.д.

Одним словом  Мы можем увеличить значение коэффициента на q, уменьшив значение следующего коэффициента на 1. Значение всего числа при                                                                               этом не поменяется.

Есть два способа вычитания:

Мой - новомодный                                                (увеличиваем коэффициенты разности)            _6734560228                                                                          2206543768                                                                                453(-2)02 (-3)(-5)(-4)| промежуточные   4526015(-5)(-4)          |  строчки           4526014248

Классический         ( увеличиваем коэффициенты вычитателя          -    делаем  известное вам занимание у следующего коэффициента для того, чтобы можно было сразу  вычесть одно число из другого )                          673456022   8                                                                                     220654376   8                                                                                     Давайте увеличим некоторые коэффициенты                                                 672(12)5579(10)  8                                                                                220      6 5437    68           452    6 0142    48 Или просто  4526014248

Умножение.

Я не буду перемножать полиномы прямо в статье, так как это займёт очень много места. Но вы можете сами составить два небольших полинома, перемножить их друг на друга и увидеть обозначенную ниже закономерность

-Можем ли мы перемножать полиномы? -Вы не поверите.

    (bnqn+bn-1qn-1+bn-2qn-2+…+b2q2 + b1q1+b0q0)

× (anqn+an-1qn-1+an-2qn-2+…+a2q2 + a1q1+a0q0)                 c2nq2n+c2n-1q2n-1+…+c2q2 + c1q1+c0q0

Одним словом, мы должны перемножить два многочлена.

Т.е мы должны перемножить все члены первого многочлена на все члены второго многочлена, а потом получившиеся произведения сложить.

(думаю, что вы и без меня это отлично помните)

 Так вот, после перемножения у нас получится куча членов, у которых будет одна общая закономерность (ниже она объясняется очень  небольшим вычислением ). akqk  × bnqn=akbnqk+n

Отсюда берётся другая закономерность

cn= …+an+2b-2+an+1b-1+anb0+an-1b1+an-2b2+…

Используя именно эту закономерность, мы будем находить коэффициенты произведения. Пример (без конкретных цифр):

Если некоторые из с (коэффициентов) окажутся больше q ,то мы сможем уменьшить их так же ,как мы это делаем в случае сложения

                                                                      _×a₃a₂a₁a₀a_-1                                                                         b₂b₁b₀

                            (a₃b₀)(a₂b₀)(a₁b₀)(a₀b₀)(a_-1b₀)

              ⁺(a₃b₁)(a₂b₁)(a₁b₁)(a₀b₁)(a_-1b₁)

  ⁺(a₃b₂)(a₂b₂)(a₁b₂)(a₀b₂)(a_-1b₂)                       . 

          c₅       c₄        c₃       c₂         c₁        c₀            c_-1

Пример (с конкретными числами):

5763₈

3124₈

                                                   (20)(28)(24)(12)

                                           (10)(14)(12)(06)

                                   (05)(07)(06)(03)

                          (15)(21)(18)(09)                       .

Вау!!! Это по-настоящему впечатляет

                          (15)(26)(35)(49)(43)(30)(12)

                          (15)(26)(35)(49)(46)74

                                                             22716674₈                    

Деление.

-А можем ли мы….

-НЕТ =(

А вот тут и проявляется самая главная проблема деления. Раньше мы просто меняли основание заменой, складывали полиномы, вычитали и умножали. Если же мы попробуем поделить полином на полином, то получим какую-то невнятную кашу, которая никак не поможет нам в создании алгоритма. Но мы можем вспомнить чему нас учили в школе:  деление- это обратное умножение.

Так как деление- это обратное умножение, то перед нами стоит задача найти все коэффициенты, если  ненулевых из них конечное множество или определённого количество, если ненулевых коэффициентов бесконечное множество

 (bnqn+bn-1qn-1+bn-2qn-2+…) 

× (akqk+ak-1qk-1+ak-2qk-2+…)       c_k+mq^k+m+c_k+m-1q^k+m-1+…- полиномиальная запись частного  

Алгоритм деления (a_na_n-1a_n-2…)/(b_kb_k-1b_k-2…) где  a_n0, b_n0, n>k

1) Ищем максимальное возможное значение члена с_m1 q^m1, при котором

((anan-1an-2…)-(bkbk-1bk-2…)× сm1 qm1)>0

*Наибольшим по порядку членом частного будет  с_m1 q^m1 2) Теперь находим разность №1

((anan-1an-2…)-(bkbk-1bk-2…)× сm1 qm1) – разность №1

3)Теперь ищем максимальное возможное значение члена с_m2 q^m2, при котором

         ((разность №1)-(b_kb_k-1b_k-2…)× с_m2 q^m2)>0

*Cледующим по порядку членом частного будет  с_m2 q^m2

4)Теперь находим разность №2

           ((разность №1)-(b_kb_k-1b_k-2…)× с_m1 q^m1) – разность №2

                    И так далее до того момента пока разность не будет равна нулю и

или вы не получите достаточное количество членов полинома частного,                          который будет выглядеть так:

Числа после m это не степени. Они нужны для того, чтобы отличить одну m от другой m

Процесс деления был прерван, но мы уже можем сказать, что  целая часть (76038/638)  равна 1178

cm1qm1+cm2qm2+cm3qm3+cm4qm4+cm5qm5+cm6qm6+… Пример такого деления:

7603₈|63₈

                                                                              6300  |117,…₈

                                                                              1103

                                                                                 630

                                                                                 473

                                                                                 445

                                                                                    26

                                                                                     …

Часть 3. «Более сложные операции и разбор гипотез»

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

Итак, преступим.

Название этой части немного обманчиво ведь в ней будет разбор только одной операции, но достаточно трудноватой. Почему я решил её вам показать? Потому что она является операцией выполняющейся в столбик.

Вынесение квадратного корня.

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

*Давайте начнём с того, что работает в абсолютно любой системе счисления:

(100…0_q)²=100…0_q

                                                                        n нулей         2n нулей

Следовательно, зная количество цифр у х², мы можем оценить количество цифр у х. На каждые 2 цифры х²  будет приходится по одной цифре х . 

          *  Теперь давайте, как и в случае с делением, найдем максимально возможно значение старшего коэффициента. Но почему мы всё время берём максимально возможное значение ? Всё очень просто!

               anan-1…a2a1a0q <bnbn-1…b2b1b0q если an  < bn

                                                                     или если a_n  = b_n , но  a_n-1  < b_n-1                                                                      или если a_n  = b_n , a_n-1  = b_n-1  , но  a_n-2  < b_n-2                                                                      и так  далее 

            *Теперь давайте вспомним Бином Ньютона для степени 2

(a1 q+a0 q)2 =( a1 q )2 +2(a1 q)( a0 q ) +( a0 q)2  N 

=(anan-1an-2an-3an-4 q)² =(anan-1an-2an-3 q + an-4 q)² =

( anan-1an-2an-3 q)² +2(anan-1an-2an-3 q)( an-4 q ) +( an-4 q)²  N

То есть, зная чему равно  a_na_n-1a_n-2a_{n-3 q} и N, мы сможем найти максимальное значение   a_n-4(коэффициент меньший по порядку), при котором (a_na_n-1a_n-2a_n-3a_{n-4 q})² < N ( это возможно конечно же только в том случае если (a_na_n-1a_n-2a_{n-3 q})² < N ), решив такое неравенство и выбрав максимальное возможное значение

(2(anan-1an-2an-3 q)+an-4 q  )( an-4 q) < N- ( anan-1an-2an-3 q)²

Теперь можно приступить к самому алгоритм.

Я думаю, что после трёх тем поднятых выше вы поймёте как появился этот алгоритм.

Пример вынесения квадратного корня в столбик:

  

     (Вспоминаем первую звёздочку)

                                      (Вспоминаем вторую звёздочку)

    

 (Вспоминаем третью звёздочку, наш x₁ это и есть тот меньший по порядку коэффициент)

Проверка:

2416₇

                                                                ×2416₇

                                            (12)(24)(06)(36)

                                    (02)(04)(01)(06)

                            (08)(16)(04)(24)

                    (04)(08)(02)(12)                           .

                    (04)(16)(20)(32)(49)(12)(36)

                    (04)(16)(21)(32)    0  ( 17)    1

                    (04)(16)(25)    4      2      3      1                     (04)(19)    4     4      2      3      1

                        6      5    4      4      2      3      1

Для такого числа достаточно неплохая точность. Но хотите небольшой фокус. Помните на каком числе мы закончили вынесение числа в столбик? 1062?  Давайте прибавим его

Вау!!

                                      6544231₇ 

                                                                   +10627

                                      6545323₇

Гипотеза №1

Иррациональное число непериодично в любой системе счисления Рациональное число периодично в любой системе счисления

Доказательство Гипотезы №1

Как мы видим, гипотеза состоит из двух утверждений.

                      1)Число рационально => Число периодично¹ в любой системе счисления

 2)Число иррационально => Число непериодично в любой системе счисления Мы можем доказать утверждение №2, доказав утверждение №3

               3)Число периодично => Число рационально

Т.к. числа являются либо рациональными, либо иррациональными, то  если все периодичные числа рациональны, то все иррациональные числа обязаны быть не периодичными.

A иррационально и периодично A периодично => A рационально A иррационально и рационально  (чего быть не может )

                     Иначе получаем противоречие вида:

Теперь начнём доказывать наши утверждения.

1)Число рационально => Число периодично

           3)Число периодично => Число рационально Утверждения №3

Его можно доказать достаточно просто

Число с периодом = Непериодическая часть числа +   Периодическая часть числа

Непериодическая часть числа рациональна. Его можно просто посчитать и представить в виде отношения двух конкретных натуральных чисел (взаимно простых)    

Периодическая часть числа тоже рациональна. Это можно доказать с помощью формулу суммы бесконечно убывающей геометрической прогрессии.

   m0qⁿ+ m1q^n-1+ m2q^n-2+…+ mkq^n-k

+m0qn-k-1+ m1qn-k-2+ m2qn—k-3+…+ mkqn-k-(k+1)

+m0qn-2k-2+ m1qn-2k-3+ m2qn—2k-4+…+ mkqn-k-2(k+1)

…

Теперь давайте выносить общий множитель, чтобы получить  Бесконечно убывающую геометрическую прогрессию      m0qⁿ+ m1q^n-1+ m2q^n-2+…+ mkq^n-k  +(m0qn+ m1qn-1+ m2qn-2+…+ mkqn-k)×q-(k+1)

+(m0qn+ m1qn-1+ m2qn-2+…+ mkqn-k)× (q-(k+1))2

…

                                                                                                                                   ¹Имеет период = периодично

Теперь можно спокойно воспользоваться формулой бесконечно убывающей геометрической прогрессии

 

b1= m0qn+ m1qn-1+ m2qn-2+…+ mkqn-k q := q^-(k+1)     теперь |q|<1, что является  необходимым условием для использования  этой формулы

В общем, периодическую часть тоже можно представить в виде 

Отношения двух натуральных ( взаимно простых) чисел.  

Итого:

Число с периодом = Непериодическая часть числа +   

                                               Периодическая часть числа

Число с периодом можно представить в виде отношения двух взаимно простых натуральных чисел => Число с периодом рационально Ч. т. д.

N

2)Число иррационально => Число непериодично в любой системе счисления       (Доказано)

А теперь давайте остановимся, чтобы я вам показал кое- что интересное

= 11.00100100001111110110…

-Стоп! То есть бесконечную непериодическую последовательность цифр можно получить из 1 и  0?.

-Да. И не только из 1 и 0, но из любого количества цифр.

Давайте попробуем замену

Пусть 1=23 (здесь может быть не только 23) , а 0= 9( и здесь тоже не только 9). Будет ли наша новая последовательность периодичной ? 

- Конечно же нет.( я предлагаю вам самим это доказать)

Поэтому если кто-то будет говорить вам, что из иррациональности  следует, что в нём можно найти любую последовательность цифр, то у вас будет достаточно хороший контрпример.

Утверждения №1

На самом деле, это утверждение можно было бы доказать через утверждения

№2 и №3, но так как я не вижу возможности также просто прийти к противоречию, как в случае с утверждениями  №2 и №3, то это утверждение придётся доказывать через алгоритм деления, а именно когда он начинает зацикливаться. Давайте докажем, что при делении одного натурального

числа на другое зацикливание неизбежно при определённых условиях.

=? q

 *Зацикливание неизбежно если B не является множителем или  степенью q, и не является произведением того и другого.

*Если выше данное условие не соблюдается, то частное это  конечное (c 0 в периоде) число.

( Это понять довольно не сложно, вспомните десятичную систему счисления и значение  таких дробей, как  

Теперь нужно разобраться с первой звёздочкой и зацикливанием  Пример зацикливания:

5603₇|5₇

56037/57 =1113,(2541)7

5                                   |1113,25412 ₇   Итого

6                                            

   5

   10

      5

      23

      21

                     --->20|Именно в этой части мы обязательно наткнёмся на зацикливание

        13

Обратите внимание на эти большие жирные числа, к которым мы приписывали нолик. Они все меньше делителя (57), а так как чисел меньше делителя ограниченное количество, то рано или поздно одно из чисел попадётся нам во второй раз, после чего и начнётся зацикливание. Ч.Т.Д

Ага            !!

           40

             34

                30

                 26

                   10

                        5

   --->20

1)Число рационально => Число периодично

(Доказано)

Итого, два утверждения, из которых состояла гипотеза, были доказаны.

Значит и сама и сама гипотеза превратилась в теорему, так как была доказана. Давайте дадим ей название.

Теорема о периоде

Иррациональное число непериодично в любой системе счисления

Рациональное число периодично в любой системе счисления

¹Гипотеза №2

|G_n (N)/ G_m (N) – log_nm| ( Если N стремиться к бесконечности)

для любого n и m (натуральные числа),n0, m0. На языке математического анализа

 

                       Доказательство гипотезы №2

Я знаю, вас очень сильно пугают такие знаки, как:  ,G, lim, log и   

Но не бойтесь, ведь у вас есть я. И я не буду сейчас давать вам сейчас какие-то излишние аксиомы и «очевидности», которые так любят ленивые профессора.

Давайте начнём с моего нововведения, а именно функции G_q(N)

Это функция нужна для того, чтобы вычислить количество цифр числа, зная его значение в десятичной системе счисления и  основание системы счисления, в которой оно записано.

Можно ли выразит эту функцию через более простые и знакомые нам функции? Конечно!

- взятие целой части x -взятие дробной части x

 = 

Но почему? Сейчас покажу.

В системе счисления  с основанием q

Если    a>bc то q^a>q^bq^c                 q^a содержит a+1 знаков a,b – натуральные числа               q^c содержит с+1 знаков

Теперь давайте перезапишем ту страшную дробь в что-то более миловидное.

 

Давайте помножим числитель и знаменатель                                    на

  

 

 

Итого

 

*(Для продвинутых)

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

 

N

Гипотеза доказана

- При возрастании N модуль суммы этих слагаемых будет уменьшаться.

(для обычных десятиклассников)

-Нет. Я не хочу сказать, что если мы увеличим N буквально на 1, то модуль сразу же уменьшится. Я хочу сказать, что для любого достаточного маленького числа  больше нуля (обозначим его как έ) , будет существовать столько большое значение N, что при большем его значении модуль нашей суммы будет не больше чем  έ.

-Стоп! Ты только что попытался объяснить десятикласснику, что такое предел? -Да =)

Практическая сторона.

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

101………….101₂ =120…………….45 

                                            1000 цифр                    ? цифр        

Решение n=2, m= 10

 

1000 цифр                    250 цифр     

                                                           => ?> 250  

 

=л(погрешность) 

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

…

 

                                                 1000/        )>?> 1000/+0,00399)  

                                                                   302,2>?>  300,6

Точность оказалась даже выше, чем я предполагал.

( Она оказалась максимально возможной, ведь при переводе числа из одной

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

Теорема о логарифмической линейки

|G_n (N)/ G_m (N) – log_nm| ( Если N стремиться к бесконечности) для любого n и m (натуральные числа),n0, m0. На языке математического анализа

 

Логарифмическая линейка , потому что мы измеряем длину числа с помощью логарифма