Теория алгоритмов. Зюзысов В.М. - 51 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

В построении следующей последовательности повторяется применение оператора F
b
с
последующим вычитанием 1. Первые девять членов суть
G
0
(266) =
266 =
222
12
)2(
12
++
+
+
G
1
(266) =
F
2
(266)–1 =
233
13
)3(
13
++
+
+
= 443426488243037769948249630619149892886
(39 цифр)
G
2
(266) =
F
3
(G
1
(266))–1 =
144
14
)4(
14
++
+
+
= 3231700607…853611059596231681 (617 цифр)
G
3
(266) =
F
4
(G
2
(266))–1 =
15
)5(
55
15
+
+
+
(10922 цифры)
G
4
(266) =
F
5
(G
3
(266))–1 =
166
16
)6(
16
−
+
+
+
=
565...65656
56
)6(
16
+⋅++⋅+⋅+
+
≈ 4⋅10
217832
G
5
(266) = F
6
(G
4
(266))–1
=
475...75757
57
)7(
17
+⋅++⋅+⋅+
+
≈ 10
4871822
G
6
(266) = F
7
(G
5
(266))–1
=
81
8
8
+
+ 5⋅8
8
+ 5⋅8
5
+… + 5⋅8 + 3 ≈ 2⋅10
121210686
G
7
(266) = F
8
(G
6
(266))–1
=
91
9
9
+
+ 5⋅9
9
+ 5⋅9
5
+… + 5⋅9 + 2 ≈ 5⋅10
3327237896
G
8
(266) = F
9
(G
7
(266))–1
=
10 1
10
10
+
+ 5⋅10
10
+ 5⋅10
5
+… + 5⋅10 + 1 ≈
11
10
10
Последовательность {G
k
(n)} называется последовательностью Гудстейна.
Теорема 25. (Гудстейн).
Для любого n существует такое k, что G
k
(n) = 0.
Кажется невероятным, но это так. А чтобы в это поверить, мы рекомендовали бы
читателю проделать вышеописанную процедуру, для начала – с числом «3».
G
0
(3) = 2 + 1
G
1
(3) = F
2
(3) –1 = 3
G
2
(3) = F
3
(G
1
) –1 = 4 – 1 = 3
G
3
(3) = F
4
(G
2
) –1 = 2
G
4
(3) = F
5
(G
3
) –1 = 1
G
5
(3) = F
6
(G
6
) –1 = 0
Попробуем проверить утверждение теоремы для n=4:
2
2
3
3
– 1 = 2×3
2
+2×3+2
2×4
2
+2×4+1
2×5
2
+2×5
2×6
2
+ 6 +5
2×7
2
+ 7 +4
2×8
2
+ 8 +3
2×9
2
+ 9 +2
2×10
2
+ 10 +1
2×11
2
+ 11
2×12
2
+ 12–1 = 2×12
2
+ 11
2×13
2
+ 10

Страницы