\input style
%% 118
������������ ��� $100\le N\le 60\ 000$ ������ ��������� �������:
$$
\displaylines{
\hbox{$1.09N^{1.27}$ ��� $.30N(\ln N)^2-1.35N\ln N$ ��� ������������������ 
����� $2^k+1$,\dots, 9, 5, 3, 1;}\hfill\cr
\hbox{$1.22N^{1.26}$ ��� $.29N(\ln N)^2-1.26N\ln N$ ��� ������������������ 
����� $2^k-1$, \dots, 15, 7, 3, 1;}\hfill\cr
\hbox{$1.12N^{1.28}$ ��� $.36N(\ln N)^2- 1.73N \ln N$ ��� 
������������������ ����� $(2^k\pm 1)/3$, \dots, 11, 5, 3, 1;}\hfill\cr
\hbox{$1.66N^{1.25}$ ��� $.33N(\ln N)^2-1.26N\ln N$ ��� ������������������ 
����� $(3^k-1)/2$, \dots, 40, 13, 4, 1.}\hfill\cr
}
$$
퀏�����, ��� $N=20\ 000$ ��� ���� ���� ����� ����� 
�������� �������������� $B\approx 31\ 000$, $33\ 000$, $35\ 000$, 
$39\ 000$. 򀁋.~7 ����
\htable{򀁋��� 7}%
{ꎋ������� ����������� �� ���������� (������� ���  $N=20 000$)}%
{\bskip\hfill$#$\bskip\hfill&\bskip\hfill$#$\bskip\bskip\hfill&\bskip\hfill$#$\bskip\hfill&\bskip\hfill$#$\bskip\bskip\hfill&\bskip\hfill$#$\bskip\hfill&\bskip\hfill$#$\bskip\bskip\hfill\cr
h_s & B_s & h_s & B_s & h_s & B_s \cr
\noalign{\hrule}
4095 & 19460 & 4097 & 19550 & 3280 & 25210\cr
2047 & 15115 & 2049 & 14944 & 1093 & 28324\cr
1023 & 15869 & 1025 & 15731 &  364 & 35477\cr
 511 & 18891 &  513 & 18548 &  121 & 47158\cr
 255 & 22306 &  257 & 21827 &   40 & 62110\cr
 127 & 27400 &  129 & 27814 &   13 & 88524\cr
  63 & 35053 &   65 & 33751 &    4 & 74599\cr
  31 & 34677 &   33 & 34303 &    1 & 34666\cr
  15 & 51054 &   17 & 46044\cr
   7 & 40382 &    9 & 35817\cr
   3 & 24044 &    5 & 19961\cr
   1 & 16789 &    3 &  9628\cr
     &       &    1 & 13277\cr
\noalign{\hrule}
}
�������� ������� ����, ��� �������������� ����������� �� ���������� � ���� 
�� ���� �������������. 랁������, ��� \emph{���} ���� ������� $\alpha N 
(\ln N)^2+\beta N\ln N$ � $\beta N^\alpha$, �������, �������� ������ 
����������� � ������������ �������, ���� ��������� ������� ���� 
����������� ����� ��� ������� ��������� $N$. 䀋������� ������������ ���� 
��������� ��� ������������������ ����� $2^k-1$ �� ��������� $N$, 
����������� $250\ 000$; ����� ���� ��������� � $N = 250\ 000$ ���� 
�������� $B\approx 7\ 900\ 000$ ��� ����������� ����������� ���������� 
$50\ 000$. "퀈����� �����������" ��������� ��� ��������� $100 \le N \le 
250\ 000$ ��������� �������������� $1.21N^{1.26}$ �~$.39N (\ln N)^2- 2.33 
N \ln N$. � ���
%%119
������������ � ������������� ��������� �������� �������� ����� ������ ��, 
� �� ����� ��� ������������ � ��������������� ������������� �������� 
����� ����������, �� ������� ������������, ��� ������ ��������� ������� 
��������� �������� ��������������� ��������� ������ �����.

��� ������������ ������ �� ���� ������� �� ����������� ���� ������������, 
� �� �� �������� ��������� ��� ����������� ���������� � ���, ����� �� 
������������������ ����� �������� ���������� ��� ��������� D. ������ 
���������� ���� $(3^k-1)/2$ �� ����������� ����������� ����� 
����������� � ��������� ��� ��� ��������� ���� �������� 5/8 ����� 
����������, ����������� ��� ����� ������ �����, ��, ��������,
 \emph{������� �������� ������������������ ����� ��������� �������:}
$$
\hbox{\it ���� $h_t=1$, $h_{s+1}=3h_s+1$ � ������������ �� $h_t$, ����� 
$h_{t+2}\ge N$.}
\eqno (8)
$$

\section ⑒���� � ������. ���� ������ ����� ����� � ���������� ������ 
���� ������������������ ������� �������. 񐅄� ����� �������� ��������� 
��������� ���� �� ����� ������ ������������ �� ���������� ������� 
�������� ������, ��������� ������������� �������� ������, ����������� 
�������� �������� ��������, ����� ���� ������������ ������. 䀋������� 
���������� ���� ����� ���� ����� ����� � \S~2.4, � ������� 
��������� �������� ������� ��������. ������, ��� ��� ����������� � 
������ ��������� ���������, ��� ������� �������. ꀊ��� �������� 
���������� ��������� ������ ��� ��������� S?

񎐒������ �������� ��������� ������� �� ���� �������� ��������:
\medskip
\item{i)} ��������� �������������� ����� ��� ���������� ����������� 
�����, �������� ��� ������� ������� �����;

\item{ii)} ������� ����� ������ � ������������ ����� �������������� �����.
\medskip
\noindent 􀉋---���, ��������, �������� ������, � �������� S ������������ 
���, ��������� ���������������� ������������� (�.~2.2.2);
������� ��� ���������� ������ �������� ������� ���������� ����������� 
�������� �������� �������. � ������ �������, ��� ��������, ��� ��� ������� 
�������� �������� ��������� ������������� (�.~2.2.3), ��� ��� ��� ���� 
��������� �������� ���� ��������� ������; ������ ��������---���������������� 
��������---��� ��������� ������������� ����� ��� �� ������, ��� � ��� 
����������������. ������ ������ ������ ��������������� � ����� � ��� 
�� �����������, �� ���������� ����� ������ � ����� ������. 򀊈� �������, 
�������� � ������, ��� "����������" ��������� ������ ��� ������ ������� 
�������---��������
%% 120
������ � ����� ������. 󄎁�� ����� �������� �������� S, 
����� ������ �������������� �  ������������ �������.

\alg L.(⑒���� � ������.) �����������, ��� ������ $R_1$,\dots, $R_N$ 
�������� ����� $K_1$, \dots, $K_N$ �~"���� �����" $L_1$, \dots, $L_N$, � 
������� ����� ��������� ����� ��~0 ��~$N$;
������� ����� ��� ���� ���� ����� $L_0$ � ��������� ������������� ������ 
$R_0$ � ������ �����. �������� ������������� ���� ����� ���, ��� ������ 
����������� ���������� � ������������ �������. �, ���� $p(1) \ldots 
p(N)$---"����������" ������������, �����, ��� 
$K_{p(1)}\le \ldots \le K_{p(N)}$, �� � ���������� ���������� ��������� 
�������
$$
L_0=p(1); L_{p(i)}=p(i+1)\ \hbox{��� $1\le i<N$}; L_{p(N)}=0. 
\eqno(9)
$$
\st[���� �� $j$.] 󑒀������ $L_0\asg N$, $L_N\asg0$. ($L_0$ 
������ "�������" ������, � 0---������ ������; �������������, ������, �� 
��������, �����������.) ⛏������ ���� �� \stp{2} �� \stp{5} ��� $j=N-1$, 
$N-2$, \dots, $1$ � ��������� ������ ���������.

\st[󑒀������ $p$, $q$, $K$.] 󑒀������ $p\asg L_0$,  $q\asg0$, 
$K\asg K_j$. (� ����������� ����� �� ������� ������ $R_j$ � ������ ����� � 
��������� ������ ����� ��������� ����� $K$ � ����������� ������� � 
������������ �������. ������� $p$ �~$q$ ������ ����������� �� ������� 
����� � ������, ������ $p=L_q$, ��� ��� $q$ ������ �� ���� ��� ������� 
�� $p$.)

\st[񐀂���� $K$, $K_p$.] 呋� $K\le K_p$, �� ������� � ���� \stp{5}. (� 
����� ������� ��������� ������ $R$ � ������ ����� $R_q$ �~$R_p$.)

\st[������� $p$, $q$.] 󑒀������ $q\asg p$, $p\asg L_q$. 呋� $p>0$,
 �� ������������ � ���� \stp{3}. (呋� $p=0$, �� $K$---���������� ����, 
������������ �� ��� ���; �������������, ������ $R$ ������ ������� � 
����� ������, ����� $R_q$ � $R_0$.)

\st[⑒����� � ������.] 󑒀������ $L_q\asg j$, $L_j\asg p$. 
\algend

\ctable{
\strut\bskip\hfill$#:$\hfill\bskip&&\bskip\hfill#\hfill\bskip\cr
\noalign{\rightline{\it 򀁋��� 8}}
\noalign{\centerline{\bf ��� ���������� ��������� ������� � ������}}
\noalign{\hrule}
  j&  0&  1&  2&  3&  4&  5&  6&  7&  8&  9& 10& 11& 12& 13& 14& 15& 16\cr
K_i&---&503&087&512&061&908&170&897&275&653&426&154&509&612&677&765&703\cr
L_j& 16&---&---&---&---&---&---&---&---&---&---&---&---&---&---&---&  0\cr
L_j& 16&---&---&---&---&---&---&---&---&---&---&---&---&---&---&  0& 15\cr
L_j& 14&---&---&---&---&---&---&---&---&---&---&---&---&---& 16&  0& 15\cr
\noalign{\hrule}
}
%% 121
\bye