Несколько замечаний о проблеме Коллатца
Розглянуто гіпотезу Коллатца (3x +1 проблема). Запропоновано нову форму функції Коллатца, яку можна досліджувати аналітично. За допомогою афінних автоматів досліджено структуру ядра цієї функції і на її основі побудовано зростаючу ієрархію чисел Бома–Зонтаччі. Введено також систему кодування успішни...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2013 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/86232 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Несколько замечаний о проблеме Коллатца / И.К. Рысцов // Кибернетика и системный анализ. — 2013. — Т. 49, № 3. — С. 32-46. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860091486061723648 |
|---|---|
| author | Рысцов, И.К. |
| author_facet | Рысцов, И.К. |
| citation_txt | Несколько замечаний о проблеме Коллатца / И.К. Рысцов // Кибернетика и системный анализ. — 2013. — Т. 49, № 3. — С. 32-46. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто гіпотезу Коллатца (3x +1 проблема). Запропоновано нову форму функції Коллатца, яку можна досліджувати аналітично. За допомогою афінних автоматів досліджено структуру ядра цієї функції і на її основі побудовано зростаючу ієрархію чисел Бома–Зонтаччі. Введено також систему кодування успішних траєкторій, які складаються з ітерацій функції Коллатца, натуральними числами і показано, що будь-яке натуральне число є кодом деякої траєкторії.
The Collatz conjecture (the 3x +1 problem) is considered in the paper. A new form of the Collatz function is proposed, which can be studied analytically. The structure of the core of this function is analyzed by affine automata and used to construct an increasing hierarchy of Bohm–Zontacchi numbers. Successful trajectories of Collatz function iterations are coded by natural numbers and any natural number is shown to be a code of some trajectory.
|
| first_indexed | 2025-12-07T17:22:46Z |
| format | Article |
| fulltext |
ÓÄÊ 519.713.2
È.Ê. ÐÛÑÖÎÂ
ÍÅÑÊÎËÜÊÎ ÇÀÌÅ×ÀÍÈÉ Î ÏÐÎÁËÅÌÅ ÊÎËËÀÒÖÀ
Êëþ÷åâûå ñëîâà: ( )3 1x � -ïðîáëåìà, ãèïîòåçà Êîëëàòöà, àôôèííûå àâòîìàòû.
ÂÂÅÄÅÍÈÅ
 ñîâðåìåííîé ìàòåìàòèêå îñòàëîñü ìàëî ïðîáëåì, ñóòü êîòîðûõ ìîæíî îáúÿñ-
íèòü øêîëüíèêó, íî êîòîðûå íå ìîãëè áû ðåøèòü ïðîôåññèîíàëû. Îäíà èç
íèõ — ïðîáëåìà Êîëëàòöà, èëè ( )3 1x � -ïðîáëåìà. Èçâåñòíîìó ìàòåìàòèêó Ï. Ýð-
äåøó ïðèïèñûâàþò ñëåäóþùåå ïåññèìèñòè÷åñêîå èçðå÷åíèå: «ìàòåìàòèêà íå ãîòî-
âà ê ðåøåíèþ ïîäîáíûõ ïðîáëåì» [1]. Òåì íå ìåíåå êîëè÷åñòâî ïîñâÿùåííûõ åé
ðàáîò ñ êàæäûì ãîäîì âîçðàñòàåò è óæå ïðîâåäåíà êîíôåðåíöèÿ.
Ôóíêöèÿ Êîëëàòöà C n( ) îïðåäåëÿåòñÿ íà íàòóðàëüíûõ ÷èñëàõ ñëåäóþùèì
îáðàçîì:
C n
n n
n n
( )
/ ,
,
�
�
�
�
�
2
3 1
(1)
Äëÿ êàæäîãî íàòóðàëüíîãî ÷èñëà n ñòðîèòñÿ òðàåêòîðèÿ ( , ( ), ( ( )), )n Ñ n C Ñ n � ,
ñîñòîÿùàÿ èç ïîñëåäîâàòåëüíûõ èòåðàöèé ýòîé ôóíêöèè. Â äàëüíåéøåì k-êðàò-
íóþ èòåðàöèþ ôóíêöèè îáîçíà÷èì C nk( ) ( ) . Ñîãëàñíî ãèïîòåçå Êîëëàòöà ëþáàÿ
òðàåêòîðèÿ äîñòèãàåò åäèíèöû.
Ïðîáëåìà Êîëëàòöà (ôîðìà 1). Äëÿ âñÿêîãî íàòóðàëüíîãî ÷èñëà n ñóùåñò-
âóåò íàòóðàëüíîå ÷èñëî k òàêîå, ÷òî C nk( ) ( ) �1.
Èç (1) âèäíî, ÷òî ïî äîñòèæåíèþ åäèíèöû ïðîöåññ âõîäèò â öèêë (1, 4, 2),
êîòîðûé íàçûâàåòñÿ òðèâèàëüíûì. Äðóãèìè ñëîâàìè, èòåðàöèîííûé ïðîöåññ «çà-
áûâàåò» íà÷àëüíîå ñîñòîÿíèå è âñåãäà äîñòèãàåò òðèâèàëüíîãî öèêëà. Ìîæíî
óáåäèòüñÿ â ñïðàâåäëèâîñòè ãèïîòåçû Êîëëàòöà, ïðîâåäÿ íåñëîæíûå âû÷èñëåíèÿ
äëÿ íåáîëüøèõ íàòóðàëüíûõ ÷èñåë.  íàñòîÿùåå âðåìÿ ýòà ãèïîòåçà ïðîâåðåíà
ñ ïîìîùüþ êîìïüþòåðîâ äëÿ ÷èñåë, íå áîëüøèõ ÷åì 100 2 112 1050 17� �, , è ðåêîð-
äû ïðîäîëæàþò ñòàâèòüñÿ [2]. Íî äîêàçàòåëüñòâà åå ñïðàâåäëèâîñòè äëÿ
íàòóðàëüíûõ ÷èñåë ïîêà íå ñóùåñòâóåò, õîòÿ ñàìîé ïðîáëåìå óæå 70 ëåò.
 íàñòîÿùåé ñòàòüå ñäåëàíà ïîïûòêà ïî-íîâîìó âçãëÿíóòü íà óæå èçâåñòíûå
ðåçóëüòàòû ñ òî÷êè çðåíèÿ òåîðèè àâòîìàòîâ. ×òîáû èçëîæåíèå áûëî äîñòóïíûì
øèðîêîìó êðóãó ÷èòàòåëåé, ïðèâåäåíû ëèøü ýëåìåíòàðíûå ìåòîäû, ïðè ýòîì
ìíîãèå ðåçóëüòàòû íå ðàññìîòðåíû. Èç íàèáîëåå èíòåðåñíûõ íåýëåìåíòàðíûõ
ïîäõîäîâ îòìåòèì îáîáùåíèå ôóíêöèè Êîëëàòöà íà êîëüöî 2-àäè÷åñêèõ öåëûõ
÷èñåë [3], îäíàêî ýòè ðåçóëüòàòû äîñòîéíû îòäåëüíîé ðàáîòû.
Ñ òî÷êè çðåíèÿ òåîðèè àâòîìàòîâ èìååì îäíîìåðíûé àôôèííûé àâòîìàò,
îáëàäàþùèé êðàéíå íåðåãóëÿðíûì ïîâåäåíèåì. ×òîáû óáåäèòüñÿ â ýòîì, äîñòà-
òî÷íî ïîñìîòðåòü íà òðàåêòîðèþ ÷èñëà 27, ïðèâåäåííóþ â [2]. Òàêèì îáðàçîì,
ôóíêöèÿ Êîëëàòöà ïîêàçûâàåò, íàñêîëüêî òðóäíîé ìîæåò îêàçàòüñÿ ïðîáëåìà
äîñòèæèìîñòè ñîñòîÿíèé â îäíîìåðíûõ àôôèííûõ àâòîìàòàõ.
ÏÐÅÄÂÀÐÈÒÅËÜÍÛÅ ÑÂÅÄÅÍÈß
Ôóíêöèÿ Êîëëàòöà èìååò ðÿä ïîëåçíûõ ìîäèôèêàöèé. Îòìåòèì, ÷òî ïðè íå-
÷åòíîì n ÷èñëî 3 1n � áóäåò ÷åòíûì, ïîýòîìó ïðîöåññ «ñõîäèìîñòè» ìîæíî íå-
ñêîëüêî óñêîðèòü çà ñ÷åò ñëåäóþùåé ôóíêöèè:
32 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
— ÷åòíîå,
— íå÷åòíîå.
© È.Ê. Ðûñöîâ, 2013
D n
n n
n n
( )
/ ,
( ) / ,
�
�
�
�
�
2
3 1 2
(2)
Èìåííî ýòó ôîðìó èññëåäîâàë Ä. Ëàãàðèàñ â ðàáîòàõ [1, 4, 5].
Ôóíêöèè Ñ n( ) è D n( ) òåñíî ñâÿçàíû, ïîýòîìó ãèïîòåçà Êîëëàòöà ñïðàâåäëèâà
äëÿ îáåèõ. Òðàåêòîðèÿ ( , ( )n D n , D n( ) ( )2 , …) ïîëó÷àåòñÿ èç òðàåêòîðèè äëÿ ôóíê-
öèè C n( ) óäàëåíèåì íåêîòîðûõ ÷åòíûõ ÷èñåë, à èìåííî òåõ, êîòîðûå ïîëó÷àþòñÿ
ñðàçó ïîñëå óìíîæåíèÿ íà òðè è ïðèáàâëåíèÿ åäèíèöû (íå÷åòíûå îïåðàöèè).
Ñ ôóíêöèåé D n( ) ìîæíî ñâÿçàòü áåñêîíå÷íûé ôóíêöèîíàëüíûé îðãðàô
G N DD � ( , ) , ñîåäèíèâ äóãîé ÷èñëî n ñ ÷èñëîì D n( ), ãäå N — ìíîæåñòâî íàòó-
ðàëüíûõ ÷èñåë. Ïîñêîëüêó îðãðàô ôóíêöèîíàëüíûé [6], èç êàæäîé åãî âåðøèíû
áóäåò âûõîäèòü îäíà äóãà, è â êàæäóþ åãî âåðøèíó áóäåò âõîäèòü îäíà, íî íå
áîëåå äâóõ äóã.  ýòîì ìîæíî óáåäèòüñÿ, âû÷èñëèâ ïðîîáðàçû ôóíêöèè D n( ):
D n
n n n
n
�
��
�
�
1 2 1 3 2 2 3
2
( )
{( ) / , }, ( ),
{ }
åñëè mod
Çäåñü a b m� ( )mod îáîçíà÷åíî ñðàâíåíèå öåëûõ ÷èñåë ïî ìîäóëþ m.
Ñîãëàñíî ãèïîòåçå Êîëëàòöà èç ëþáîé âåðøèíû îðãðàôà GD äîñòèãàåòñÿ
åäèíèöà, ò.å. îðãðàô GD äîëæåí èìåòü ñòðóêòóðó âõîäÿùåãî îðèåíòèðîâàííîãî
äåðåâà [6], åñëè åãî êîðíåì ñ÷èòàòü òðèâèàëüíûé öèêë (1, 2). Àíàëîãè÷íóþ
ñòðóêòóðó áóäåò èìåòü îðãðàô äëÿ ôóíêöèè C n( ). Ýòî ïîçâîëÿåò ñôîðìóëèðîâàòü
«ãðàôè÷åñêóþ» ôîðìó ïðîáëåìû.
Ïðîáëåìà Êîëëàòöà (ôîðìà 2). Ãðàô ôóíêöèè D n( ) ÿâëÿåòñÿ âõîäÿùèì
îðèåíòèðîâàííûì äåðåâîì, â êîðíå êîòîðîãî íàõîäèòñÿ òðèâèàëüíûé öèêë.
 ñâÿçè ñ îðãðàôîì GD âîçíèêàåò åùå îäíî óòâåðæäåíèå, ýêâèâàëåíòíîå ãè-
ïîòåçå Êîëëàòöà: ïðåäïîëîæèì, ÷òî ïîäìíîæåñòâî íàòóðàëüíûõ ÷èñåë M ñîäåð-
æèò åäèíèöó è çàìêíóòî îòíîñèòåëüíî óìíîæåíèÿ íà äâà, êðîìå òîãî, âìåñòå
ñ ëþáûì ÷èñëîì âèäà 3 2n � îíî ñîäåðæèò ÷èñëî 2 1n � , òîãäà M äîëæíî ñîäåð-
æàòü âñå íàòóðàëüíûå ÷èñëà. Ýòî óòâåðæäåíèå ñïðàâåäëèâî, åñëè ïî äóãàì îðãðà-
ôà GD äâèãàòüñÿ â ïðîòèâîïîëîæíîì íàïðàâëåíèè.
Ìîæíî è äàëüøå óñêîðÿòü ïðîöåññ ñõîäèìîñòè, åñëè ÷èñëî 3 1n � ñðàçó äå-
ëèòü íà ìàêñèìàëüíî âîçìîæíóþ ñòåïåíü äâîéêè. Îáîçíà÷èì ord 2 ( )n êðàòíîñòü
äâîéêè â ðàçëîæåíèè íàòóðàëüíîãî ÷èñëà n íà ïðîñòûå ìíîæèòåëè, ò.å. 2 2ord ( )n
áóäåò íàèáîëüøåé ñòåïåíüþ äâîéêè, êîòîðàÿ äåëèò ÷èñëî n . Ôóíêöèÿ ord 2 ( )n
íàïîìèíàåò ëîãàðèôì, ïîñêîëüêó ord ord ord2 2 2( ) ( ) ( )mn m n� � . Ïîëîæèì
e n
n
�( )
( )� 2 2ord
è íàçîâåì ýòó ñòåïåíü ÷åòíîé ÷àñòüþ ÷èñëà n . Îñòàëüíûå ñîìíî-
æèòåëè â ðàçëîæåíèè îòíåñåì ê íå÷åòíîé ÷àñòè ÷èñëà n, êîòîðóþ îáîçíà÷èì
od n( ) . Îòìåòèì, ÷òî od n( ) áóäåò íàèáîëüøèì íå÷åòíûì äåëèòåëåì ÷èñëà n . Òà-
êèì îáðàçîì, äëÿ êàæäîãî íàòóðàëüíîãî ÷èñëà n èìååò ìåñòî ðàçëîæåíèå
n e n od n od n
n� � � ��( ) ( ) ( )
( )
2 2ord
. (3)
Îáîçíà÷èì N 0 , N1 ìíîæåñòâà ÷åòíûõ è íå÷åòíûõ íàòóðàëüíûõ ÷èñåë ñîîòâåò-
ñòâåííî. Ðàññìîòðèì ôóíêöèþ E N N: 1 1� , îïðåäåëåííóþ ñëåäóþùèì îáðàçîì:
E n od n n N( ) ( ),� �
3 1 1. (4)
Äðóãèìè ñëîâàìè, çäåñü ÷èñëî 3 1n � äåëèì ñðàçó íà ìàêñèìàëüíî âîçìîæíóþ
ñòåïåíü äâîéêè è â ðåçóëüòàòå èìååì íå÷åòíîå ÷èñëî. Òðàåêòîðèþ ôóíêöèè
E n( ) äëÿ çàäàííîãî ÷èñëà n ïîëó÷àåì èç ñîîòâåòñòâóþùåé òðàåêòîðèè ôóíê-
öèè Ñ n( ) óäàëåíèåì âñåõ ÷åòíûõ ÷èñåë.  ýòîì ñëó÷àå åäèíèöà ñòàíîâèòñÿ íå-
ïîäâèæíîé òî÷êîé ôóíêöèè E n( ). Íåòðóäíî ïîêàçàòü, ÷òî ýòà ôóíêöèÿ íå
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 33
— ÷åòíîå,
— íå÷åòíîå.
â ïðîòèâíîì ñëó÷àå.
èìååò äðóãèõ íåïîäâèæíûõ òî÷åê ñðåäè íàòóðàëüíûõ ÷èñåë. Íî äëÿ äîêàçà-
òåëüñòâà ãèïîòåçû Êîëëàòöà íåîáõîäèìî, ÷òîáû è ñóïåðïîçèöèÿ ôóíêöèè E n( )
ëþáîé ñòåïåíè èìåëà îäíó íåïîäâèæíóþ òî÷êó.
Ñ ôóíêöèåé E n( ) òàêæå ìîæíî ñâÿçàòü ôóíêöèîíàëüíûé îðãðàô
G N EE � ( , )1 , ñîåäèíèâ äóãîé íå÷åòíîå ÷èñëî n ñ ÷èñëîì E n( ) . Èç ãèïîòåçû
Êîëëàòöà ñëåäóåò, ÷òî îðãðàô GE äîëæåí èìåòü ñòðóêòóðó äåðåâà ñ ïåòëåé, åñëè
åãî êîðíåì ñ÷èòàòü åäèíèöó.
Îäíàêî ñòðóêòóðà îðãðàôà GE ñóùåñòâåííî ñëîæíåå ïî ñðàâíåíèþ ñ îðãðà-
ôîì GD . Â êàæäóþ âåðøèíó îðãðàôà GE äóãè ëèáî âîîáùå íå âõîäÿò, ëèáî âõî-
äèò áåñêîíå÷íîå ÷èñëî äóã.  ýòîì ìîæíî óáåäèòüñÿ, âû÷èñëèâ ïðîîáðàçû
ôóíêöèè E n( ) :
E n
n
n m nm
�
� �
� �
�
1
0 3
4 1 3 1 1 3
2 4
( )
, (mod ),
( ) / | , (mod ),
(
{ }
{ m n m n
� �
�
�
�
�
� 1 1 3 1 2 3) / | , (mod ).}
(5)
Äëÿ äîêàçàòåëüñòâà ôîðìóëû (5) îòìåòèì, ÷òî âñå ïðîîáðàçû ÷èñëà n ïðèíàä-
ëåæàò ìíîæåñòâó ðàöèîíàëüíûõ ÷èñåë { }( ) / |2 1 3 1m n m
� . Â çàâèñèìîñòè îò
îñòàòêà ïðè äåëåíèè n íà òðè â ýòîì ìíîæåñòâå ìîæíî âûäåëèòü ïîäìíîæåñ-
òâà íàòóðàëüíûõ ÷èñåë, ÷òî è ñäåëàíî â (5).
Ëþáîå íå÷åòíîå ÷èñëî èìååò âèä 4 1n � èëè 4 1n
. Íåòðóäíî âèäåòü, ÷òî
ôóíêöèÿ E n( ) óáûâàåò íà íå÷åòíûõ ÷èñëàõ ïåðâîãî òèïà è âîçðàñòàåò íà íå÷åò-
íûõ ÷èñëàõ âòîðîãî òèïà:
E n n E n n( ) , ( )4 1 4 1 4 1 4 1� � �
�
. (6)
Äåéñòâèòåëüíî, E n od n od n n( ) ( ) ( )4 1 12 4 3 1 4 1� � � � � � � è E n od n( ) ( )4 1 12 2
�
�
�
�
6 1 4 1n n . Êðîìå òîãî, èç (5) âèäíî, ÷òî ó êàæäîãî íàòóðàëüíîãî ÷èñëà
áóäåò áåñêîíå÷íîå ÷èñëî ïðîîáðàçîâ ïåðâîãî òèïà è íå áîëåå îäíîãî ïðîîáðà-
çà âòîðîãî òèïà.
Îòìåòèì, ÷òî â (4) â îòëè÷èå îò (2) óæå íåò ðàçâåòâëåíèÿ íà äâà íàïðàâëåíèÿ
çà ñ÷åò ïîÿâëåíèÿ íîâîé ôóíêöèè od n( ) . Íî ââèäó íåðåãóëÿðíîñòè ýòîé ôóíêöèè
åå òðóäíî èññëåäîâàòü àíàëèòè÷åñêè, ïîýòîìó ôóíêöèÿ E n( ) ðåäêî âñòðå÷àåòñÿ
â ëèòåðàòóðå.
Îñíîâíàÿ òðóäíîñòü â ïðîáëåìå Êîëëàòöà ñîñòîèò â îòñóòñòâèè àïðèîðíîé
îöåíêè ÷èñëà íåîáõîäèìûõ èòåðàöèé, ïîýòîìó óìåñòíûìè ÿâëÿþòñÿ ñëåäóþùèå
îïðåäåëåíèÿ. Ïóñòü T — îäíà èç ôóíêöèé C D, èëè E , òîãäà äëÿ çàäàííîãî ÷èñëà
n âîçìîæíû òðè òèïà òðàåêòîðèé:
— ñõîäÿùàÿñÿ (ñóùåñòâóåò k òàêîå, ÷òî T nk( ) ( ) �1);
— íåòðèâèàëüíûé öèêë (òðàåêòîðèÿ T nk( ) ( ) ñòàíîâèòñÿ ïåðèîäè÷åñêîé,
ïðè÷åì T nk( ) ( ) �1 äëÿ âñåõ k);
— ðàñõîäÿùàÿñÿ ( lim ( )( )
k
kT n
��
� �).
Ãèïîòåçà Êîëëàòöà óòâåðæäàåò, ÷òî ó íàòóðàëüíûõ ÷èñåë âñå òðàåêòîðèè ñõîäÿ-
ùèåñÿ. Ïîëîæèì �T
kn k T n( ) min | ( )( )� �{ }1 , åñëè òðàåêòîðèÿ äëÿ ÷èñëà n ñõîäÿ-
ùàÿñÿ, è �T n( ) � � â ïðîòèâíîì ñëó÷àå. Ôóíêöèÿ �T n( ) íàçûâàåòñÿ ïîëíûì âðåìå-
íåì îñòàíîâêè äëÿ ÷èñëà n , åå òàêæå ìîæíî íàçâàòü âûñîòîé ÷èñëà n , îäíàêî âûñî-
òîé èíîãäà íàçûâàþò ìàêñèìàëüíîå ÷èñëî, êîòîðîå âñòðå÷àåòñÿ íà òðàåêòîðèè [2].
Îòìåòèì, ÷òî äëÿ n �1 óñëîâèå T nk( ) ( ) �1 âëå÷åò óñëîâèå T n nk( ) ( )� . Ïîýòî-
ìó âðåìåíåì îñòàíîâêè äëÿ ÷èñëà n �1 íàçûâàþò ôóíêöèþ �T n( ) �
� �min | ( )( ){ }k T n nk è �T n( ) � � , åñëè òàêîãî k íå ñóùåñòâóåò. Äðóãèìè ñëîâà-
ìè, åñëè âåðíóòüñÿ ê ÷èñëó, ìåíüøåìó ÷åì n , òî îñòàíîâêó ïðîöåññà ãàðàíòèðóåò
34 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
èíäóêöèÿ. Ïîýòîìó ãèïîòåçà Êîëëàòöà óòâåðæäàåò, ÷òî ëþáîå íàòóðàëüíîå ÷èñëî
èìååò êîíå÷íîå âðåìÿ îñòàíîâêè.
Ââåäåííûå ôóíêöèè ïðèíèìàþò áîëüøèå çíà÷åíèÿ äàæå äëÿ íåáîëüøèõ çíà-
÷åíèé n . Íàïðèìåð, äëÿ ôóíêöèè C èìååì �Ñ ( )27 96� , �C ( )27 111� , è ìàêñè-
ìàëüíûì íà òðàåêòîðèè ÷èñëà 27 ÿâëÿåòñÿ ÷èñëî 9232.
ÀÂÒÎÌÀÒ ÊÎËËÀÒÖÀ
Ïðîìîäåëèðóåì ôóíêöèþ D n( ) c ïîìîùüþ àâòîìàòà. Îïðåäåëèì àôôèííûé
àâòîìàò A Q f1 0 1� ( , , , ){ } íà ìíîæåñòâå ðàöèîíàëüíûõ ÷èñåë Q, ïîëîæèâ
f q q( , ) /0 2� , f q q( , ) / /1 3 2 1 2� � . Îáúåäèíèì ýòè ðàâåíñòâà â îäíî
f q x q xx( , ) / /� �3 2 2 , (7)
ãäå q Q
è x
{ }0 1, . Òàêèì îáðàçîì, ïîëó÷åí îäíîìåðíûé àôôèííûé àâòî-
ìàò [7]. Ïîñêîëüêó îáå ôóíêöèè: f q q0 2( ) /� è f q q1 3 1 2( ) ( ) /� � , ÿâëÿþòñÿ
áèåêöèÿìè íà Q, àâòîìàò áóäåò ãðóïïîâûì, ò.å. åãî ïîëóãðóïïà ïðåîáðàçîâà-
íèé â ýòîì ñëó÷àå ÿâëÿåòñÿ ãðóïïîé áèåêöèé íà ìíîæåñòâå Q. Ýòî îçíà÷àåò,
÷òî ïîä äåéñòâèåì ëþáîãî âõîäíîãî ñëîâà êàæäîå ñîñòîÿíèå áóäåò èìåòü åäèí-
ñòâåííîãî ïðåäøåñòâåííèêà.  ÷àñòíîñòè, ïîä äåéñòâèåì âõîäíîãî ñëîâà â åäèíè-
öó ïåðåéäåò òîëüêî îäíî ñîñòîÿíèå.
 àôôèííîì àâòîìàòå âõîäíîå ñëîâî w x x x k� ( ) ( ) ( )1 2 � äåéñòâóåò íà ñî-
ñòîÿíèå q ñëåäóþùèì îáðàçîì: f q w q a w b w( , ) ( ) ( )� � � , ãäå êîýôôèöèåíòû a w( )
è b w( ) îïðåäåëÿþòñÿ â äàííîì ñëó÷àå ðàâåíñòâàìè:
a w
x x x k
k
( )
( ) ( ) ( )
�
� � �3
2
1 2 �
, b w x i
x i x k
k i
i
k
( ) ( )
( ) ( )
�
� � �
�
�
�
3
2
1
1
1
�
. (8)
Ýòè âûðàæåíèÿ ïîëó÷àþòñÿ ïîñëåäîâàòåëüíûì ïðèìåíåíèåì ôóíêöèè ïåðåõî-
äîâ (7) ê ñèìâîëàì x i( ) âõîäíîãî ñëîâà w. Ïîñêîëüêó àâòîìàò A1 ãðóïïîâîé,
a w( ) � 0 äëÿ âñåõ âõîäíûõ ñëîâ w.
Òàêèì îáðàçîì, ïîä äåéñòâèåì âõîäíîãî ñëîâà w x x x k� ( ) ( ) ( )1 2 � â åäèíèöó
ïåðåéäåò åäèíñòâåííîå ñîñòîÿíèå f w b w a w
�
1 1 1( , ) ( ( )) / ( ). Ïîäñòàâèâ ñþäà
âûðàæåíèÿ äëÿ êîýôôèöèåíòîâ (8), ïîëó÷èì
f w x i
x x x k
k i
i
k
x i
� � �
�
��
�1
1 2
1
1
11
1
3
2 2 3( , ) ( )
( ) ( ) ( )
( )
�
� ��
�
�
�
�
�
�
�
� x k( ) . (9)
Òðóäíî ïðåäñòàâèòü, ÷òî ýòî âûðàæåíèå ìîæåò ïðèíèìàòü ëþáûå íàòóðàëü-
íûå çíà÷åíèÿ ïðè íåêîòîðûõ çíà÷åíèÿõ äâîè÷íûõ ïàðàìåòðîâ, íî èìåííî ýòîò
ôàêò ñëåäóåò èç ãèïîòåçû Êîëëàòöà. Îáîçíà÷èì � : , *{ }0 1 � Q ôóíêöèþ, êîòîðàÿ
âõîäíîìó ñëîâó w ñòàâèò â ñîîòâåòñòâèå ñîñòîÿíèå f w
1 1( , ) , îïèñûâàåìîå (9).
Òîãäà èç ãèïîòåçû Êîëëàòöà ñëåäóåò âêëþ÷åíèå N � Im ( )� , ãäå N — ìíîæåñò-
âî íàòóðàëüíûõ ÷èñåë.
Íî âåðíî è îáðàòíîå. Ïóñòü äëÿ íàòóðàëüíîãî ÷èñëà n ñóùåñòâóåò ñëîâî
w x x x k� ( ) ( ) ( )1 2 � òàêîå, ÷òî f n w( , ) �1. Ïîëîæèì n n� ( )0 è n i f n i x i( ) ( ( ), ( ))�
1 ,
1 � �i k . Òîãäà ñëîâî w x x x k� ( ) ( ) ( )1 2 � äîëæíî óäîâëåòâîðÿòü ñëåäóþùåìó
óñëîâèþ:
n i x i( ) ( ) ( )
�1 2mod , 1 � �i k . (10)
Äåéñòâèòåëüíî, ëþáîå îòêëîíåíèå îò ýòîãî óñëîâèÿ ïðèâîäèò ê òóïèêîâîé ñèòóàöèè.
Åñëè â íå÷åòíîì ñîñòîÿíèè ïîÿâèòñÿ íóëü èëè â ÷åòíîì — åäèíèöà, òî ïîëó÷èì ñî-
ñòîÿíèå âèäà ( ) /2 1 2n m� , ãäå m � 1. Íî òàêèå ñîñòîÿíèÿ îáðàçóþò çàìêíóòûé ïîä-
àâòîìàò îòíîñèòåëüíî ôóíêöèé f 0 , f1 è, ñëåäîâàòåëüíî, èç íèõ íåäîñòèæèìî åäè-
íè÷íîå ñîñòîÿíèå. Çíà÷èò, íàòóðàëüíàÿ òðàåêòîðèÿ n n k( ), , ( )1 � àâòîìàòà A1 îä-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 35
íîçíà÷íî îïðåäåëÿåòñÿ íà÷àëüíûì ñîñòîÿíèåì n n� ( )0 è äîëæíà ñîâïàäàòü
ñ òðàåêòîðèåé ôóíêöèè D ni( ) ( ) , 1 � �i k . Òàêèì îáðàçîì, ïðèõîäèì ê ñëåäóþ-
ùåìó óòâåðæäåíèþ.
Ïðîáëåìà Êîëëàòöà (ôîðìà 3). Ëþáîå íàòóðàëüíîå ÷èñëî n ìîæíî ïðåä-
ñòàâèòü â ôîðìå (9) ïðè íåêîòîðûõ çíà÷åíèÿõ äâîè÷íûõ ïàðàìåòðîâ x i( ) .
 íåÿâíîì âèäå àâòîìàò A1 è ôóíêöèþ � èñïîëüçîâàë Ð. Òåððàñ ïðè èññëå-
äîâàíèè âðåìåíè îñòàíîâêè äëÿ ôóíêöèè Êîëëàòöà [8]. Êðîìå òîãî, îí ðàññìîò-
ðåë ñåìåéñòâî îáðàòíûõ ôóíêöèé � k
kN: ,� { }0 1 , êîòîðûå íàòóðàëüíîìó ÷èñëó
n ñòàâÿò â ñîîòâåòñòâèå äîïóñòèìîå ñëîâî w x x x k� ( ) ( ) ( )1 2 � äëèíû k , ò.å. ñëî-
âî, óäîâëåòâîðÿþùåå óñëîâèþ (10). Èíà÷å ãîâîðÿ, ñëîâî w áóäåò äîïóñòèìûì
äëÿ ñîñòîÿíèÿ n , åñëè ïîä äåéñòâèåì ýòîãî ñëîâà òðàåêòîðèÿ àâòîìàòà, êîòîðàÿ
íà÷èíàåòñÿ â ñîñòîÿíèè n , îñòàåòñÿ âñå âðåìÿ â îáëàñòè íàòóðàëüíûõ ÷èñåë. Êàê
óæå îòìå÷àëîñü, åñëè ñëîâî w äëèíû k ÿâëÿåòñÿ äîïóñòèìûì äëÿ ñîñòîÿíèÿ n , òî
âûïîëíÿþòñÿ ñëåäóþùèå ðàâåíñòâà:
f n w f n n n a n b n D nk k k
k( , ) ( , ( )) ( ( )) ( ( )) ( )( )� � � � �� � � . (11)
 ñâÿçè ñ ýòèì Ð. Òåððàñ îáðàòèë âíèìàíèå íà âàæíîñòü ìîìåíòà, êîãäà ñòå-
ïåíü äâîéêè âïåðâûå íà÷èíàåò îáãîíÿòü ñòåïåíü òðîéêè
3 21 2x x x k k( ) ( ) ( )� � � �� . (12)
Î÷åâèäíî, ÷òî ýòî íåðàâåíñòâî áóäåò âûïîëíÿòüñÿ, êîãäà â äîïóñòèìîì ñëîâå
íàêîïèòñÿ äîñòàòî÷íîå ÷èñëî íóëåé, ïîñêîëüêó êàæäûé íóëü âäâîå óâåëè÷èâà-
åò ïðàâóþ ÷àñòü íåðàâåíñòâà è íå èçìåíÿåò ëåâóþ. Èç (8) âèäíî, ÷òî íåðàâåí-
ñòâî (12) ýêâèâàëåíòíî óñëîâèþ a w( )� 1.
Ð. Òåððàñ íàçâàë êîýôôèöèåíòíûì âðåìåíåì îñòàíîâêè äëÿ ÷èñëà n �1 ôóíê-
öèþ � �( ) min | ( ( ))n k a n
k
� �{ }1 è �( )n � � , åñëè òàêîãî k íå ñóùåñòâóåò. Èç
(11) ñëåäóåò, ÷òî åñëè D n nk( ) ( )� , òî a nk( ( ))� � 1, ïîñêîëüêó b nk( ( ))� � 0. Çíà-
÷èò, � �( ) ( )n nD� , íî èç óñëîâèÿ a nk( ( ))� � 1 íå ñëåäóåò, ÷òî D n nk( ) ( )� , ïî-
ñêîëüêó èìååòñÿ äîïîëíèòåëüíûé êîýôôèöèåíò b nk( ( ))� . Îäíàêî Ð. Òåððàñ
ïðåäïîëîæèë, ÷òî ýòè ôóíêöèè ñîâïàäàþò [7].
Ãèïîòåçà î êîýôôèöèåíòíîì âðåìåíè îñòàíîâêè. Äëÿ ëþáîãî íàòóðàëüíî-
ãî ÷èñëà n �1 âûïîëíÿåòñÿ ðàâåíñòâî � �( ) ( )n nD� .
Ýòî ñèëüíàÿ ãèïîòåçà, íî âñå ÷èñëåííûå ýêñïåðèìåíòû åå ïîêà ïîäòâåðæäà-
þò.  ÷àñòíîñòè, ñîãëàñíî ýòîé ãèïîòåçå íåâîçìîæíî ñóùåñòâîâàíèå íåòðèâèàëü-
íûõ öèêëîâ â ôóíêöèè D n( ), à çíà÷èò, è âî âñåõ ôîðìàõ ôóíêöèè Êîëëàòöà [1].
Ðàâåíñòâà (8) ïîêàçûâàþò, ÷òî â àâòîìàòå A1 êîýôôèöèåíòû a w( ) è b w( )
ñëîæíî çàâèñÿò îò äâîè÷íîãî ñëîâà w. Îêàçûâàåòñÿ, ýòè âûðàæåíèÿ ìîæíî
óïðîñòèòü, íî äëÿ ýòîãî íóæíî èçìåíèòü ôóíêöèþ Êîëëàòöà.
ÌÎÄÈÔÈÖÈÐÎÂÀÍÍÀß ÔÓÍÊÖÈß ÊÎËËÀÒÖÀ
Ðàññìîòðèì ñëåäóþùóþ ôóíêöèþ, îïðåäåëåííóþ íà íàòóðàëüíûõ ÷èñëàõ:
F n n n
n n
( ) ( ( ) )
( ) ( )� � � � �3 2 2 3 12 2ord ord
od . (13)
Ýòà ôîðìà ôóíêöèè Êîëëàòöà, ïî-âèäèìîìó, åùå íå ðàññìàòðèâàëàñü. Äëÿ åå
âû÷èñëåíèÿ íåîáõîäèìî ðàçëîæèòü íàòóðàëüíîå ÷èñëî íà ÷åòíóþ è íå÷åòíóþ
÷àñòè, êàê óêàçàíî â (3). Ýòà ôîðìà ïîäîáíà ôóíêöèè E n( ). Îäíàêî çäåñü ÷åò-
íàÿ ÷àñòü ÿâëÿåòñÿ àääèòèâíûì ñëàãàåìûì è ïîýòîìó ìîíîòîííî óâåëè÷è-
âàåòñÿ ïî ìåðå âûïîëíåíèÿ èòåðàöèé. ×òîáû ñäåëàòü ñâÿçü ñ ôóíêöèåé E n( )
áîëåå ÿâíîé, äîêàæåì èíäóêöèåé ïî k , ÷òî äëÿ ëþáîãî íå÷åòíîãî ÷èñëà n âû-
ïîëíÿåòñÿ ðàâåíñòâî
od F n E nk k( ( )) ( )( ) ( )� . (14)
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
Äåéñòâèòåëüíî, ïðè k �1 èìååì od F n od n E n( ( )) ( ) ( )� � �3 1 . Îáîçíà÷èì mk
÷èñëî F nk( ) ( ), à nk ÷èñëî E nk( ) ( ), òîãäà ïî ïðåäïîëîæåíèþ èíäóêöèè èìååì
od m nk k( ) � . Äàëåå âûïîëíèì åùå îäíó èòåðàöèþ, òîãäà èç (4) è (13) ïîëó÷èì
od F m od e m od m od n E nk k k k k( ( )) ( ( )( ( ) )) ( ) ( )� � � � �� 3 1 3 1 .
Òàêèì îáðàçîì, ñâîéñòâî (14) äîêàçàíî è, ñëåäîâàòåëüíî, ãèïîòåçà Êîëëàòöà
ýêâèâàëåíòíà ñëåäóþùåìó óòâåðæäåíèþ.
Ïðîáëåìà Êîëëàòöà (ôîðìà 4). Äëÿ âñÿêîãî íàòóðàëüíîãî ÷èñëà n ñóùåñò-
âóåò íàòóðàëüíîå ÷èñëî k òàêîå, ÷òî od F nk( ( ))( ) �1.
Ñîîòâåòñòâåííî ïîëíûì âðåìåíåì îñòàíîâêè äëÿ ôóíêöèè F n( ) íàçîâåì
ôóíêöèþ �F
kn k od F n( ) min | ( ( ))( )� �{ }1 , åñëè òàêîå k ñóùåñòâóåò, è �F n( ) � �
â ïðîòèâíîì ñëó÷àå. Åñëè F nk m( ) ( ) � 2 è k nF� � ( ) , òî ÷èñëî m óêàçûâàåò íà êî-
ëè÷åñòâî äåëåíèé íà äâà (÷åòíûå îïåðàöèè), êîòîðûå íàäî âûïîëíèòü ïðè èòåðà-
öèÿõ ôóíêöèè C n( ) , ÷òîáû äîñòè÷ü åäèíèöû. Çíà÷èò, â ýòîì ñëó÷àå
� �C Fn n m( ) ( )� � . Êðîìå òîãî, èç ñâîéñòâà (14) ñëåäóåò, ÷òî � �E Fn n( ) ( )� . Íàï-
ðèìåð, � �E F( ) ( )27 27 41� � , F ( ) ( )41 7027 2� è � �C F( ) ( )27 27 70 111� � � .
Ïåðåéäåì òåïåðü ê ðàññìîòðåíèþ ñâîéñòâ ôóíêöèè F n( ) . Îòìåòèì, ÷òî
e n e n� �( ) ( )2 2� , è çíà÷èò F n n e n F n( ) ( ) ( )2 3 2 2 2� � � � � �� . Äàëåå, ïðèìåíÿÿ èí-
äóêöèþ ïî m , ïîëó÷àåì ñëåäóþùóþ ôîðìóëó:
F n F nm m( ) ( )2 2� � (15)
äëÿ âñåõ m � 1.
Íàçîâåì íàòóðàëüíûå ÷èñëà m è n ýêâèâàëåíòíûìè, åñëè od m od n( ) ( )� , ò.å.
åñëè îíè îòëè÷àþòñÿ ëèøü ñòåïåíüþ äâîéêè. Î÷åâèäíî, ÷òî â êàæäîì êëàññå ýê-
âèâàëåíòíîñòè íàõîäèòñÿ òî÷íî îäíî íå÷åòíîå ÷èñëî, êîòîðîå áóäåì ñ÷èòàòü
ïðåäñòàâèòåëåì ýòîãî êëàññà. Îáîçíà÷èì P j j ii( ) ( ) |2 1 2 2 1 11
�
�
{ } êëàññ ñ íå-
÷åòíûì ïðåäñòàâèòåëåì 2 1j
.  ÷àñòíîñòè, ïåðâûé êëàññ P ( )1 áóäåò ñîäåðæàòü
âñå ñòåïåíè äâîéêè. Ñîãëàñíî ãèïîòåçå Êîëëàòöà äëÿ ëþáîãî n ðàíî èëè ïîçäíî
òðàåêòîðèÿ ôóíêöèè F n( ) ïîïàäåò â ïåðâûé êëàññ.
Ðàñïîëîæèì âñå íàòóðàëüíûå ÷èñëà â âèäå áåñêîíå÷íîé äâóõìåðíîé òàáëè-
öû S , â êîòîðîé ñòîëáöàìè ÿâëÿþòñÿ êëàññû ýêâèâàëåíòíîñòè
s i j ji( , ) ( )�
2 2 11 (16)
äëÿ âñåõ i j� �1 1, . Ñòðîêàìè ýòîé òàáëèöû áóäóò àðèôìåòè÷åñêèå ïðîãðåñ-
ñèè ñî ñòåïåíÿìè äâîéêè â êà÷åñòâå ðàçíîñòåé. Ñâîéñòâî (15) ïîêàçûâàåò, ÷òî
ôóíêöèÿ F n( ) ñîõðàíÿåò îòíîøåíèå ýêâèâàëåíòíîñòè è îòîáðàæàåò êàæäûé
ñòîëáåö ýòîé òàáëèöû âíóòðü äðóãîãî ñòîëáöà.
Îòìåòèì, ÷òî åñëè èç êàæäîãî ýëåìåíòà òàáëèöû S âû÷åñòü åäèíèöó è îò-
áðîñèòü ïåðâóþ ñòðîêó, êîòîðàÿ áóäåò ñîñòîÿòü èç ÷åòíûõ ÷èñåë, òî ïîëó÷èòñÿ
òàáëèöà èç [9], îáëàäàþùàÿ ìíîãèìè èíòåðåñíûìè ñâîéñòâàìè.
ÐÀÖÈÎÍÀËÜÍÛÅ ×ÈÑËÀ
Ðàñïðîñòðàíèì ôóíêöèþ F íà ðàöèîíàëüíûå ÷èñëà, ó÷èòûâàÿ, ÷òî ïðè òàêîì
ðàñøèðåíèè â ôóíêöèè Êîëëàòöà ïîÿâèòñÿ áåñêîíå÷íîå ìíîæåñòâî íåòðèâè-
àëüíûõ öèêëîâ [2].
Äëÿ íåíóëåâîãî öåëîãî ÷èñëà m ÷åòíàÿ ÷àñòü e m�( ) ðàâíà 2 2ord ( )m
, ò.å. ñòåïå-
íè äâîéêè â ðàçëîæåíèè ÷èñëà m íà ïðîñòûå ìíîæèòåëè. Íåáîëüøàÿ ñëîæíîñòü
âîçíèêàåò â íóëå, ïîñêîëüêó ord 2 0( ) � � , òåì íå ìåíåå, áóäåì ñ÷èòàòü, ÷òî è ÷åò-
íàÿ, è íå÷åòíàÿ ÷àñòè íóëÿ ðàâíû íóëþ e od�( ) ( )0 0 0� � . Äëÿ íåíóëåâîãî ðàöèî-
íàëüíîãî ÷èñëà q m n� / ïîëîæèì ord ord ord2 2 2( ) ( ) ( )q m n�
, e q
q
�( )
( )� 2 2ord
,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 37
od q od m od n( ) ( ) / ( )� . Îòìåòèì, ÷òî ÷èñëà ord 2 ( )q è od q( ) íå çàâèñÿò îò ïðåä-
ñòàâëåíèÿ ÷èñëà q â âèäå äðîáè. Òàêèì îáðàçîì, ðàâåíñòâî (3) íåïîñðåäñòâåííî
îáîáùàåòñÿ íà íåíóëåâûå ðàöèîíàëüíûå ÷èñëà
q e q od q od q
q� � � ��( ) ( ) ( )
( )
2 2ord
. (17)
Íàêîíåö, äëÿ íåíóëåâîãî ðàöèîíàëüíîãî ÷èñëà q ïîëîæèì
F q q od q
q q
( ) ( ( ) )
( ) ( )� � � � �3 2 2 3 12 2ord ord
. (18)
Êðîìå òîãî, áóäåì ñ÷èòàòü, ÷òî F ( )0 0� . Èç ýòîãî îïðåäåëåíèÿ äëÿ íåíóëåâî-
ãî ðàöèîíàëüíîãî ÷èñëà q m n� / ñëåäóåò íåðàâåíñòâî
ord ord2 2( ) ( ( ))q F q� , (19)
ïîñêîëüêó 3 1 3� � � � �od q od m od n od n( ) ( ( ) ( )) / ( ) , à ñóììà (èëè ðàçíîñòü) äâóõ
íå÷åòíûõ ÷èñåë ÿâëÿåòñÿ ÷åòíûì ÷èñëîì. Êðîìå òîãî, äëÿ ïîëîæèòåëüíûõ ðà-
öèîíàëüíûõ ÷èñåë q � 0 è, â ÷àñòíîñòè, äëÿ íàòóðàëüíûõ ÷èñåë âûïîëíÿåòñÿ
ñëåäóþùåå íåðàâåíñòâî:
q F q� ( ) . (20)
Ðàññìîòðèì ìíîæåñòâî ðàöèîíàëüíûõ ÷èñåë Q q q2 2 0� �{ ord }| ( ) , êîòîðûå
ïðåäñòàâëÿþòñÿ â âèäå íåñîêðàòèìîé äðîáè ñ íå÷åòíûì çíàìåíàòåëåì.  äàëü-
íåéøåì îãðàíè÷èìñÿ ðàöèîíàëüíûìè ÷èñëàìè èç Q2 , ïîñêîëüêó ýòî ïîçâîëèò
ðàáîòàòü ñ íåîòðèöàòåëüíûìè ýêñïîíåíòàìè.
Îïðåäåëèì àâòîìàò A Q Z f2 2� �( , , ) ñ ïîäìíîæåñòâîì ðàöèîíàëüíûõ ÷èñåë
Q2 â êà÷åñòâå ñîñòîÿíèé è ñ ìíîæåñòâîì íåîòðèöàòåëüíûõ öåëûõ ÷èñåë Z � â êà-
÷åñòâå âõîäîâ. Ôóíêöèþ ïåðåõîäîâ f q x( , ) â ñîîòâåòñòâèè ñ (17) è (18) íàõîäèì
ñëåäóþùèì îáðàçîì:
f q x q x( , ) � �3 2 . (21)
Àâòîìàò A2 òàêæå áóäåò àôôèííûì ãðóïïîâûì àâòîìàòîì, íî ñ áåñêîíå÷-
íûì ÷èñëîì âõîäîâ. Âõîäíîå ñëîâî w x x x k� ( ) ( ) ( )1 2 � äåéñòâóåò íà ñîñòîÿíèå q
ñëåäóþùèì îáðàçîì:
f n w q bt wk( , ) ( )� � �3 , (22)
ãäå êîýôôèöèåíò bt w( ) îïðåäåëÿåòñÿ ïî ôîðìóëå
bt w x i k i
i
k
( ) ( )�
�
�2 3
1
. (23)
Ýòà ôîðìóëà ïîëó÷àåòñÿ ïîñëåäîâàòåëüíûì ïðèìåíåíèåì ôóíêöèè ïåðåõîäîâ
(21) ê ñèìâîëàì x i( ) âõîäíîãî ñëîâà w .
Îïðåäåëèì òåïåðü äîïóñòèìûå ñëîâà. Ïóñòü àâòîìàò A2 íàõîäèòñÿ â íà÷àëü-
íîì ñîñòîÿíèè q q� ( )0 è íà åãî âõîä ïîäàåòñÿ ñëîâî w x x x k� ( ) ( ) ( )1 2 � è ïóñòü
q i f q i x i( ) ( ( ), ( ))�
1 , 1 � �i k , — òðàåêòîðèÿ ñîñòîÿíèé àâòîìàòà ïîä äåéñòâèåì
ýòîãî ñëîâà. Òîãäà ñëîâî w íàçûâàåòñÿ äîïóñòèìûì, åñëè äëÿ âñåõ i, 1 � �i k ,
âûïîëíÿåòñÿ óñëîâèå
x i q i( ) ( ( ))�
ord 2 1 , 1 � �i k . (24)
Äîïóñòèìîå ñëîâî w äëèíû k îäíîçíà÷íî îïðåäåëÿåòñÿ íà÷àëüíûì ñîñòîÿíè-
åì q, è èç (21) è (24) èíäóêöèåé ïî k ëåãêî óáåäèòüñÿ, ÷òî òðàåêòîðèÿ àâòîìàòà
A2 íà äîïóñòèìîì ñëîâå w äîëæíà ñîâïàäàòü ñ òðàåêòîðèåé ôóíêöèè F q( ):
q i F qi( ) ( )( )� , 1 � �i k . (25)
Êðîìå òîãî, èç íåðàâåíñòâà (19) ñëåäóåò, ÷òî äîïóñòèìîå ñëîâî w x x� ( ) ( )1 2 �
� x k( ) äîëæíî áûòü ìîíîòîííûì, ò.å. óäîâëåòâîðÿòü ñëåäóþùåé öåïî÷êå íå-
ðàâåíñòâ:
0 1 2� � � �x x x k( ) ( ) ( )� . (26)
38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
Òàêèì îáðàçîì, åñëè àâòîìàò A2 èç ñîñòîÿíèÿ q ïîä äåéñòâèåì äîïóñòèìîãî ñëî-
âà w x x x k� ( ) ( ) ( )1 2 � äëèíû k ïåðåõîäèò â ñîñòîÿíèå 2 y , òî èç (22), (23) ïîëó÷èì
q f w
bt wy
y
k
y k x i i
i
k
� �
�
�
�1
1
2
2
3
2 3 2 3( , )
( ) ( ) , (27)
ãäå 0 1 2� � � � �x x x k y( ) ( ) ( )� . Îòñþäà è èç ñâîéñòâà (25) ïîëó÷àåì ñëåäóþ-
ùóþ âàæíóþ ôîðìóëó:
F k y k x i i
i
k
y( ) ( )2 3 2 3 2
1
�
�
�
�
�
�
�
�
�
�� . (28)
×ÈÑËÀ ÁÎÌÀ–ÇÎÍÒÀ××È
Ïóñòü ñîãëàñíî (26) çàäàíà ìîíîòîííàÿ ïîñëåäîâàòåëüíîñòü íåîòðèöàòåëüíûõ
öåëûõ ÷èñåë 0 1 2� � � �x x x k( ) ( ) ( )� äëèíû k . Ñ ïîìîùüþ ïîçèöèîííîãî äâî-
è÷íîãî êîäèðîâàíèÿ ýòó ïîñëåäîâàòåëüíîñòü ìîæíî îòîæäåñòâèòü ñ íàòóðàëü-
íûì ÷èñëîì
m x i
i
k
�
�
�2
1
( ) , 0 1 2� � � �x x x k( ) ( ) ( )� . (29)
È íàîáîðîò, íîìåðà åäèíè÷íûõ ðàçðÿäîâ äâîè÷íîãî ðàçëîæåíèÿ íàòóðàëüíîãî
÷èñëà äàþò òàêóþ ìîíîòîííóþ ïîñëåäîâàòåëüíîñòü.
×èñëî åäèíèö â äâîè÷íîì ðàçëîæåíèè íàòóðàëüíîãî ÷èñëà m íàçîâåì âàëåíò-
íîñòüþ (âåñîì) ýòîãî ÷èñëà è îáîçíà÷èì �( )m . ×èñëî ord 2 1( ) ( )m x� íàçîâåì
(äâîè÷íûì) ïîðÿäêîì ÷èñëà m . Îòìåòèì, ÷òî ïîñëå âûíåñåíèÿ çà ñêîáêè ìëàä-
øåé ñòåïåíè äâîéêè â âûðàæåíèè (29) îñòàåòñÿ íå÷åòíîå ÷èñëî. Äâîè÷íîé ñòå-
ïåíüþ deg 2 ( )m íàòóðàëüíîãî ÷èñëà m íàçîâåì íàèáîëüøóþ ñòåïåíü äâîéêè x k( )
â åãî äâîè÷íîì ðàçëîæåíèè (29).
Îïðåäåëèì ôóíêöèþ � : N Q� , ïîëîæèâ �( )2 2x x� äëÿ âñåõ x � 0, à ÷èñëó
m âèäà (29), ãäå �( )m k� � 2, ïîñòàâèì â ñîîòâåòñòâèå ÷èñëî
�( )
( ) ( ) ( ) ( )
m
x k x k x k x k
k
�
2 2 3 2 3 2
3
1 2 2 1
1
�
. (30)
Íàçîâåì ÷èñëà, íàõîäÿùèåñÿ â îáëàñòè çíà÷åíèé ýòîé ôóíêöèè, ÷èñëàìè Áî-
ìà–Çîíòà÷÷è, ïîñêîëüêó ýòè àâòîðû ïåðâûìè îáðàòèëè âíèìàíèå íà èõ âàæ-
íîñòü äëÿ ïðîáëåìû Êîëëàòöà [10]. Òî÷íåå, ÷èñëî âèäà (30) íàçîâåì ÷èñëîì
Áîìà–Çîíòà÷÷è óðîâíÿ k
1, à ÷èñëî m áóäåì ñ÷èòàòü «íîìåðîì» ñîîòâåòñòâó-
þùåãî ÷èñëà Áîìà–Çîíòà÷÷è. Ñòåïåíè äâîéêè ìîæíî ñ÷èòàòü ÷èñëàìè
Áîìà–Çîíòà÷÷è íóëåâîãî óðîâíÿ.
Îáðàòèì âíèìàíèå, ÷òî â (27) è (28) òàêæå ôèãóðèðóþò ÷èñëà Áîìà–Çîíòà÷-
÷è. Ïîýòîìó èç ãèïîòåçû Êîëëàòöà âûòåêàåò âêëþ÷åíèå
N � Im ( )� . (31)
Ñâîéñòâî (28) ïîêàçûâàåò, ÷òî âåðíî è îáðàòíîå óòâåðæäåíèå. Òàêèì îáðàçîì,
ïðèõîäèì ê ñëåäóþùåé ýêâèâàëåíòíîé ôîðìå ãèïîòåçû Êîëëàòöà.
Ïðîáëåìà Êîëëàòöà (ôîðìà 5). Ëþáîå íàòóðàëüíîå ÷èñëî ÿâëÿåòñÿ ÷èñëîì
Áîìà–Çîíòà÷÷è.
×òîáû ëó÷øå ïîíÿòü ñòðóêòóðó ÷èñåë Áîìà–Çîíòà÷÷è, íà÷íåì èçó÷åíèå èõ
ñîñòàâíûõ ÷àñòåé. Ôóíêöèþ bt èç (23) ìîæíî îïðåäåëèòü íà íàòóðàëüíûõ ÷èñëàõ
bt N N: � ñëåäóþùèì îáðàçîì:
bt m x k x k x k( ) ( ) ( ) ( )� � � �
2 3 2 3 21 1 1
� , 0 1 2� � � �x x x k( ) ( ) ( )� , (32)
ãäå ÷èñëî m èìååò äâîè÷íîå ðàçëîæåíèå âèäà (29). ×èñëî bt m( ) íàçîâåì áè-
òåðíàðíûì ÷èñëîì óðîâíÿ k. Íàçâàíèå äëÿ ýòèõ ÷èñåë îòðàæàåò êîìáèíàöèþ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 39
íàçâàíèé ñòåïåíåé äâîéêè (áèíàðíûå) ñî ñòåïåíÿìè òðîéêè (òåðíàðíûå).
Îòìåòèì, ÷òî áèòåðíàðíûå ÷èñëà íå äåëÿòñÿ íà òðè, ïîýòîìó íå âñÿêîå íàòó-
ðàëüíîå ÷èñëî ìîæíî ïðåäñòàâèòü â âèäå (32). Òàêèì îáðàçîì, îòîáðàæåíèå
bt N N: � íå ÿâëÿåòñÿ íè ñþðúåêöèåé, íè èíúåêöèåé, ïîñêîëüêó, íàïðèìåð,
bt bt( ) ( )7 17 19� � . Ôóíêöèÿ bt íåïîäâèæíà íà ñòåïåíÿõ äâîéêè bt x x( )2 2� äëÿ
âñåõ x � 0.
Îêàçûâàåòñÿ, áèòåðíàðíûå ÷èñëà èìåþò ñâîþ èñòîðèþ, ïîñêîëüêó åùå Ðàìà-
íóäæàí ðàññìàòðèâàë ñóììû ñëåäóþùåãî âèäà [2]:
2 3 2 3 2 31 1 2 1x y k x k y x k y( ) ( ) ( ) ( ) ( ) ( )� � �
� ,
ãäå 0 1 2� � � �x x x k( ) ( ) ( )� , 0 1 2� � � �y y y k( ) ( ) ( )� . À. Àíèñèìîâ íàçûâàåò
òàêèå ÷èñëà áèòðèòîâûìè (ïðîèçâîäíàÿ îò áèòîâ è òðèòîâ) è îòìå÷àåò, ÷òî
ëþáîå íàòóðàëüíîå ÷èñëî ÿâëÿåòñÿ áèòðèòîâûì [11].
Ïîðÿäîê ord 2 ( ( ))bt m áèòåðíàðíîãî ÷èñëà bt m( ) ñîâïàäàåò ñ ïîðÿäêîì ÷èñëà m :
ord ord2 2 1( ( )) ( ) ( )bt m m x� � , (33)
ïîñêîëüêó ïîñëå âûíåñåíèÿ çà ñêîáêè ìëàäøåé ñòåïåíè äâîéêè â âûðàæåíèè
(32) îñòàåòñÿ íå÷åòíîå ÷èñëî.
Íåòðóäíî ïîêàçàòü, ÷òî íà íàòóðàëüíûõ ÷èñëàõ, èìåþùèõ îäèíàêîâóþ âà-
ëåíòíîñòü, ôóíêöèÿ bt âçàèìíî îäíîçíà÷íà. Äåéñòâèòåëüíî, ïóñòü èìååò ìåñòî
ðàâåíñòâî
2 3 2 3 2 2 3 2 3 21 1 1 1 1 1x k x k x k y k y k y( ) ( ) ( ) ( ) ( )
� � � � � � �� �
( )k . (34)
Òîãäà èç (33) èìååì x y( ) ( )1 1� , ïîñêîëüêó äâîè÷íûå ïîðÿäêè ðàâíûõ íàòóðàëü-
íûõ ÷èñåë äîëæíû áûòü ðàâíû. Ñîêðàùàÿ îáå ÷àñòè ðàâåíñòâà (34) íà îáùèé
÷ëåí 2 31 1x k( )
, ïðèõîäèì ê ðàâåíñòâó áèòåðíàðíûõ ÷èñåë óðîâíÿ k –1. Äàëåå, ðàñ-
ñóæäàÿ àíàëîãè÷íî èëè ïðèìåíÿÿ èíäóêöèþ, çàêëþ÷àåì, ÷òî x i y i( ) ( )� , 2 � �i k .
Òàêèì îáðàçîì, ïðè ôèêñèðîâàííîì ÷èñëå k êàæäîå íàòóðàëüíîå ÷èñëî èìååò íå
áîëåå îäíîãî ïðåäñòàâëåíèÿ â âèäå áèòåðíàðíîãî ÷èñëà óðîâíÿ k.
ßäðîì Ker ( )F ôóíêöèè F q( ) íàçîâåì ìíîæåñòâî ðàöèîíàëüíûõ ÷èñåë
Ker { }( ) | ( ) ( )( )F q k F qk� � � 0 . (35)
Ðàññìîòðèì ôóíêöèþ rt N Q: � ñëåäóþùåãî âèäà:
rt m
bt m
k
x x k k x k( )
( )
( ( ) ( ) ( ) ( )�
�
� � �
3
2 3 2 3 2 31 1 1 1
�
k ) , (36)
ãäå ÷èñëî m èìååò äâîè÷íîå ðàçëîæåíèå âèäà (29) è k m� �( ). Êðîìå òîãî, áóäåì
ñ÷èòàòü, ÷òî rt( )0 0� . ×èñëî rt m( ) íàçîâåì êîðíåâûì ÷èñëîì óðîâíÿ k.  îòëè-
÷èå îò ôóíêöèè bt ôóíêöèÿ rt âçàèìíî îäíîçíà÷íà. Äåéñòâèòåëüíî, åñëè
rt m rt n( ) ( )� , òî íàòóðàëüíûå ÷èñëà m è n äîëæíû èìåòü îäèíàêîâóþ âàëåíò-
íîñòü è òîãäà èç ðàâåíñòâà bt m bt n( ) ( )� ñëåäóåò, ÷òî m n� . Îòìåòèì, ÷òî
rt( ) /7 19 27�
, à rt( ) /17 19 9�
. Î÷åâèäíî, ÷òî ñâîéñòâî (33) âåðíî è äëÿ êîðíå-
âûõ ÷èñåë, ïîñêîëüêó îíè îòëè÷àþòñÿ îò áèòåðíàðíûõ íå÷åòíûì çíàìåíàòåëåì
ord ord2 2 1( ( )) ( ( )) ( )rt m bt m x� � . (37)
Ðàññìîòðèì òàêæå ôóíêöèþ g m( ), êîòîðàÿ ñòèðàåò ìëàäøèé åäèíè÷íûé ðàç-
ðÿä â äâîè÷íîé çàïèñè íåíóëåâîãî íàòóðàëüíîãî ÷èñëà m:
g m m
m
( )
( )�
2 2ord
. (38)
Èìååò ìåñòî ñëåäóþùåå ñîîòíîøåíèå äëÿ ëþáîãî íàòóðàëüíîãî ÷èñëà m :
F rt m rt g m( ( )) ( ( ))� . (39)
40 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
Äåéñòâèòåëüíî, ñ ó÷åòîì ñâîéñòâ (36) è (37) èìååì ñëåäóþùèå ðàâåíñòâà:
F rt m
bt m bt g mx
x
k
x
k
( ( ))
( ) ( ( ))( )
( )
( )�
� �
2
2
3
2
3
1
1
1
1
1
� rt g m( ( )) .
Òàêèì îáðàçîì, ôóíêöèè F è g ñîïðÿæåíû ÷åðåç ôóíêöèþ rt. Äðóãèìè ñëî-
âàìè, ôóíêöèÿ F äåéñòâóåò íà êîðíåâûå ÷èñëà êàê ôóíêöèÿ g íà íàòóðàëüíûå,
îíà ñòèðàåò ìëàäøèé «áèòåðíàðíûé ðàçðÿä» â êîðíåâîì ÷èñëå è òåì ñàìûì ïî-
íèæàåò åãî óðîâåíü íà åäèíèöó. Ñ ïîìîùüþ èíäóêöèè ñîîòíîøåíèå (39) ìîæíî
îáîáùèòü íà ëþáîå íàòóðàëüíîå ÷èñëî k:
F rt m rt g mk k( ) ( )( ( )) ( ( ))� . (40)
Îòñþäà, åñëè ïîëîæèòü k m� �( ), ñ ó÷åòîì (38) è î÷åâèäíîãî ðàâåíñòâà g mk( ) ( ) � 0
ïîëó÷àåì ñîîòíîøåíèå
F rt mk( ) ( ( )) � 0 , k m� �( ) . (41)
Çíà÷èò, âñå êîðíåâûå ÷èñëà ñîãëàñíî (35) íàõîäÿòñÿ â ÿäðå ôóíêöèè F . Äëÿ
äîêàçàòåëüñòâà ñëåäóþùåé òåîðåìû èñïîëüçóåì ïîíÿòèå ýêâèâàëåíòíîñòè.
Íàçîâåì ðàöèîíàëüíûå ÷èñëà q è r èç Q2 ýêâèâàëåíòíûìè, åñëè
od q od r( ) ( )� . Äðóãèìè ñëîâàìè, îòíîøåíèå ýêâèâàëåíòíîñòè áåç èçìåíåíèé ïå-
ðåíîñèòñÿ íà ðàöèîíàëüíûå ÷èñëà. Ðàöèîíàëüíîå ÷èñëî q íàçîâåì «íå÷åòíûì»,
åñëè q od q� ( ) , ò.å. åñëè îíî ÿâëÿåòñÿ îòíîøåíèåì äâóõ öåëûõ íå÷åòíûõ ÷èñåë.
Îáîçíà÷èì P q q xx( ) { | }� �2 0 êëàññ ýêâèâàëåíòíîñòè ñ åäèíñòâåííûì íå÷åòíûì
ïðåäñòàâèòåëåì q od q� ( ) . Ñâîéñòâî (15) îñòàåòñÿ âåðíûì è äëÿ ðàöèîíàëüíûõ
÷èñåë, ïîýòîìó ôóíêöèÿ F q( ) òàêæå äåéñòâóåò íà êëàññàõ ýêâèâàëåíòíîñòè.
Òåîðåìà 1. Ïðè ôèêñèðîâàííîì ÷èñëå k êîðíåâûå ÷èñëà óðîâíÿ k è òîëüêî
îíè ÿâëÿþòñÿ ðåøåíèÿìè óðàâíåíèÿ F qk( ) ( ) � 0.
Äîêàçàòåëüñòâî. Èç ñîîòíîøåíèÿ (41) ñëåäóåò, ÷òî âñå êîðíåâûå ÷èñëà
óðîâíÿ k ÿâëÿþòñÿ ðåøåíèÿìè ýòîãî óðàâíåíèÿ. Äîêàæåì èíäóêöèåé ïî k, ÷òî
äðóãèõ ðåøåíèé íå ñóùåñòâóåò.
Ïóñòü k �1 è F q( ) � 0 äëÿ íåíóëåâîãî ðàöèîíàëüíîãî ÷èñëà q , òîãäà
3 0q e q� ��( ) . Ïîäñòàâèâ ñþäà âìåñòî q âûðàæåíèå e q od q�( ) ( ) èç ñîîòíîøåíèÿ
(17) è ñîêðàòèâ íà íåíóëåâîå ÷èñëî e q�( ), ïîëó÷èì od q( ) /�
1 3 . Çíà÷èò, ÷èñëî
q äîëæíî íàõîäèòüñÿ â êëàññå ýêâèâàëåíòíîñòè P ( / )
1 3 , ò.å. q rt x x� �
( ) /2 2 3
ïðè íåêîòîðîì ÷èñëå x � 0 . Òàêèì îáðàçîì, áàçèñ èíäóêöèè äîêàçàí.
Ïðåäïîëîæèì, ÷òî óòâåðæäåíèå äîêàçàíî äëÿ âñåõ ÷èñåë, ìåíüøèõ ÷åì k ,
äîêàæåì åãî äëÿ ÷èñëà k �1 . Ïóñòü äëÿ íåíóëåâîãî ðàöèîíàëüíîãî ÷èñëà q âû-
ïîëíÿåòñÿ óñëîâèå F qk( ) ( ) � 0 , òîãäà èç ïðåäïîëîæåíèÿ èíäóêöèè ñëåäóåò, ÷òî
÷èñëî F q( ) äîëæíî áûòü êîðíåâûì ÷èñëîì óðîâíÿ k
1, ò.å. F q rt m( ) ( )� äëÿ íå-
êîòîðîãî íàòóðàëüíîãî ÷èñëà m âàëåíòíîñòè k
1. Èç ñâîéñòâ (19) è (37) ïîëó÷à-
åì íåðàâåíñòâî
ord ord ord ord2 2 2 2( ) ( ( )) ( ( )) ( )q F q rt m m� � � . (42)
Îòñþäà è èç ðàâåíñòâà F q q rt m
q
( ) ( )
( )� � �3 2 2ord
çàêëþ÷àåì, ÷òî èìååò ìåñòî
ðàâåíñòâî q rt mx�
�2 3 3/ ( ) / , ãäå x q� ord 2 ( ) . Òîãäà èç íåðàâåíñòâà (42) ñëå-
äóåò, ÷òî q rt n� ( ), ãäå n mx� �2 .
Òåîðåìà äîêàçàíà.
Òàêèì îáðàçîì, ÿäðî ôóíêöèè F èìååò ñëîèñòóþ (óðîâíåâóþ) ñòðóêòóðó, íà îò-
äåëüíûõ ñëîÿõ êîòîðîé ðàñïîëàãàþòñÿ êîðíåâûå ÷èñëà ñîîòâåòñòâóþùåãî óðîâíÿ.
Äîêàæåì òåïåðü ñëåäóþùåå óòâåðæäåíèå, êîòîðîå íàçîâåì àääèòèâíîé ëåììîé.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 41
Ëåììà 1. Ïóñòü q è r — íåíóëåâûå ðàöèîíàëüíûå ÷èñëà è k — íàòóðàëüíîå
÷èñëî òàêîå, ÷òî ord ord2
1
2( ( )) ( )( )F q rk
� , òîãäà èìååò ìåñòî ñëåäóþùåå ðàâåí-
ñòâî: F q r F q rk k k( ) ( )( ) ( )� � � �3 .
Äîêàçàòåëüñòâî. Áóäåì äîêàçûâàòü ëåììó èíäóêöèåé ïî k. Ïîñêîëüêó
F q q( ) ( )0 � ïðè k �1, óñëîâèå ëåììû äàåò íåðàâåíñòâî ord ord2 2( ) ( )q r� , èç êîòî-
ðîãî ñëåäóåò, ÷òî ord ord2 2( ) ( )q q r� � . Îòñþäà ïîëó÷àåì ñëåäóþùåå ðàâåíñòâî:
F q r q r q r F q r
q r q
( ) ( ) ( )
( ) ( )� � � � � � � � � � ��
3 2 3 2 3 32 2ord ord
. (43)
Òàêèì îáðàçîì, áàçèñ èíäóêöèè äîêàçàí.
Ïðåäïîëîæèì òåïåðü, ÷òî óòâåðæäåíèå äîêàçàíî äëÿ âñåõ ÷èñåë, ìåíüøèõ
÷åì k , òîãäà äîêàæåì åãî äëÿ ÷èñëà k �1. Èç ïðåäïîëîæåíèÿ èíäóêöèè èìååì
F q r F F q r F F q rk k k k( ) ( ) ( )( ) ( ( )) ( ( ) )� � � � � �
1 1 13 .
Äàëåå, èç óñëîâèÿ ëåììû ñëåäóåò, ÷òî ord ord2
1 1
2
13( ( ) ) ( ( ))( ) ( )F q r F qk k k
� � � .
Òîãäà, ïîäñòàâèâ â ðàâåíñòâî (43) F qk( ) ( )
1 âìåñòî q è 3 1k r
� âìåñòî r, ïî-
ëó÷èì ðàâåíñòâî
F F q r F F q r F qk k k k k( ( ) ) ( ( )) ( )( ) ( ) ( )
� � � � � � � �1 1 1 13 3 3 3k r� .
Ëåììà äîêàçàíà.
Âåðíåìñÿ ê ÷èñëàì Áîìà–Çîíòà÷÷è. Ïóñòü íàòóðàëüíîå ÷èñëî m èìååò äâî-
è÷íîå ðàçëîæåíèå âèäà (29) è âàëåíòíîñòü íå ìåíüøå äâóõ k m� ��( ) 2 . Èç (30)
è (36) ñëåäóåò ñîîòíîøåíèå
�( ) ( )
( )
( )m rt m
x k
k
x k� �
2
3
2
1
. (44)
Òîãäà èç (40) ïîëó÷èì ðàâåíñòâî
F rt m rt g m rtk x k k x k x k( ) ( ) ( ) ( ) ( )( ( )) ( ( )) (
�
�2 2 12 2 2 ) /( )�
2 31x k .
Çíà÷èò, èìååò ìåñòî ñëåäóþùåå íåðàâåíñòâî:
ord ord2
2
22 1 2 3( ( ( )) ( ) ( ) ( /( ) ( ) ( )F rt m x k x kk x k x k k
�
� �
1 ) .
Ñëåäîâàòåëüíî, ê ÷èñëàì rt m x k( )( )
2 è 2 3 1x k k( ) /
ìîæíî ïðèìåíèòü ëåììó 1
è ñ ïîìîùüþ ñâîéñòâà (41) ïîëó÷èòü ñîîòíîøåíèå
F m F rt mk k x k k
x k
k
x( ) ( ) ( )
( )
( ( )) ( (( ))
�
� �1 1 1
1
2 3
2
3
2�
( )k .
Îòìåòèì, ÷òî ýòî ñîîòíîøåíèå òðèâèàëüíî âûïîëíÿåòñÿ äëÿ ñòåïåíåé äâîéêè,
ïîñêîëüêó F x x( ) ( )0 2 2� . Çíà÷èò, äëÿ âñåõ íàòóðàëüíûõ ÷èñåë m, èìåþùèõ
äâîè÷íîå ðàçëîæåíèå (29), èìååò ìåñòî ñëåäóþùåå ðàâåíñòâî:
F mk m( ) ( )
( ( ))
�1 2 2�
deg
, k m� �( ) , deg 2 ( ) ( )m x k� . (45)
Òàêèì îáðàçîì, ïîëó÷åíî åùå îäíî äîêàçàòåëüñòâî ðàâåíñòâà (28), ïðè ýòîì
âûÿñíèëîñü, ÷òî ÷èñëà Áîìà–Çîíòà÷÷è ÿâëÿþòñÿ ñìåùåííûìè íà íåêîòîðîå ÷èñ-
ëî êîðíåâûìè ÷èñëàìè. Òåì ñàìûì ñëîèñòàÿ ñòðóêòóðà, ñâîéñòâåííàÿ êîðíåâûì
÷èñëàì, íàñëåäóåòñÿ ÷èñëàìè Áîìà–Çîíòà÷÷è.
42 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
ÊÎÄÈÐÎÂÀÍÈÅ ÒÐÀÅÊÒÎÐÈÉ
Ðàññìîòðèì ôóíêöèþ �( )m . Îáîçíà÷èì N k( ) ìíîæåñòâî íàòóðàëüíûõ ÷èñåë
âàëåíòíîñòè k � 1, à BZ k( ) ìíîæåñòâî ÷èñåë Áîìà–Çîíòà÷÷è óðîâíÿ k. Íåòðóä-
íî ïîêàçàòü, ÷òî ôóíêöèÿ � âçàèìíî îäíîçíà÷íà íà ìíîæåñòâå N k( ) . Äåéñò-
âèòåëüíî, ïóñòü èìååò ìåñòî ðàâåíñòâî
2 2 3 2 2 2 3 21 2 1 1 2 1x k x k x k y k y k y k( ) ( ) ( ) ( ) ( ) (
�
� �
) .
Òîãäà, ðàññóæäàÿ êàê è â ñëó÷àå áèòåðíàðíûõ ÷èñåë, çàêëþ÷àåì, ÷òî x y( ) ( )1 1� ,
ïîñêîëüêó äâîè÷íûå ïîðÿäêè ðàâíûõ öåëûõ ÷èñåë äîëæíû áûòü ðàâíû, è ò.ä.
Îáîçíà÷èì � k îãðàíè÷åíèå � íà N k( ), òîãäà áèåêöèÿ � k N k BZ k: ( ) ( )�
1
äîëæíà èìåòü îáðàòíóþ, êîòîðóþ îáîçíà÷èì � k . Áèåêöèÿ � k BZ k N k: ( ) ( )
�1
îáëàäàåò ñëåäóþùèì ñâîéñòâîì:
� �k k
x i
i
k
m m( ( )) ( )� �
�
�2
1
, (46)
ãäå ÷èñëî m èìååò äâîè÷íîå ðàçëîæåíèå âèäà (29). Èç ñâîéñòâ (40), (44) è ëåì-
ìû 1 âûòåêàåò ðàâåíñòâî
F m rt g mi
x k
k i
i x k( )
( )
( ) ( )( ( )) ( ( ))
� �
1 12
3
2� , 1 � �i k .
Çíà÷èò, ord 2
1( ( ( ))) ( )( )F m x ii
�� , 1 � �i k , è, ñëåäîâàòåëüíî, ôóíêöèÿ � k
«ñîáèðàåò» ñòåïåíè äâîéêè, êîòîðûå îáðàçóþòñÿ âäîëü òðàåêòîðèè F mi( ) ( ( ))
1
� ,
1 � �i k , è òåì ñàìûì êîäèðóåò ýòó òðàåêòîðèþ íàòóðàëüíûì ÷èñëîì. Ïðè òàêîé
òðàêòîâêå ôóíêöèÿ � k ëåãêî ïåðåíîñèòñÿ íà íàòóðàëüíûå ÷èñëà è ðàöèîíàëüíûå
÷èñëà ñ íå÷åòíûìè çíàìåíàòåëÿìè, íî òàì îíà óæå íå áóäåò áèåêöèåé.
Òàêèì îáðàçîì, ôóíêöèÿ �( )m ïî êîäó òðàåêòîðèè âîññòàíàâëèâàåò èñõîä-
íîå ÷èñëî Áîìà–Çîíòà÷÷è. Ïîñêîëüêó ýòà ôóíêöèÿ âñþäó îïðåäåëåíà, ëþáîå íà-
òóðàëüíîå ÷èñëî ìîæåò áûòü êîäîì íåêîòîðîé «óñïåøíîé» òðàåêòîðèè.
Îòìåòèì, ÷òî ìíîæåñòâà N k( ) âçàèìíî íå ïåðåñåêàþòñÿ ïðè ðàçëè÷íûõ
÷èñëàõ k, â òî âðåìÿ êàê ìíîæåñòâà BZ k( ) âêëþ÷àþòñÿ îäíî â äðóãîå:
BZ k BZ k( ) ( )
�1 (47)
ïðè ëþáîì k � 1. Äåéñòâèòåëüíî, ïóñòü ÷èñëî m èìååò ðàçëîæåíèå âèäà (29), òîã-
äà èç ñâîéñòâà (45) ñëåäóåò, ÷òî òðàåêòîðèÿ ÷èñëà Áîìà–Çîíòà÷÷è �( )m
«óñïåøíî» çàêàí÷èâàåòñÿ íà ÷èñëå 2x k( ) . Íî ìîæíî ñäåëàòü åùå îäèí øàã
F x k x k( )( ) ( )2 2 2� � è, ñëåäîâàòåëüíî, � �( ) ( )( )m m x k� � �2 2 . Âïðî÷åì, ýòî ðàâåí-
ñòâî ëåãêî ïðîâåðÿåòñÿ ñ ïîìîùüþ ôîðìóëû (30). Çíà÷èò, ÷èñëî �( )m èìååò
ïðåäñòàâëåíèå óðîâíÿ k è âêëþ÷åíèå (47) äîêàçàíî. Ñëåäîâàòåëüíî, êàæäîå
÷èñëî Áîìà–Çîíòà÷÷è èìååò áåñêîíå÷íî ìíîãî íîìåðîâ.
Îòìåòèì òàêæå áûñòðûé ðîñò ôóíêöèè � k . Íàïðèìåð, F ( ) ( )41 7027 2� è, ñëå-
äîâàòåëüíî, äëÿ êîäèðîâàíèÿ ýòîé òðàåêòîðèè ïîíàäîáèòñÿ 71 äâîè÷íûé ðàçðÿä
èëè 22 äåñÿòè÷íûõ ðàçðÿäà: �42 27 1258491824377140468475( ) � .
ÍÀÒÓÐÀËÜÍÛÅ ×ÈÑËÀ ÁÎÌÀ–ÇÎÍÒÀ××È
Âåðíåìñÿ ê âêëþ÷åíèþ (31), ïîñêîëüêó âîïðîñ î íàòóðàëüíûõ ÷èñëàõ Áîìà–Çîí-
òà÷÷è ÿâëÿåòñÿ îäíèì èç ãëàâíûõ â äàííîé ïðîáëåìå. Ìîæíî ïîïûòàòüñÿ íàéòè
ôîðìóëû äëÿ ýòèõ ÷èñåë èëè èõ íîìåðîâ, íàäåÿñü, ÷òî ëþáîå íàòóðàëüíîå
÷èñëî áóäåò èìåòü ñîîòâåòñòâóþùèé íîìåð.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 43
×èñëàìè íóëåâîãî óðîâíÿ BZ ( )0 , êàê óæå îòìå÷àëîñü, ÿâëÿþòñÿ ñòåïåíè
äâîéêè BZ P( ) ( )0 1� . Íå÷åòíûå ðàöèîíàëüíûå ÷èñëà Áîìà–Çîíòà÷÷è ïåðâîãî
óðîâíÿ èñ÷åðïûâàþòñÿ ÷èñëàìè âèäà ( ) /2 1 3x
, ãäå x N
. Èç íèõ òîëüêî ïðè
÷åòíûõ ÷èñëàõ x ïîëó÷àþòñÿ íàòóðàëüíûå ÷èñëà, ïîýòîìó èìååì
BZ N x Nx( ) ( ) / |1 4 1 31� �
{ }. (48)
Èç ðàâåíñòâà F x x(( ) / )4 1 3 4
� ñëåäóåò, ÷òî �2 4 1 3 1 4(( ) / )x x
� � . Îòìåòèì
òàêæå, ÷òî ÷èñëà Áîìà–Çîíòà÷÷è ïåðâîãî óðîâíÿ ÿâëÿþòñÿ ÷àñòè÷íûìè ñóììà-
ìè áåñêîíå÷íîé ãåîìåòðè÷åñêîé ïðîãðåññèè
( ) /4 1 3 4 1 4 4 1
0
1
x i x
i
x
� � � � �
�
� � . (49)
Ýòîò ðåçóëüòàò ìîæíî ïîëó÷èòü è èç ñëåäóþùåãî îáùåãî óòâåðæäåíèÿ.
Ëåììà 2. Åñëè n ÿâëÿåòñÿ íå÷åòíûì íàòóðàëüíûì ÷èñëîì Áîìà–Çîíòà÷÷è,
òî ÷èñëî 4 1n � òàêæå áóäåò ÷èñëîì Áîìà–Çîíòà÷÷è òîãî æå óðîâíÿ.
Äîêàçàòåëüñòâî. Èç óñëîâèÿ ëåììû âûòåêàþò ñëåäóþùèå ðàâåíñòâà:
F n n F n( ) ( ) ( )4 1 4 3 1 4� � � � . Çíà÷èò, òðàåêòîðèè ÷èñåë n è 4 1n � ïîïàäàþò â îäèí
êëàññ ïîñëå ïåðâîãî øàãà. Ïîýòîìó åñëè F nk x( ) ( ) � 2 ïðè k � 1, òî F nk( ) ( )4 1� �
� �2 2x , è ëåììà äîêàçàíà.
Îòìåòèì, ÷òî åäèíèöà â ñèëó âêëþ÷åíèÿ (47) èìååò ïðåäñòàâëåíèå äëÿ ïåð-
âîãî óðîâíÿ. Ïîýòîìó ìîæíî âîñïîëüçîâàòüñÿ ëåììîé 2 è ïðèìåíèòü ê åäèíèöå
íåîãðàíè÷åííîå ÷èñëî ðàç ôóíêöèþ f n n4 4 1( ) � � äëÿ ïîëó÷åíèÿ âñåõ ÷èñåë
âèäà (49) íà ïåðâîì óðîâíå.
Êîíå÷íî, ýëåìåíòàðíûìè ìåòîäàìè ðåçóëüòàòà íå äîñòèãíåøü, õîòÿ è âòî-
ðîé, è òðåòèé óðîâíè ìîæíî åùå ïîäâåðãíóòü òàêîìó àíàëèçó. Îïèøåì îáùèé
ìåòîä, ïîçâîëÿþùèé ïîëó÷àòü íàòóðàëüíûå ÷èñëà Áîìà–Çîíòà÷÷è íà ëþáîì
óðîâíå è îñíîâàííûé íà ñëåäóþùåì óòâåðæäåíèè.
Ëåììà 3. ×èñëî 2 ÿâëÿåòñÿ ïåðâîîáðàçíûì (ïðèìèòèâíûì) êîðíåì ïî ìîäó-
ëþ 3k ïðè ëþáîì k � 1.
Äîêàçàòåëüñòâî. Ýòî óòâåðæäåíèå ñëåäóåò èç èçâåñòíûõ ôàêòîâ òåîðèè ÷è-
ñåë, íàïðèìåð, äîêàçàòåëüñòâà òåîðåìû 2 èç [12, ãë. 4]. Îòìåòèì òàêæå, ÷òî ÷èñ-
ëî 4 èìååò ïîðÿäîê 3 1k
ïî ìîäóëþ 3k èç [12, ãë. 4, ñëåäñòâèå 2]. Çíà÷èò, â ïîä-
ãðóïïå ãðóïïû U Z Zk( / )3 , ïîðîæäåííîé ÷èñëîì 2, ÷åòíûå ñòåïåíè äâîéêè îáðà-
çóþò ïîäãðóïïó ïîðÿäêà 3 1k
, à íå÷åòíûå ñòåïåíè — ñìåæíûé êëàññ ïî ýòîé
ïîäãðóïïå. Òàêèì îáðàçîì, ïîðÿäîê ïîäãðóïïû, ïîðîæäåííîé ÷èñëîì 2, ðàâåí
2 3 3 3 31 1� �
�
k k k k
�( ) , ãäå � — ôóíêöèÿ Ýéëåðà. Çíà÷èò, ÷èñëî 2 ïîðîæäàåò
âñþ ãðóïïó U Z Zk( / )3 , ñîñòîÿùóþ èç ÷èñåë, âçàèìíî ïðîñòûõ ñ ìîäóëåì 3k
è ìåíüøèõ ÷åì 3k . Ñëåäîâàòåëüíî, ÷èñëî 2 ÿâëÿåòñÿ ïåðâîîáðàçíûì êîðíåì è
ëåììà äîêàçàíà.
Ïîëîæèì c k k( ) ( )� � 3 = 3 3 1k k
. Êàê áûëî ïîêàçàíî â ëåììå 2, ÷èñëî c k( )
áóäåò ïåðèîäîì ÷èñëà 2 ïî ìîäóëþ 3k , ò.å. c k( ) — íàèìåíüøåå ÷èñëî, óäîâëåòâî-
ðÿþùåå ñðàâíåíèþ
2 1 3c k k( ) ( )� mod . (50)
Âîçüìåì òåïåðü ïðîèçâîëüíîå áèòåðíàðíîå ÷èñëî bt m( ) óðîâíÿ k âèäà (32). Ïî-
ñêîëüêó ÷èñëî bt m( ) íå äåëèòñÿ íà òðè, îíî áóäåò âçàèìíî ïðîñòûì ñ ÷èñëîì 3k
è, ñëåäîâàòåëüíî, áóäåò ýëåìåíòîì ãðóïïû U Z Zk( / )3 . Òîãäà ïî ëåììå 3 íàéäåò-
ñÿ ÷èñëî 0 � �y m c k( ) ( ) òàêîå, ÷òî 2 3y m kbt m( ) ( ) (mod )� . Îòñþäà è èç ñâîé-
44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
ñòâà (50) çàêëþ÷àåì, ÷òî ïðè ëþáîì öåëîì íåîòðèöàòåëüíîì ÷èñëå x � 0 ñëåäóþ-
ùèå ÷èñëà Áîìà–Çîíòà÷÷è áóäóò öåëûìè:
2
3
x c k y m
k
bt m� �
( ) ( ) ( )
. (51)
Îòìåòèì, ÷òî íà÷èíàÿ ñ íåêîòîðîãî x0 âñå ÷èñëà âèäà (51) áóäóò íàòóðàëü-
íûìè. Ïîýòîìó, ÷òîáû ïîëó÷èòü íîìåð íàòóðàëüíîãî ÷èñëà Áîìà–Çîíòà÷÷è,
ìîæíî âûáðàòü ïðîèçâîëüíîå íàòóðàëüíîå ÷èñëî, à ïîñëåäíèé ñòàðøèé ðàçðÿä
ïîäáèðàòü â çàâèñèìîñòè îò âûáðàííîãî ÷èñëà. Òàêèì îáðàçîì, ìîæíî ïîëó÷èòü,
íàïðèìåð, âñå ÷èñëà íà ïåðâîì óðîâíå âèäà (49).
ÏÐÎÁËÅÌÀ ÖÈÊËÎÂ
Äàííàÿ ïðîáëåìà ñîñòîèò â äîêàçàòåëüñòâå îòñóòñòâèÿ íåòðèâèàëüíûõ öèêëîâ
äëÿ ôóíêöèè Êîëëàòöà, ñîñòîÿùèõ èç íàòóðàëüíûõ ÷èñåë. Îòìåòèì, ÷òî ðåøå-
íèå ïðîáëåìû öèêëîâ íå âëå÷åò ðåøåíèÿ ïðîáëåìû Êîëëàòöà, ïîñêîëüêó îñòà-
åòñÿ åùå ïðîáëåìà ðàñõîäèìîñòè.
Ïóñòü m — íå÷åòíîå íàòóðàëüíîå ÷èñëî, â äâîè÷íîì ðàçëîæåíèè êîòîðîãî
èìååòñÿ k åäèíèö:
m y y k� � � �
1 2 21 1( ) ( )
� , 0 0 1 1 1� � � �
�y y y k k( ) ( ) ( ),� . (52)
Äàëåå, ïîëîæèì d i y i y i( ) ( ) ( )�
1 , 1 1� �i k – , è çàïèøåì íå÷åòíîå áèòåðíàð-
íîå ÷èñëî bt m( ) êàê ôóíêöèþ ïîñëåäîâàòåëüíîñòè íàòóðàëüíûõ ÷èñåë d i( ),
1 1� �i k – :
bt d d k k d k d d k( ( ), , ( )) ( ) ( ) ( )1 1 3 2 3 21 1 2 1 1
� �
�
� � � �
� �
. (53)
Áîì è Çîíòà÷÷è îïèñàëè âñå ðàöèîíàëüíûå ÷èñëà, êîòîðûå ìîãóò âñòðå÷àòü-
ñÿ â öèêëàõ ôóíêöèè Êîëëàòöà [10]. À èìåííî, ïóñòü m — íå÷åòíîå íàòóðàëüíîå
÷èñëî âèäà (52) è y k y k m( ) ( ) ( )�
�1 2deg . Ïîëîæèì d k y k y k( ) ( ) ( )�
1 , òîãäà
ñëåäóþùåå ðàöèîíàëüíîå ÷èñëî íàçîâåì öèêëè÷åñêèì ïîðÿäêà k:
cc d d k d k
k d k d d
( ( ), , ( ), ( ))
( ) ( ) (
1 1
3 2 3 21 1 2 1
�
�
�
�
� � �
� � k
y k k
1
2 3
)
( )
. (54)
Îñòàëüíûå ÷ëåíû öèêëà ïîëó÷àþòñÿ öèêëè÷åñêèì ñäâèãîì âëåâî ïîñëåäîâà-
òåëüíîñòè íàòóðàëüíûõ ÷èñåë d i( ), 1 � �i k :
cc d d k d cc d k d d k( ( ), , ( ), ( )), , ( ( ), ( ), , ( ))2 1 1 1� � �
. (55)
Îáîçíà÷èì cc1 ÷èñëî âèäà (54), à cci , 2 � �i k, ÷èñëà âèäà (55), òîãäà ñ ïî-
ìîùüþ íåïîñðåäñòâåííîãî âû÷èñëåíèÿ ìîæíî óáåäèòüñÿ, ÷òî F cci( ) ýêâèâàëåíò-
íî cci�1, 1 1� �i k – , à F cck( ) ýêâèâàëåíòíî cc1, ò.å. ÷èñëà cci , 1 � �i k , äåéñòâè-
òåëüíî îáðàçóþò öèêë.
Îòìåòèì, ÷òî ÷ëåíû öèêëà (55) ëèáî âñå îòðèöàòåëüíûå, ëèáî âñå ïîëîæè-
òåëüíûå, ïîñêîëüêó èõ çíàê îïðåäåëÿåòñÿ çíàìåíàòåëåì 2 3y k k( )
, êîòîðûé
ó âñåõ ÷ëåíîâ öèêëà îäèíàêîâûé. Êðîìå òîãî, îíè ëèáî âñå öåëûå, ëèáî âñå íåöå-
ëûå, ïîñêîëüêó ôóíêöèÿ F ñîõðàíÿåò öåëî÷èñëåííîñòü. Îáîçíà÷èì ÑÑ ñîâîêóï-
íîñòü âñåõ öèêëè÷åñêèõ ðàöèîíàëüíûõ ÷èñåë âèäà (54), òîãäà äëÿ ðåøåíèÿ
ïðîáëåìû öèêëîâ íåîáõîäèìî äîêàçàòü óñëîâèå
CC N� �1 1{ }. (56)
Ñëåäóåò îòìåòèòü, ÷òî ïðè k �1 ôîðìóëà (54) äàåò ðàöèîíàëüíûå íåïîäâèæ-
íûå êëàññû, êîòîðûå îïðåäåëÿþòñÿ ÷èñëàìè 1 2 3/ ( )y
, ãäå y � 1. Òîëüêî ïðè
y � 2 â ýòîì ñëó÷àå ïîëó÷àåòñÿ íàòóðàëüíîå ÷èñëî, ðàâíîå åäèíèöå. Äðóãèìè ñëîâà-
ìè, òîëüêî åäèíè÷íûé êëàññ ÿâëÿåòñÿ íåïîäâèæíûì (îòíîñèòåëüíî ôóíêöèè F ), ñî-
ñòîÿùèì èç íàòóðàëüíûõ ÷èñåë.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 45
Ñ ðîñòîì k ïðîâåðêà óñëîâèÿ (56) óñëîæíÿåòñÿ. Òåì íå ìåíåå äîêàçàòåëüñòâî
óñëîâèÿ (56) ìîæåò îêàçàòüñÿ ïðîùå äîêàçàòåëüñòâà âêëþ÷åíèÿ (31). Îñòàåòñÿ
íåðåøåííûì âîïðîñ, ïî÷åìó áèòåðíàðíîå ÷èñëî bt m( ) óðîâíÿ k íå ìîæåò èìåòü
íåòðèâèàëüíîãî ïîëîæèòåëüíîãî äåëèòåëÿ âèäà 2 3y k
, ãäå y m� deg 2 ( ) .
ÇÀÊËÞ×ÅÍÈÅ
 òåîðåìå 1 óäàëîñü ðàçáèòü êîðíåâûå ÷èñëà ïî óðîâíÿì. Íîìåð óðîâíÿ ïîêà-
çûâàåò ÷èñëî èòåðàöèé ôóíêöèè F , íåîáõîäèìûõ äëÿ äîñòèæåíèÿ íóëÿ. Îòìå-
òèì, ÷òî êîðíåâûå ÷èñëà íà ðàçíûõ óðîâíÿõ ïîäîáíî íàòóðàëüíûì ÷èñëàì ðàç-
ëè÷íîé âàëåíòíîñòè âçàèìíî íå ïåðåñåêàþòñÿ. Ñ ïîìîùüþ àääèòèâíîé ëåììû
ýòó èåðàðõèþ óäàåòñÿ ïåðåíåñòè íà ÷èñëà Áîìà–Çîíòà÷÷è. Çäåñü íîìåð óðîâíÿ
óêàçûâàåò íà ÷èñëî èòåðàöèé ôóíêöèè F , äîñòàòî÷íîå äëÿ äîñòèæåíèÿ åäèíè÷-
íîãî êëàññà. Îäíàêî ÷èñëà Áîìà–Çîíòà÷÷è îáðàçóþò âîçðàñòàþùóþ èåðàðõèþ.
Íóìåðàöèÿ «óñïåøíûõ» òðàåêòîðèé íàòóðàëüíûìè ÷èñëàìè ñ ïîìîùüþ ñòå-
ïåíåé äâîéêè ìîæåò ïîêàçàòüñÿ íåîáû÷íîé. Äåéñòâèòåëüíî, íà ïåðâûé âçãëÿä êà-
æåòñÿ, ÷òî äîñòèæåíèå åäèíè÷íîãî êëàññà çàâèñèò ëèøü îò íå÷åòíûõ ÷èñåë äàííî-
ãî ðÿäà. Òåì íå ìåíåå â ñëó÷àå óñïåøíîãî îêîí÷àíèÿ ïðîöåññà ìîæíî ñ ïîìîùüþ
ñòåïåíåé äâîéêè âîññòàíîâèòü èñõîäíîå ÷èñëî, à çíà÷èò, è âñþ òðàåêòîðèþ. Ýòî
ñâèäåòåëüñòâóåò î íàëè÷èè ñâÿçè ìåæäó ãîðèçîíòàëüíûì è âåðòèêàëüíûì íàïðàâ-
ëåíèÿìè â òàáëèöå S , êîòîðàÿ îïðåäåëÿåòñÿ èç (16).
Ñëåäóåò îòìåòèòü, ÷òî ïîëó÷åíû âïå÷àòëÿþùèå ðåçóëüòàòû íà âîçìîæíûé
ðàçìåð öèêëà, êîòîðûé îêàçûâàåòñÿ àñòðîíîìè÷åñêèì [2]. Ýòè ðåçóëüòàòû
îñíîâàíû íà òîíêîì ïðèáëèæåíèè èððàöèîíàëüíîãî ÷èñëà log ( )2 3 ðàöèîíàëüíû-
ìè äðîáÿìè, à òàêæå íà òîì, ÷òî âîçìîæíàÿ âåëè÷èíà öèêëè÷åñêîãî íàòóðàëüíî-
ãî ÷èñëà äîëæíà áûòü î÷åíü áîëüøîé. Îäíàêî ãëàâíûé âîïðîñ, íà êîòîðûé ïðåä-
ñòîèò åùå îòâåòèòü: ïî÷åìó áèòåðíàðíîå ÷èñëî bt m( ) óðîâíÿ k íå ìîæåò èìåòü
íåòðèâèàëüíîãî ïîëîæèòåëüíîãî äåëèòåëÿ âèäà 2 3y k
, ãäå y m� deg 2 ( ).
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. L a g a r i a s J . The 3 1x � problem and its generalization // American Mathematical Monthly. —
1985. — 92, N 1. — P. 3–23.
2. C h a m b e r l a n d M . An update on the 3 1x � problem // Butletti de la Societat Catalana de Mathe-
matiques. — 2003. — 18. — P. 19–45.
3. A k i n E . Why is the 3 1x � problem hard? // Contemp. Math. — 2004. — 356. — P. 1–20.
4. L a g a r i a s J . 3 1x � problem annotated bibliography. — www.research.att.com /~jc1/doc/3x+1bib.ps.
5. L a g a r i a s J . The ultimate challenge: the 3 1x � problem. — N.Y.: AMS, 2010. — 344 p.
6. Õ à ð à ð è Ô . Òåîðèÿ ãðàôîâ. — Ì.: Ìèð, 1973. — 300 ñ.
7. Ð û ñ ö î â È . Ê . Ïðîáëåìà ìîðòàëüíîñòè è àôôèííûå àâòîìàòû // Êèáåðíåòèêà è ñèñòåìíûé
àíàëèç. — 2008. — ¹ 2. — Ñ. 24–29.
8. T e r r a s R . A stopping time problem on the positive integers // Acta Arithmetica. — 1976. — 30.
— P. 241–252.
9. C a d o g a n C . A solution of the 3 1x � problem // Caribbean J. Math. and Comput. Sci. — 2006. —
13. — P. 1–11.
10. B o h m C . , S o n t a c c h i G . On the existence of cycles of given length in integer sequence // Atti
della Accademia Nazionale dei Lincei, Classe di Scienze Fisiche, Matematiche e Naturali. — 1978.
— 64, N 2. — P. 260–264.
11. À í è ñ è ì î â À .  . Ïðåäñòàâëåíèå ÷èñåë â ñìåøàííîì áàçèñå (2 ,3) // Êèáåðíåòèêà è ñèñòåì-
íûé àíàëèç. — 2009. — ¹ 4. — Ñ. 3–18.
12. À é å ð ë å í ä Ê . , Ð î ó ç å í Ì . Êëàññè÷åñêîå ââåäåíèå â ñîâðåìåííóþ òåîðèþ ÷èñåë. — Ì.:
Ìèð, 1987. — 415 ñ.
Ïîñòóïèëà 10.09.2012
46 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
|
| id | nasplib_isofts_kiev_ua-123456789-86232 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T17:22:46Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Рысцов, И.К. 2015-09-10T18:24:59Z 2015-09-10T18:24:59Z 2013 Несколько замечаний о проблеме Коллатца / И.К. Рысцов // Кибернетика и системный анализ. — 2013. — Т. 49, № 3. — С. 32-46. — Бібліогр.: 12 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/86232 519.713.2 Розглянуто гіпотезу Коллатца (3x +1 проблема). Запропоновано нову форму функції Коллатца, яку можна досліджувати аналітично. За допомогою афінних автоматів досліджено структуру ядра цієї функції і на її основі побудовано зростаючу ієрархію чисел Бома–Зонтаччі. Введено також систему кодування успішних траєкторій, які складаються з ітерацій функції Коллатца, натуральними числами і показано, що будь-яке натуральне число є кодом деякої траєкторії. The Collatz conjecture (the 3x +1 problem) is considered in the paper. A new form of the Collatz function is proposed, which can be studied analytically. The structure of the core of this function is analyzed by affine automata and used to construct an increasing hierarchy of Bohm–Zontacchi numbers. Successful trajectories of Collatz function iterations are coded by natural numbers and any natural number is shown to be a code of some trajectory. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Несколько замечаний о проблеме Коллатца Декілька зауважень щодо проблеми Коллатца Some remarks about the Collatz problem Article published earlier |
| spellingShingle | Несколько замечаний о проблеме Коллатца Рысцов, И.К. Кибернетика |
| title | Несколько замечаний о проблеме Коллатца |
| title_alt | Декілька зауважень щодо проблеми Коллатца Some remarks about the Collatz problem |
| title_full | Несколько замечаний о проблеме Коллатца |
| title_fullStr | Несколько замечаний о проблеме Коллатца |
| title_full_unstemmed | Несколько замечаний о проблеме Коллатца |
| title_short | Несколько замечаний о проблеме Коллатца |
| title_sort | несколько замечаний о проблеме коллатца |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/86232 |
| work_keys_str_mv | AT ryscovik neskolʹkozamečaniioproblemekollatca AT ryscovik dekílʹkazauvaženʹŝodoproblemikollatca AT ryscovik someremarksaboutthecollatzproblem |