Элементы теории чисел и криптозащита. Воронков Б.Н - 25 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

25
дет понять смысл результирующей последовательности чисел для различ-
ных начальных значений. Например, начиная с N = 27, последовательность
достигает нескольких пиковых значений, наибольшее из которых 9232 по-
лучается на 77 итерации перед тем, как она закончится как 1 на 111 итера-
ции. Максимальное значение 9232 также появляется для нескольких других
значений N, таких как 54, 73 и 97, которые обладают таким
свойством, что
их «длины путей» (число итераций для достижения 1) больше, чем для всех
меньших начальных значений N. Попытайтесь найти эти значения n (<700).
5.8. Проблема Варинга. Это известная теорема Лагранжа (1736–
1813), где каждое положительное целое число n может быть представлено
суммой, cамое большое, четырёх квадратов.
Например, числа 7 = 2
2
+ 1
2
+ 1
2
+ 1
2
, 15 = 3
2
+ 2
2
+ 1
2
+ 1
2
используют
для своего представления максимальное число квадратов – 4. Однако суще-
ствуют числа, требующие для своего представления меньшее число квадра-
тов: 8 = 2
2
+ 2
2
и 11 = 3
2
+ 1
2
+ 1
2
. (Во многих книгах по теории чисел со-
держатся ссылки на эту теорему, см. [7]). Для суммы положительных кубов
ситуация не так ясна для понимания. Известно, что суммы девяти кубов
всегда достаточно и даже семи кубами обходятся для представления всех
достаточно больших чисел n (существует догадка, что в действительности
достаточно четырёх кубов
для представления всех достаточно больших чи-
сел n). Напишите программу определения для всех n ≤ 10 000, скажем, наи-
меньшего требуемого количество кубов, чтобы их сумма составляла бы n.
В особенности выберите те числа, для представления которых требуются
все девять кубов. Это 23 и 239 (они действительно явяляются единственной
парой, для которой доказана необходимость использования 9
кубов), и пе-
речислите такие числа, которые требуют для своего представления восемь и
семь кубов.
Зададимся целью создать программу разумно эффективную. Органи-
зуем массив, скажем, d таким образом:
d: array [0. . 10000] of interger;
и определим d[0] := 0, d[1] := 1. Число d[j] должно быть (в итоге) наименьшим
числом кубов, необходимых для предствления j. Для каждого j = 2, 3, . . . ,
10 0000, в свою очередь,
значение d[j] начинается при d[j – 1] + 1, что соответ-
ствует представлению вида j = 1
3
+ (выражение для j – 1 в виде суммы кубов).
Теперь рассмотрим все числа вида t = j – i
3
≥ 0 (где i ≥ 2); если 1 + d[t] < d[j],
тогда заменяют d[j] на 1 + d[t]. (Заметим, что d[t] должно всегда быть опреде-
лено, так как t < j). Объясните, почему необходимо определить d[0] = 0?
(Начните, например, с j = 8). Напишите программу, которая реально вычисля-
ет кубы для заданных j.

Страницы