\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 i0$, το χοϊχςατιτψσρ λ ϋαηυ \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