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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

24
Интересно отметить, что двоичные числа не всегда имеют палиндром.
Предлагаем для доказательства, что 10110 никогда не даст единицу. Покажите,
что после четырёх итераций оно должно стать 10110100, или, скажем, 101
2
010
2
,
где дополнительные цифры указывают число повторяющихся десятичных
цифр. Покажите, что четыре последующие итерации дадут 101
3
010
3
и т. д. До-
кажите, что со второй итерации число выборов между 10 . . . 00 и 11 . . . 01, где
«. . .» указывает на некоторую последовательность нулей и единиц.
5.6. Перевод вагона с грузом на запасный путь.
Эта проблема каса-
ется перевода на запасный путь вагонов с грузом при наличии нескольких
запасных путей. Мы определим указатель m(
σ
) последовательности
σ
це-
лых чисел, таких как 5632413572623 (в общем виде a
1
, . . . , a
r
при 1 ≤ a
i
≤ n
для каждого i, а каждое простое число от 1 до n должно появиться, по край-
ней мере, один раз).
5.6.1. Начнем, записывая слева направо и сверху вниз в сторону
уменьшения все первые и все вторые (если есть таковые) элементы, затем
проделывая аналогичные действия со всеми вторыми членами последова-
тельности, уже
использованными ранее, всеми третьими (если существуют).
располагая их справа от всех этих вторых и т. д. В примере мы получили
122. Надо исключить их из последовательности.
5.6.2. Начиная слева в новой (укороченной) последовательности и за-
писывая ниже все появления наименьших чисел a
i
, затем всех a
i
+ 1 (если
таковые есть) справа от этих a
i
, потом проделывая сходные операции с чле-
нами a
i
+ 1, уже использованными ранее, помещая все a
i
+ 2 справа от полу-
ченной последовательности и т. д. В примере получено 233.
5.6.3. Повторяем до тех пор, пока последовательность не будет окон-
чательно сокращена. В примере это даёт 345, затем 566 и, наконец, 7.
Тогда m(
σ
) будет числом этих несокращаемых подпоследовательно-
стей, с которыми вы завершили работу. Связь с постановкой вагонов с гру-
зом на запасной путь описана в [7]. Грубо говоря, это число переводов не-
обходимо, чтобы изменить первоначальный порядок 56324 . . . нумерован-
ных вагонов с грузом в порядок 1222333455667, используя локомотив и но-
мера запасных путей.
5.7. 3N + 1 проблема.
Это хорошо известная, но очень трудная про-
цедура. Начиная с некоторого положительного числа N, применим следую-
щую функцию к N:
31, 21,
()
/2, 2 .
NNn
fN
NNn
+
=+
⎧
=
⎨
=
⎩
где n = 0, 1, 2, . . .
Возникает вопрос: может ли последовательность N, f(N), f(f(N)), . . .
случайно стать 1 (и, следовательно, пройти через цикл 1, 4, 2, 1, . . . после
этого)? Весьма просто написать программу для итерации f; но труднее бу-

Страницы