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

ГБОУ ЛИЦЕЙ № 000 ПРИ МЭИ

Проектная работа

       

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

Работу выполнили: 

Коновалов Матвей

и

Даниил Долматов

  класс 10«3» 

  Научный руководитель:

учитель математики

Москва

2018

СОДЕРЖАНИЕ

Титульный лист……………………………………………...1

Содержание…………………………………………………..2

Введение……………………………………………………...3

Глава 1. Основные понятия…………………………………3

1.1 Понятие мантиссы и экспоненты числа………….3

1.2 Граф, маршрут, цикл в графе……………………..3

1.3 Основные понятия систем счисления……………3

1.4 Понятие М-функции………………………………4

Глава 2. Ход работы и основные тезисы…………………..5

       2.1 Начало работы……………………………………..5

       2.2 Написание программ………………………………5

       2.3 Математический смысл в коде программ………..7

       2.4 Гипотеза……………………………………………8

       2.5 Итоги проекта……………………………………...9

       2.6 Общий вывод……………………………………...10

       2.7 Заключение………………………………………..11

Примеры графов…………………………………………….12

Литература……………………………………………….….13

Программы………………………………………………..…13

Выражаем благодарность………………………………..…13

ВВЕДЕНИЕ

К началу проекта у нас была последовательность, упомянутая в статье И. Акулича в журнале «Квант», где число умножается на свою первую цифру неограниченное количество раз, и тогда мы решили исследовать эту последовательность более подробно.

ГЛАВА 1. ОСНОВНЫЕ ПОНЯТИЯ

1.1 Понятие мантиссы и экспоненты числа

Мантисса –  дробная часть логарифма числа;

Логарифм – отношение числа b по основанию a (loga b) называется такое число c, и b=ac, то есть записи loga b=c и b=ac эквивалентны. Логарифм имеет смысл, если a > 0, а ≠ 1, b > 0;

Экспонента — показательная функция f(x)=exp(x)=ex, где e – число Эйлера (e≈2,718).

Мантиссно-экспоненциальная форма числа – число, приведенное к виду (A + m)ЧkH, где 1≤А<k, Z, 0≤m<1, kZ, HZ (A – первый разряд, m - мантисса, k – основание системы счисления, H – показатель экспоненты)

1.2  Граф, маршрут, цикл в графе

Граф – это совокупность двух конечных множеств вершин Х и множества пар вершин U. G = (X, U). Элементы множества U называются ребрами.

Маршрутом в графе называется последовательность ребер, в которой соседние ребра имеют общую вершину.

Цикл – цепь, у которой совпадают начальные и конечные вершины.

1.3 Основные понятия систем счисления

Система счисления – это совокупность правил и приемов записи чисел с помощью набора цифровых знаков. Количество цифр, необходимых для записи числа в системе, называют основанием системы счисления.

Различают два типа систем счисления:

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

Любое целое число в позиционной системе можно записать в форме многочлена:

, где

S - основание системы счисления; An - цифры числа, записанного в данной системе счисления; n - количество разрядов числа.

Пример. Число  123410 запишется в форме многочлена следующим образом: 1*103+2*102+3*101+4*100

Индо-арабская система счисления с основанием k – позиционная система счисления, при которой при записи числа х на nном месте справа стоит цифра, имеющая значение [x/kn] % kn+1.

1.4 Понятие М-функции

M-функция – функция M(a, m, k), определенная на тройках чисел (a, m, k), таких, что 1 ≤ a < k, Z, 0 ≤ m < 1, kN, и выдающая в качестве значений тройку ([a Ч (a + m)], {a Ч (a + m)}, k), при a Ч (a + m) < k, или ([a Ч (a + m)/k], {a Ч (a + m)/k}, k), при a Ч (a + m) ≥ k.

Допустим мы работаем в десятичной системе счисления, k=10. Возьмем уже известные нам число 52, разделим его на мантиссу и экспоненту, а позже мантиссу на целую (5) и дробную (0.2) части. Тогда a=5, b=0.2, а М-функция приобретает вид M(5, 0.2, 10). Проведем преобразование:

M(5, 0.2, 10) → M([5 Ч (5 + 0.2)], {5 Ч (5 + 0.2)}, 10) по условию, если a > k (26 > 10) мы делим 1 и 2 аргумент на к → M(2, 0.6, 10)

В итоге у нас получилась функция M(2, 0.6, 10). Позже можно провести еще бесконечное множество преобразований, что в данном случае приведет к зацикливанию 1 и 2 аргумента.

ГЛАВА 2. ХОД РАБОТЫ И ОСНОВНЫЕ ТЕЗИСЫ

2.1 Начало работы

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

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

Мы воспользовались тем, что число можно представить в виде произведения мантиссы и экспоненты.

Поскольку нас интересует только 1-я цифра мантиссы, мы разделили ее на целую (n) и дробную (ϕ) части.

Таким образом, n – это 1-я цифра числа.

Изучив на бумаге поведение некоторых чисел в десятичной системе счисления, мы обнаружили, что различные числа при домножении на свою первую цифру ведут себя по-разному:

В какой-то момент первая цифра становится 1, и число перестает расти; Мантисса зацикливается, и число растет неограниченно.

2.2 Написание программ

Рассмотрев некоторые числа, мы поняли, что вычислениями на бумаге ограничиваться не стоит. Тогда была написана первая программа "Интервалы" с подпрограммой "num_sys", которая вычисляет интервалы, на которых первая цифра числа сводится к единице или зацикливается.

Примеры вывода программы "Интервалы":

Base 3:

Интервалы, приводящие к единице: (1.0; 2.2222).

Base 8:

Интервалы, приводящие к единице: (2.4; 3.7777), (5.0; 5.7777), (6.5253; 6.7777), (7.475; 7.7777).

Интервалы, приводящие к бесконечности: (1.0; 2.3777), (4.0; 4.7777), (6.0; 6.5252), (7.0; 7.4747).

Base 10:

Интервалы, приводящие к единице: (1.0; 2.4999), (3.0; 3.3068), (3.3334; 4.9999), (6.0; 7.1428), (8.0; 8.9285), (9.0; 9.9206).

Интервалы, приводящие к бесконечности: (2.5; 2.9999), (3.3069; 3.3333), (5.0; 5.9999), (7.1429; 7.9999), (8.9286; 8.9999), (9.9207; 9.9999).

Во время работы с этой программой мы заметили, что первая цифра числа не всегда зацикливается бесконечно, но иногда выходит из цикла. Тогда нам пришлось написать еще одну программу - "Зацикливания первых цифр", которая находит все циклы в заданной системе счисления и проверяет каждый из них. Если через 200 повторений первая цифра не выходит из цикла, то программа считает этот цикл бесконечным.

Примеры вывода программы "Зацикливания первых цифр":

Десятичная система счисления:

  1 2 3 4 5 6 7 8 9

  1: 1 0 0 0 0 0 0 0 0

  2: 0 0 0 1 1 0 0 0 0

  3: 1 0 0 0 0 0 0 0 1

  4: 1 0 0 0 0 0 0 0 0

  5: 0 1 0 0 0 0 0 0 0

  6: 0 0 1 1 0 0 0 0 0

  7: 0 0 0 1 1 0 0 0 0

  8: 0 0 0 0 0 1 1 0 0

  9: 0 0 0 0 0 0 0 1 0

5 2: True

9 8 6 3: False False

Двенадцатеричная система счисления:

  1 2 3 4 5 6 7 8 9 A B 

  1: 1 0 0 0 0 0 0 0 0 0 0

  2: 0 0 0 1 1 0 0 0 0 0 0

  3: 0 0 0 0 0 0 0 0 1 1 1

  4: 1 0 0 0 0 0 0 0 0 0 0

  5: 0 1 0 0 0 0 0 0 0 0 0

  6: 0 0 1 0 0 0 0 0 0 0 0

  7: 0 0 0 1 0 0 0 0 0 0 0

  8: 0 0 0 0 1 0 0 0 0 0 0

  9: 0 0 0 0 0 1 1 0 0 0 0

  10: 0 0 0 0 0 0 0 1 1 0 0

  11: 0 0 0 0 0 0 0 0 0 1 0

5 2: False False

9 6 3: False True

10 9 6 3: False False

11 10 9 6 3: False False

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

Тринадцатеричная система счисления:

  1 2 3 4 5 6 7 8 9 A B C

  1: 1 0 0 0 0 0 0 0 0 0 0 0

  2: 0 0 0 1 1 0 0 0 0 0 0 0

  3: 0 0 0 0 0 0 0 0 1 1 1 0

  4: 1 0 0 0 0 0 0 0 0 0 0 0

  5: 1 1 0 0 0 0 0 0 0 0 0 0

  6: 0 1 1 0 0 0 0 0 0 0 0 0

  7: 0 0 1 1 0 0 0 0 0 0 0 0

  8: 0 0 0 1 1 0 0 0 0 0 0 0

  9: 0 0 0 0 0 1 0 0 0 0 0 0

  10: 0 0 0 0 0 0 1 1 0 0 0 0

  11: 0 0 0 0 0 0 0 0 1 1 0 0

  12: 0 0 0 0 0 0 0 0 0 0 1 0

5 2: False False

9 6 3: False False

10 7 3: False False

11 9 6 3: False False

11 10 7 3: False False

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

2.3 Математический смысл в коде программ

Общий алгоритм для программы «Интервалы»:

Перевести число в нормализованную запись. Умножить число на первую цифру, не учитываю его экспоненту. Перевести полученное число в нормализованную запись, приведя число к нужной первой цифре. Повторить (1)-(3) для нового числа, если требуется. Сравнить записи полученного числа и того, которое требуется получить, в нормализованной записи (где ц – дробная часть мантиссы), не учитывая экспоненту. Решить неравенство относительно мантиссы.

В данном проекте мы полностью исследовали восьмеричную и десятичную систему счисления.

Поэтому можно привести пример 1 из десятичной системы счисления:

7 переходит в 4 и в 5 (см рис.1 в «Примеры графов»; то есть число в десятичной записи с первой цифрой 7 переходит после умножения на первую цифру в число с первой цифрой 4 или 5), потому что

49 ≤ (7+ц)2 < 56, где ц - дробная часть мантиссы.

Нужно выяснить, при каких значениях ц 7 переходит в 4:

Пусть у нас есть число (7+ц) Ч 10k, тогда при его перемножении на 1 цифру:

(7+ц) Ч 10k Ч 7 = (4+0,9+0,7ц) Ч 10k-1;

0,7ц+0,9+4 < 5;

Отсюда: при ц < число из вершины 7 переходит в вершину графа 4, в противном случае в вершину графа 5.

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

2.4 Гипотеза

Больше всего проблем у нас возникло с гипотезой, доказать которую так и не удалось. Для ее выведения нам пришлось углубиться в теорию чисел, ввести такие понятия, как М-функция, но, отчаявшись, попросить о помощи.

Данная гипотеза описывает те случаи, когда число неограниченно возрастает, но его первая цифра зацикливается.

ОСНОВНАЯ ГИПОТЕЗА

Если в перворазрядном графе перворазрядно-квадратной последовательности относительно индо-арабской системы счисления с основанием k существует циклический путь а0 -> … -> an, такой, что

то М-функция имеет периодический цикл длиной в n+1, в котором первое число тройки будет принимать значения

а1, …, an соответственно.

Покажем, как работает данная гипотеза на примере, допустим будем работать в 36-ричной системе счисления:

Сокращенный вывод программы «Зацикливание первых цифр»:

10 3: False False

11 3: False False

18 9 2 4 : True

19 10 2 4: False False

19 10 3 9 2 4: False False

25 18 9 2 5: False False

26 18 9 2 5: False False

26 19 10 2 5: False False

26 19 10 3 9 2 5: False False

27 20 11 3 9 2 5: False False

27 20 11 3 10 2 5: False False

28 21 12 4 18 9 2 5: False False

28 21 12 4 19 10 2 5: False False

28 21 12 4 19 10 3 9 2 5: False False

28 22 13 4 18 9 2 5: False False

28 22 13 4 19 10 2 5: False False

28 22 13 4 19 10 3 9 2 5: False False

28 22 13 5: False False

28 22 14 5: False False

29 23 14 5: False False

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

18(1810 → I36) 9 2 4 : True

936 x 236 = I36

I36 x I36 = 9036

9036 x 436 = 10036

Основание системы – 3610 →1036

10236 = 10036

10036 = 10036

Таким образом произведение всех элементов цикла равно основанию системы счисления в натуральной степени, что показывает верность нашей гипотезы на примере 36-ричной СС.

Позже экспериментальным методом обнаружилось, что существуют системы счисления, например, 23, где нет периодических циклов, но не всегда первая цифра сводиться к 1, а число растет бесконечно, но первая цифра не зацикливается. Такие случаи не объясняются данной теоремой, и пока мы не можем сказать про них больше.

2.5 Общий вывод

В ходе работы мы выяснили, что с числом, домножаемым на свою первую цифру, может происходить следующее:

В какой-то момент первая цифра становится 1, и число перестает расти; такое происходит со всеми числами в системах счисления с основаниями, например, 2, 3, 4, 5, 6, 7, 9…; Мантисса зацикливается, и число растет неограниченно; такое происходит с некоторыми числами в системах счисления с основаниями, например, 8, 10, 27, 30, 36, 128…; выведена гипотеза, описывающая все такие системы счисления; Мантисса не зацикливается, но число все равно растет неограниченно(?); такое происходит с некоторыми числами в таких системах счисления, как 23, 30…, но это не доказано пока что.

2.6 Итоги проекта

К концу работы над проектом мы добились следующих результатов:

Были полностью исследованы системы счисления с основаниями от 2 до 10; В системах счисления с основаниями 8 и 10 доказана возможность бесконечного возрастания перворазрядно-квадратной последовательности, то есть некоторые числа в этой системе счисления при домножении на первую цифру растут неограниченно; Выведена основная перворазрядно-квадратная гипотеза; Получено множество примеров систем счисления, в которых некоторые числа растут неограниченно; Написана программа «Зацикливание первых цифр» («5murder. pas»), строящая матрицу смежности перворазрядного графа и ищущая в ней циклы; Построены вручную перворазрядные графы от 2 до 16; Выдвинута гипотеза о возможности бесконечного возрастания перворазрядно-квадратной последовательности, не переводимой по в периодический цикл в М-функции, например, в системе счисления с основанием 23. Была написана программа «Интервалы» («intervals. py»), определяющая при каких начальных числах перворазрядно-квадратная последовательность бесконечно возрастает, причём делается различие между попаданием мантиссы в бесконечный цикл (с ростом экспоненты) и бесконечным ростом без зацикливания («непериодический цикл»). С помощью этой программы получены результаты, приведшие к гипотезе об основании 23, и получены численные результаты для ещё некоторых систем счисления («results. txt»).

2.7 Заключение

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

ПРИМЕРЫ ГРАФОВ

рис.1- десятичная система

рис.2 – восьмеричная система

Рис.1

Рис.2

Такие графы можно строить вручную, а также строить матрицы смежности графов для систем счисления, например, в программе «Зацикливания первых цифр» (5murder. pas).

ЛИТЕРАТУРА

Научно-популярный физико-математический журнал "Квант" - статья
И. Акулича «Бурсацкое развлечение»

ПРОГРАММЫ

«Интервалы» («intervals. py»), язык – Python 3, см приложение 1; «Зацикливание первых цифр» («5murder. pas»), язык – Pascal ABC, см приложение 2.

ВЫРАЖАЕМ БЛАГОДАРНОСТЬ

Янковскому Владимиру (за помощь в работе с гипотезой).