Дипломная работа: Возвратные задачи
Таким образом, мы получили, что
J((bm bm-1 … b1 b0 )2 ) = (bm-1 … b1 b0 bm )2 (9)
т.е. J(n) получается путем циклического сдвига двоичного представления n влево на один сдвиг.
Рассмотрим свойства функции J(n).
Если мы начнем с n и итерируем J-функцию m+1 раз, то тем самым осуществляем циклический сдвиг на m+1 битов, а т.к. nявляется (m+1)-битовым числом, то мы могли бы рассчитывать в итоге снова получить n. Но это не совсем так. К примеру, если n = 27, то J(11011) = ((10111)2 ), но затем J(10111) = ((1111)2 ), и процесс обрывается: когда 0 становится старшим битом – он пропадает (т.к. принято, что коэффициент при старшей степени не равен 0). В действительности J(n) всегда должно быть ≤ n по определению, т.к. J(n) есть номер уцелевшего; и если J(n) < n, мы никогда не сможем получить снова n в следующих итерациях.
Многократное применение J порождает последовательность убывающих значений, достигающих, в конце концов «неподвижной точки» n, такой, что J(n)=n. Докажем, что J порождает последовательность убывающих значений, т.е. покажем, что 2n > 2n -1 + 2n -2 +…+21 + 1 при n≥ 1.
Докажем методом математической индукции по n:
1) База: n=1, 21 > 20 (верно);
2) Индуктивный переход: пусть верно для всех чисел t≤ (n–1) , т.е. выполняется неравенство 2t -1 > 2t -2 + 2t -3 +…+21 + 1. Докажем для t=n:
(2n -1 > 2n -2 + 2n -3 +…+21 + 1) умножим на 2, получим 2n > 2n -1 + 2n -2 +…+22 + 21 . Левая и правая части неравенства четные числа, тогда между ними есть хотя бы одно нечетное число, следовательно, прибавление 1 к правой части неравенства (четное число +1 = нечетное число) неравенство не изменит. Т.о. получаем нужное нам неравенство: 2n > 2n -1 + 2n -2 +…+21 + 1 при n ≥ 1.
Свойство циклического сдвига позволяет выяснить, чем будет «неподвижная точка»: итерирование функции m и более раз всегда будет порождать набор из одних единиц со значением 
, где ν(n) – число равных 1 битов в двоичном представлении n (это следует из того, что имеем последовательность 20 , 21 , 22 ,…,2n -1 , 2n , и по формуле суммы геометрической прогрессии получаем 
). Так, например: ν(27) = ν(11011) = 4, тогда J(J(…J(27)…)) =24 −1=15
|
Теперь давайте вернемся к нашему первоначальному предположению, что J(n) = 
при четном n. Вообще-то это неверно, но мы выясним, когда это верно: J(n) = , тогда 2k+1 = 
=> k = 
. Если число k = = целое, то n= 2m + kбудет решением, т.к. k< 2m . Нетрудно убедиться, что (2m − 2) кратно 3, когда m нечетно, но не когда m четно. Действительно, если m – нечетно, то 2m − 2 = 22 k +1 − 2 = 2(4k − 1). Докажем методом математической индукции, что (4k − 1) делится на три (где 
):
1) База: k=1, 4−1=3, три делится на три (верно);
2) Индуктивный переход: пусть верно для всех чисел t≤(k−1), т.е (4t −1) делится на три. Докажем для t=k:
4k − 1 = 4(4k -1 − 1) + 3 
(4k -1 − 1) делится на три, и 3 делится на три => (4к −1) делится на три.
Таким образом, показали, что для m – нечетного (2m − 2) делится на 3.
Теперь покажем, что при m – четном (2m − 2) не делится на 3. Предположим противное: пусть (2m − 2) делится на 3 при четном m, тогда 
, числа 2 и 3 взаимнопростые, следовательно, (
) должно делится на 3, т.е. =3q
, но 
, a
, т.е. получили, что 
, а это не верно. Следовательно, наше предположение не верно и 2m − 2 не делится на 3 при четном m.
Таким образом, имеем бесконечно много решений уравнения J(n) = , и первые такие:
| m | k | N= 2m + k | J(n) =2k+1= | n (двоичное) |
| 1 | 0 | 2 | 1 | 10 |
| 3 | 2 | 10 | 5 | 1010 |
| 5 | 10 | 42 | 21 | 101010 |
| 7 | 42 | 170 | 85 | 10101010 |
Правый крайний столбец содержит двоичные числа, циклический сдвиг которых на одно позицию влево дает тот же самый результат, что и обычный сдвиг на одну позицию вправо (деление пополам).
Далее обобщим J - функцию, т.е. рассмотрим рекуррентность схожую с (7), но с другими константами: α, β и γ; найдем решение в замкнутой форме.
f(1) = α,
f(2n) = 2f(n) + β при n ≥ 1, (10)
f(2n + 1) = 2f(n) + γ при n ≥ 1.
Составим таблицу для малых значений n:
Анализируя таблицу можно сделать предположение, что коэффициенты при α равны наибольшим степеням 2, не превосходящим n; между последовательностями 2 коэффициенты при β уменьшаются на 1 вплоть до 0, а при γ увеличиваются на 1, начиная с 0. Если выразить f(n) в виде:
f(n) = A(n)∙α + B(n)∙β + C(n)∙γ (11)
то, по-видимому,
A(n) = 2m ,
B(n) = 2m −1−k,(12)
С(n) = k.
Здесь n = 2m + k и 0 ≤ k < 2m при n ≥ 1.
Докажем соотношения (11) и (12).