Внутре гипотезы Коллатца

waxtep · 07/01/16 1427 Аязьма

Кажется, это что-то сезонное, по крайней мере я тоже маньячу в указанную гипотезу пару недель, независимо от появившихся недавно тем.
Не стал присоединяться к теме уважаемого Dmitriy40, поскольку интересуюсь частным вопросом: для данного натурального $n$ можно ли "легко" построить (хоть какое-то) натуральное нечетное $R_n$ , которое "свалится в единицу" ровно за $n$ утроений? Далее попробую уточнить.

Будем рассматривать только нечетные натуральные $R$ , и за один шаг считать такое преобразование $R\rightarrow(3R+1)/2^m$ , что справа будет стоять обезжиренное так же нечетное натуральное число. Определим функцию $C(R)=n$ , показывающую, за сколько шагов ( $n$ ) нечетное натуральное $R$ придет к единице. Понятно, что $C(1)=0, x\neq1:C(4x+1)=C(x), C\left(\frac13(2^{4+2a_1}-1)\right)=1$ , и уже придется немного потрудиться, чтобы получить, что $C(R_2)=2$ для $R_2=\frac19\left(2^{5+6b_1+2a_2}-2^{1+2a_2}-3\right)$ или $R_2=\frac19\left(2^{10+6b_1+2a_2}-2^{2+2a_2}-3\right)$ . Дальше еще тяжелее, один из вариантов (есть и другие) $R_3$ выглядит так: $R_3=\frac1{27}\left(2^{10+18c_1+6b_2+2a_3}-2^{6+6b_2+2a_3}-3\cdot2^{1+2a_3}-3^2\right)$ (здесь $a,b,c$ с индексами - неотрицательные целые). Можно написать общую формулу для нечетного $R_n$ , приходящего к единице за $n$ утроений: $R_n=\frac1{3^n}\left(2^{\sum\limits_{i=1}^{n}{m_i}}-\sum\limits_{i=2}^{n+1}{3^{i-2}\cdot2^{\sum\limits_{j=i}^n{m_j}}}}\right)$ Если для каких-то натуральных $m_i,i=1,2\ldots,{n}$ полученное $R_n$ натурально - то мы нашли то, что хотели. Если. Какие попало $m_i$ не годятся, в общем случае надо решать диофантово уравнение сомнительного вида о $n+1$ неизвестных. А есть ли какой-то простой рецепт для нахождения хотя бы одного $R_n$ ? Типа $m=(4,3,2,1,1,1,1,\ldots,1,1,{x})$ или $m=(4,3,2,1,1,1,1,\ldots,1,1,x,y)$ (здесь $m$ обозначает последовательность $m_i,i=1,2,\ldots,{n}$ ). Хочется записать аналитически $m$ для данного $n$ , без навороченных вычислений и привлечения компьютера. Возможно ли?

И еще один родственный вопрос: если мы зададимся задачей найти не какое попало $R_n$ , а минимальное для данного $n$ , верно ли, что для него всегда $m_1=4$ ?

Еще чуть добавлю: вот минимальные $R_n$ : A092893; и, например, для $C(27)=41$ неверно, что $m_2=3$ , для него $m_2=5:27=\frac1{3^{41}}(2^{70}-2^{66}-3\cdot2^{61}-\ldots-3^{40})$ .

Dmitriy40 · 20/08/14 11214 Россия, Москва

waxtep в сообщении #1617495 писал(а):

И еще один родственный вопрос: если мы зададимся задачей найти не какое попало $R_n$ , а минимальное для данного $n$ , верно ли, что для него всегда $m_1=4$ ?

Для всех 300 значений из OEIS это так.
Но концовка продолжает меняться, даже в следующем значении: $13 \to 5 \to 1$ или $53 \to 5 \to 1$ , так что не уверен что когда-то не может поменяться и предпоследняя $5$ (и соответственно $m_1$ ).

waxtep в сообщении #1617495 писал(а):

Типа $m=(4,3,2,1,1,1,1,\ldots,1,1,{x})$ или $m=(4,3,2,1,1,1,1,\ldots,1,1,x,y)$ (здесь $m$ обозначает последовательность $m_i,i=1,2,\ldots,{n}$ ).

Если Вы нумеруете $m_i$ в порядке переходов от $1$ к исходному $R$ чтобы последним применённым было именно $m_1$ , тогда при записи вектора $m=(m_1,m_2,\ldots,m_{n-1},m_n)$ применять их к исходному $R$ придётся справа налево, что несколько запутывает. Так что предлагаю вектор записывать в обратном порядке, $m=(m_n,m_{n-1},\ldots,m_2,m_1)$ , аналогично записи десятичных чисел, тогда применять к $R$ его можно слева направо и после применения $m_1$ и получится $1$ , что совпадает с записью переходов/преобразований $R \to R_n \to R_{n-1} \to R_2 \to R_1=1$ . Так что вектор $m=(4,3,2,1,1,1,1,\ldots,1,1,x,y)$ будет выглядеть как $m=(y,x,1,1,\ldots,1,1,1,1,2,3,4)$ . Далее я пользуюсь именно такой записью.

Насчёт построения допустимого вектора $m_i$ , я бы применил анализ по модулю $3$ в порядке увеличения индекса.
Для единственного $(m_1)$ последнее (и единственное) преобразование выглядит как $R=(2^{m_1}-1)/3$ , а значит должно выполняться $2^{m_1}=1\mod3$ , что возможно только для чётных $m_1$ .
Для вектора $m=(m_2,m_1)$ выражение сложнее, условие $R=((2^{m_1}-1)/3\cdot2^{m_2}-1)/3\in \mathbb N$ снимает ограничения на $m_2$ , а условие на $m_1$ распадается на два в зависимости от чётности $m_2$ .
Для вектора из трёх $m=(m_3,m_2,m_1)$ из условия $R=(((2^{m_1}-1)/3\cdot2^{m_2}-1)/3\cdot2^{m_3}-1)/3\in \mathbb N$ ограничений на $m_3,m_2$ не образуется, только на $m_1$ (если не ошибаюсь, 6 вариантов).
Можно аналогично предположить что для вектора любой длины $n$ условие будет только на $m_1$ (в зависимости от остальных $m_i$ ), остальные же $m_{i=n\ldots2}$ могут быть произвольными и всегда давать некоторое допустимое $R$ .

Опять же если не ошибаюсь, то минимальное $R_n$ получается при минимальной $\sum m_i$ .

Dmitriy40 · 20/08/14 11214 Россия, Москва

Dmitriy40 в сообщении #1617499 писал(а):

waxtep в сообщении #1617495 писал(а):

И еще один родственный вопрос: если мы зададимся задачей найти не какое попало $R_n$ , а минимальное для данного $n$ , верно ли, что для него всегда $m_1=4$ ?

Для всех 300 значений из OEIS это так.
Но концовка продолжает меняться, даже в следующем значении: $13 \to 5 \to 1$ или $53 \to 5 \to 1$ , так что не уверен что когда-то не может поменяться и предпоследняя $5$ (и соответственно $m_1$ ).

Написал прогу на асме (на PARI/GP очень уж медленно, десяток тысяч в секунду), запустил, она за 13 минут смогла досчитать до 23e9 (потом промежуточное нечётное число не влазит в регистр, т.е. больше $2^{64}$ ), отклонений от правила $16\to1$ не обнаружено. Вот продолжение данных из OEIS (все длины до 300 прога считает всего 7с):

код: [ скачать ] [ спрятать ]

Используется синтаксис Text

165276159 -> ... -> 16 -> 1

203875591 -> ... -> 16 -> 1

145324775 -> ... -> 16 -> 1

96883183 -> ... -> 16 -> 1

129177577 -> ... -> 16 -> 1

172236769 -> ... -> 16 -> 1

229649025 -> ... -> 16 -> 1

306198703 -> ... -> 16 -> 1

408264937 -> ... -> 16 -> 1

544353249 -> ... -> 16 -> 1

369953007 -> ... -> 16 -> 1

483869551 -> ... -> 16 -> 1

644034303 -> ... -> 16 -> 1

430106267 -> ... -> 16 -> 1

286737511 -> ... -> 16 -> 1

382316681 -> ... -> 16 -> 1

254877787 -> ... -> 16 -> 1

339837049 -> ... -> 16 -> 1

453116065 -> ... -> 16 -> 1

604154753 -> ... -> 16 -> 1

402769835 -> ... -> 16 -> 1

268513223 -> ... -> 16 -> 1

179008815 -> ... -> 16 -> 1

477356841 -> ... -> 16 -> 1

636475787 -> ... -> 16 -> 1

424317191 -> ... -> 16 -> 1

282878127 -> ... -> 16 -> 1

754341673 -> ... -> 16 -> 1

1005788897 -> ... -> 16 -> 1

670525931 -> ... -> 16 -> 1

447017287 -> ... -> 16 -> 1

596023049 -> ... -> 16 -> 1

397348699 -> ... -> 16 -> 1

529798265 -> ... -> 16 -> 1

353198843 -> ... -> 16 -> 1

235465895 -> ... -> 16 -> 1

156977263 -> ... -> 16 -> 1

209303017 -> ... -> 16 -> 1

279070689 -> ... -> 16 -> 1

744188505 -> ... -> 16 -> 1

992251339 -> ... -> 16 -> 1

1323001785 -> ... -> 16 -> 1

882001191 -> ... -> 16 -> 1

2352003177 -> ... -> 16 -> 1

3097885415 -> ... -> 16 -> 1

2065256943 -> ... -> 16 -> 1

2741096351 -> ... -> 16 -> 1

1827397567 -> ... -> 16 -> 1

1224961663 -> ... -> 16 -> 1

1633282217 -> ... -> 16 -> 1

1088854811 -> ... -> 16 -> 1

725903207 -> ... -> 16 -> 1

483935471 -> ... -> 16 -> 1

322623647 -> ... -> 16 -> 1

215082431 -> ... -> 16 -> 1

143388287 -> ... -> 16 -> 1

95592191 -> ... -> 16 -> 1

63728127 -> ... -> 16 -> 1

169941673 -> ... -> 16 -> 1

226588897 -> ... -> 16 -> 1

302118529 -> ... -> 16 -> 1

402824705 -> ... -> 16 -> 1

268549803 -> ... -> 16 -> 1

716132809 -> ... -> 16 -> 1

954843745 -> ... -> 16 -> 1

1273124993 -> ... -> 16 -> 1

848749995 -> ... -> 16 -> 1

1131666663 -> ... -> 16 -> 1

1508888879 -> ... -> 16 -> 1

1005925919 -> ... -> 16 -> 1

670617279 -> ... -> 16 -> 1

1788312745 -> ... -> 16 -> 1

2384416993 -> ... -> 16 -> 1

3179222657 -> ... -> 16 -> 1

2119481771 -> ... -> 16 -> 1

1412987847 -> ... -> 16 -> 1

3767967593 -> ... -> 16 -> 1

2511978395 -> ... -> 16 -> 1

1674652263 -> ... -> 16 -> 1

4465739369 -> ... -> 16 -> 1

2977159579 -> ... -> 16 -> 1

3969546105 -> ... -> 16 -> 1

10585456281 -> ... -> 16 -> 1

7056970855 -> ... -> 16 -> 1

9409294471 -> ... -> 16 -> 1

6272863003 -> ... -> 16 -> 1

8363817307 -> ... -> 16 -> 1

11151756409 -> ... -> 16 -> 1

7434504283 -> ... -> 16 -> 1

4956336199 -> ... -> 16 -> 1

6608448251 -> ... -> 16 -> 1

4405632167 -> ... -> 16 -> 1

2937088111 -> ... -> 16 -> 1

3916117481 -> ... -> 16 -> 1

2610744987 -> ... -> 16 -> 1

6961986633 -> ... -> 16 -> 1

9282648843 -> ... -> 16 -> 1

--- Дальше есть пропуски

16502486823 -> ... -> 16 -> 1

22003315783 -> ... -> 16 -> 1

19118164135 -> ... -> 16 -> 1

16993923675 -> ... -> 16 -> 1

11590223975 -> ... -> 16 -> 1

7726815983 -> ... -> 16 -> 1

5151210655 -> ... -> 16 -> 1

6868280873 -> ... -> 16 -> 1

4578853915 -> ... -> 16 -> 1

6105138553 -> ... -> 16 -> 1

8140184737 -> ... -> 16 -> 1

10853579649 -> ... -> 16 -> 1

14471439535 -> ... -> 16 -> 1

19295252713 -> ... -> 16 -> 1

17625062639 -> ... -> 16 -> 1

11750041759 -> ... -> 16 -> 1

15666722345 -> ... -> 16 -> 1

10444481563 -> ... -> 16 -> 1

13925975417 -> ... -> 16 -> 1

9283983611 -> ... -> 16 -> 1

6189322407 -> ... -> 16 -> 1

16504859753 -> ... -> 16 -> 1

11003239835 -> ... -> 16 -> 1

7335493223 -> ... -> 16 -> 1

4890328815 -> ... -> 16 -> 1

13040876841 -> ... -> 16 -> 1

17387835787 -> ... -> 16 -> 1

18318049223 -> ... -> 16 -> 1

12212032815 -> ... -> 16 -> 1

19298027167 -> ... -> 16 -> 1

20646664519 -> ... -> 16 -> 1

18352590683 -> ... -> 16 -> 1

12235060455 -> ... -> 16 -> 1

21751218587 -> ... -> 16 -> 1

14500812391 -> ... -> 16 -> 1

19334416521 -> ... -> 16 -> 1

20056791791 -> ... -> 16 -> 1

13371194527 -> ... -> 16 -> 1

17828259369 -> ... -> 16 -> 1

-- 12.11.2023, 13:14 --

Раз до 23e9 все концовки только $m_1=4$ , значит не может быть $4<m_1<37$ - иначе $R_1\le(2^{36}-1)/3\approx22.9\cdot10^9$ , а они все проверены. Как-то уже слабо верится что для минимального $R_n$ может быть такое большое $m_1$ (фактически степень двойки).

waxtep · 07/01/16 1427 Аязьма

Dmitriy40, спасибо, очень интересно! И Вы меня натолкнули на мысль, как найти какое-нибудь $R_n$ , кажется, это работает. Будем искать его в виде $R_n=2^{n-1}\cdot{x}-1$ Легко убедиться, что один шаг меняет двойку на тройку перед $x$ , и пройдя $n-1$ шаг мы придем к $R_1=3^{n-1}\cdot{x}-1$ Чтобы оно за один шаг свалилось в единицу требуется, чтобы выполнялось $3^{n-1}\cdot{x}-1=\frac13(4^{p+2}-1)$ для какого-то целого неотрицательного $p$ . Видно, что $x=4a+2$ и требуется найти такое $p$ , чтобы было $2^{2p+3}\equiv-1\pmod{3^n}$ А это ведь, если не ошибаюсь, всегда возможно.

Способ, конечно, расточительный, выдает большие $R_n$ , далекие от минимальных, поскольку в общем случае подходящее значение $p$ может оказаться в районе $3^n$ . Например, для $n=4$ наименьшее подходящее $p=12$ и $R_4=26512143$ (при $x=\dfrac{2^{28}+2}{3^4}=3314018$ )

А, ведь даже так: $2^{3^{n-1}}\equiv-1\pmod{3^n}$ и тогда можно взять для $n>1$ $R_n=\left(\frac23\right)^n\cdot\left(2^{3^{n-1}}+1\right)-1$

Dmitriy40 · 20/08/14 11214 Россия, Москва

Чуть переписал прогу и за 14ч досчиталось до 1e12, вот продолжение таблицы для OEIS:

код: [ скачать ] [ спрятать ]

Используется синтаксис Text

9282648843 -> ... -> 16 -> 1

24753730235 -> ... -> 16 -> 1

16502486823 -> ... -> 16 -> 1

22003315783 -> ... -> 16 -> 1

28677246203 -> ... -> 16 -> 1

19118164135 -> ... -> 16 -> 1

25490885513 -> ... -> 16 -> 1

16993923675 -> ... -> 16 -> 1

11590223975 -> ... -> 16 -> 1

7726815983 -> ... -> 16 -> 1

5151210655 -> ... -> 16 -> 1

6868280873 -> ... -> 16 -> 1

4578853915 -> ... -> 16 -> 1

6105138553 -> ... -> 16 -> 1

8140184737 -> ... -> 16 -> 1

10853579649 -> ... -> 16 -> 1

14471439535 -> ... -> 16 -> 1

19295252713 -> ... -> 16 -> 1

25727003559 -> ... -> 16 -> 1

17625062639 -> ... -> 16 -> 1

11750041759 -> ... -> 16 -> 1

15666722345 -> ... -> 16 -> 1

10444481563 -> ... -> 16 -> 1

13925975417 -> ... -> 16 -> 1

9283983611 -> ... -> 16 -> 1

6189322407 -> ... -> 16 -> 1

16504859753 -> ... -> 16 -> 1

11003239835 -> ... -> 16 -> 1

7335493223 -> ... -> 16 -> 1

4890328815 -> ... -> 16 -> 1

13040876841 -> ... -> 16 -> 1

17387835787 -> ... -> 16 -> 1

23183781049 -> ... -> 16 -> 1

30911708065 -> ... -> 16 -> 1

41215610753 -> ... -> 16 -> 1

27477073835 -> ... -> 16 -> 1

18318049223 -> ... -> 16 -> 1

12212032815 -> ... -> 16 -> 1

32565420841 -> ... -> 16 -> 1

43420561121 -> ... -> 16 -> 1

28947040747 -> ... -> 16 -> 1

19298027167 -> ... -> 16 -> 1

25730702889 -> ... -> 16 -> 1

34841246377 -> ... -> 16 -> 1

45743471803 -> ... -> 16 -> 1

30969996779 -> ... -> 16 -> 1

20646664519 -> ... -> 16 -> 1

27528886025 -> ... -> 16 -> 1

18352590683 -> ... -> 16 -> 1

12235060455 -> ... -> 16 -> 1

32626827881 -> ... -> 16 -> 1

21751218587 -> ... -> 16 -> 1

14500812391 -> ... -> 16 -> 1

19334416521 -> ... -> 16 -> 1

50768754217 -> ... -> 16 -> 1

67691672289 -> ... -> 16 -> 1

45127781531 -> ... -> 16 -> 1

30085187687 -> ... -> 16 -> 1

20056791791 -> ... -> 16 -> 1

13371194527 -> ... -> 16 -> 1

17828259369 -> ... -> 16 -> 1

47542024985 -> ... -> 16 -> 1

31694683323 -> ... -> 16 -> 1

84519155529 -> ... -> 16 -> 1

112692207371 -> ... -> 16 -> 1

75128138247 -> ... -> 16 -> 1

200341701993 -> ... -> 16 -> 1

133561134663 -> ... -> 16 -> 1

346590066283 -> ... -> 16 -> 1

237442017179 -> ... -> 16 -> 1

158294678119 -> ... -> 16 -> 1

211059570825 -> ... -> 16 -> 1

281412761247 -> ... -> 16 -> 1

349448440831 -> ... -> 16 -> 1

250144676519 -> ... -> 16 -> 1

166763117679 -> ... -> 16 -> 1

222350823583 -> ... -> 16 -> 1

292237823835 -> ... -> 16 -> 1

383428016575 -> ... -> 16 -> 1

263526902011 -> ... -> 16 -> 1

351369202681 -> ... -> 16 -> 1

468492270241 -> ... -> 16 -> 1

575623135935 -> ... -> 16 -> 1

416437573547 -> ... -> 16 -> 1

277625049031 -> ... -> 16 -> 1

370166732041 -> ... -> 16 -> 1

254479316383 -> ... -> 16 -> 1

329037095147 -> ... -> 16 -> 1

219358063431 -> ... -> 16 -> 1

584954835817 -> ... -> 16 -> 1

402140154283 -> ... -> 16 -> 1

519959854059 -> ... -> 16 -> 1

683388232127 -> ... -> 16 -> 1

455592154751 -> ... -> 16 -> 1

303728103167 -> ... -> 16 -> 1

202485402111 -> ... -> 16 -> 1

539961072297 -> ... -> 16 -> 1

719948096395 -> ... -> 16 -> 1

486912565695 -> ... -> 16 -> 1

639953863463 -> ... -> 16 -> 1

426635908975 -> ... -> 16 -> 1

568847878633 -> ... -> 16 -> 1

758463838177 -> ... -> 16 -> 1

1011285117569 -> ... -> 16 -> 1

674190078379 -> ... -> 16 -> 1

881715740415 -> ... -> 16 -> 1

Отклонений от правила $16\to1$ по прежнему нет. Значит не бывает $4<m_1<42$ (для минимальных $R_n$ ).

waxtep в сообщении #1617622 писал(а):

Способ, конечно, расточительный, выдает большие $R_n$ , далекие от минимальных,

Именно, Вы же хотели минимальные $R_n$ , прочих-то навалом:

(Много текста)

Код:

? forstep(x0=3,1000,2, x=x0; n=0; while(x>1, x=3*x+1; n++; xx=x; x>>=valuation(x,2); ); if(n==4, print(n,": ",x0," -> ... -> ",xx," -> 1");); );
11 -> ... -> 16 -> 1
23 -> ... -> 16 -> 1
45 -> ... -> 16 -> 1
93 -> ... -> 16 -> 1
181 -> ... -> 16 -> 1
201 -> ... -> 1024 -> 1
369 -> ... -> 16 -> 1
373 -> ... -> 16 -> 1
401 -> ... -> 256 -> 1
403 -> ... -> 1024 -> 1
725 -> ... -> 16 -> 1
739 -> ... -> 16 -> 1
753 -> ... -> 16 -> 1
803 -> ... -> 256 -> 1
805 -> ... -> 1024 -> 1

? forstep(x0=3,1000,2, x=x0; n=0; while(x>1, x=3*x+1; n++; xx=x; x>>=valuation(x,2); ); if(xx>16, print(n,": ",x0," -> ... -> ",xx," -> 1");); );
21 -> ... -> 64 -> 1
75 -> ... -> 256 -> 1
85 -> ... -> 256 -> 1
113 -> ... -> 256 -> 1
151 -> ... -> 1024 -> 1
201 -> ... -> 1024 -> 1
227 -> ... -> 1024 -> 1
267 -> ... -> 256 -> 1
301 -> ... -> 256 -> 1
341 -> ... -> 1024 -> 1
401 -> ... -> 256 -> 1
403 -> ... -> 1024 -> 1
423 -> ... -> 1024 -> 1
453 -> ... -> 256 -> 1
475 -> ... -> 256 -> 1
535 -> ... -> 256 -> 1
537 -> ... -> 1024 -> 1
605 -> ... -> 1024 -> 1
633 -> ... -> 256 -> 1
635 -> ... -> 1024 -> 1
713 -> ... -> 256 -> 1
715 -> ... -> 1024 -> 1
803 -> ... -> 256 -> 1
805 -> ... -> 1024 -> 1
847 -> ... -> 1024 -> 1
891 -> ... -> 1024 -> 1
909 -> ... -> 1024 -> 1
951 -> ... -> 256 -> 1
953 -> ... -> 1024 -> 1
955 -> ... -> 1024 -> 1

? forstep(x0=3,1e6,2, x=x0; n=0; while(x>1, x=3*x+1; n++; xx=x; x>>=valuation(x,2); ); if(xx>2^17, print(n,": ",x0," -> ... -> ",xx," -> 1");); );
87381 -> ... -> 262144 -> 1
184111 -> ... -> 1048576 -> 1
245481 -> ... -> 1048576 -> 1
276167 -> ... -> 1048576 -> 1
349525 -> ... -> 1048576 -> 1
368223 -> ... -> 1048576 -> 1
414251 -> ... -> 1048576 -> 1
436411 -> ... -> 1048576 -> 1
466033 -> ... -> 1048576 -> 1
490963 -> ... -> 1048576 -> 1
517227 -> ... -> 1048576 -> 1
552335 -> ... -> 1048576 -> 1
581881 -> ... -> 1048576 -> 1
621377 -> ... -> 1048576 -> 1
654617 -> ... -> 1048576 -> 1
736445 -> ... -> 1048576 -> 1
775841 -> ... -> 1048576 -> 1
828503 -> ... -> 1048576 -> 1
872823 -> ... -> 1048576 -> 1
919515 -> ... -> 1048576 -> 1
932067 -> ... -> 4194304 -> 1
981925 -> ... -> 1048576 -> 1

\\Первое нетривиальное (n>1) m_1:
? q=vector(100); forstep(x0=3,1e7,2, x=x0; n=0; while(x>1, x=3*x+1; n++; xx=valuation(x,2); x>>=xx;); if(n>1 && q[xx]==0, q[xx]=n; print(n,": ",x0," -> ... -> 2^",xx," -> 1");); );
3 -> ... -> 2^4 -> 1
75 -> ... -> 2^8 -> 1
151 -> ... -> 2^10 -> 1
7281 -> ... -> 2^14 -> 1
14563 -> ... -> 2^16 -> 1
184111 -> ... -> 2^20 -> 1
932067 -> ... -> 2^22 -> 1

Впрочем задачу построения хоть какого-то $R_n$ по $n$ без тупого перебора Вы решили, что и требовалось в общем-то, могу только поздравить.

waxtep · 07/01/16 1427 Аязьма

Dmitriy40 в сообщении #1617524 писал(а):

Раз до 23e9 все концовки только $m_1=4$ , значит не может быть $4<m_1<37$ - иначе $R_1\le(2^{36}-1)/3\approx22.9\cdot10^9$ , а они все проверены. Как-то уже слабо верится что для минимального $R_n$ может быть такое большое $m_1$ (фактически степень двойки).

Dmitriy40, а как Вы получаете такую оценку, не соображу? Вот мы проверили все нечетные натуральные не превышающие $2.3\cdot10^{10}$ и получили минимальное $R_{456}\approx1.78\cdot10^{10}$ . Почему минимальное $R_{457}$ или $R_{458}$ и т.п. не может оказаться чуть больше $2.3\cdot10^{10}$ и "прилететь" к какому-либо $R_1<2.3\cdot10^{10}$ с $m_1$ отличным от четверки?

Dmitriy40 · 20/08/14 11214 Россия, Москва

waxtep
О-о-о-о! А Вы правы, я похоже зарапортовался. Посчитал что любое $R_1$ обязано совпадать с каким-либо минимальным $R_n$ и тогда вывод верен, но вообще-то да, с какой стати быть такому совпадению ... :facepalm:

Был неправ с ограничением на $m_1$ .

Dmitriy40 · 20/08/14 11214 Россия, Москва

Посмотрел на статистику $m_i$ для всех вот этих минимальных $R_n$ , интересно:
1. За исключением первых двух все оканчиваются или $1,5,4$ или $2,3,4$ , других вариантов так и не нашлось.
2. $m_n$ бывает или $1$ или $2$ , других не обнаружено (за исключением $m_{n=1}=4$ ).
3. Сумма всех $\sum m_i$ растёт монотонно от $n$ и для $R_{503}=1567494649627$ она составляет уже $\sum m_i =838$ , т.е. среди $m_i$ достаточно много не единичных значений.
4. До $n=503$ встретились варианты $m_i\in\{1,2,3,4,5,6,7,8,9,10,12,15\}$ , первое $m_i=10$ для $R_{197}=1501353$ , первое $m_i=12$ для $R_{348}=1224961663$ , первое (и пока единственное) $m_i=15$ для $R_{502}=1210271371431$ .
5. Встретились непрерывные цепочки единичных $m_{i\ldots j}=1$ длиной до $14$ включительно, такой длины только у $R_{478}=575623135935$ , цепочки $m_{i\ldots j}=2$ встретились длиной до $7$ включительно, такой длины только у $R_{178}=3216799$ , цепочки $m_{i\ldots j}=3$ бывают длиной до $3$ , цепочки $m_{i\ldots j}=4,5,6$ длиной до $2$ , остальные варианты не "объединяются".
6. Максимальная сумма непрерывной цепочки не единичных $m_{i \ldots j}\ne1$ у варианта $m_{i \ldots j}=(3,4,2,5,9,2,3)$ (если не наврал, проверял глазками).
7. Концовки очень часто совпадают, причём весьма нередко разные буквально лишь несколько первых $m_i$ . Т.е. $R_i$ быстро попадают в весьма ограниченное множество и далее всё одинаково. Например 45 разных $R_n$ сваливаются в $R_{415}=17625062639$ и потом одинаково идут к $R_4=11$ .
8. Достаточно часто (175 раз из 503) следующее $R_n$ получается как $R_n=(R_{n-1}\cdot2^1-1)/3$ , т.е. новое $m_n=1$ , а все остальные $m_i$ те же. И ещё 109 раз из 503 новое $m_n=2$ при тех же остальных $m_i$ . В сумме получается даже больше половины случаев. Из оставшихся 124 раза $2^2 > \frac{3 R_n + 1}{R_{n-1}} > 2^1$ и 95 раз $\frac{3 R_n + 1}{R_{n-1}} > 2^2$ и только 1 раз $\frac{3 R_n + 1}{R_{n-1}} > 2^4$ (переход $R_2 \to R_3$ ). Т.е. в 56% $R_n$ вычисляется прямо (но недоказуемо), и в 81% (или в 99.8% или даже 100%) можно ограничить $R_n$ сверху (и тоже недоказуемо).
0. Ну и отдельное наблюдение: только для двух значений $n=458,461$ все последующие $R_n$ строго больше всех предыдущих.

waxtep · 07/01/16 1427 Аязьма

Да, минимальные $R_n$ видимо довольно коварны, ползут к единице извилистыми маршрутами :-)

Но вот кстати:

Dmitriy40 в сообщении #1617685 писал(а):

3. Сумма всех $\sum m_i$ растёт монотонно от $n$ и для $R_{503}=1567494649627$ она составляет уже $\sum m_i =838$ , т.е. среди $m_i$ достаточно много не единичных значений

Кажется, интересно еще за такой величиной понаблюдать для минимальных $R_n$ : $k_n=\ln{R_n}+n\ln3-\sum\ind_{i=1}^{n}{m_i}\ln2$ Типа насколько хорошо соблюдается приближенное равенство $R_n\approx\frac{2^{\sum\ind_{i=1}^{n}{m_i}}}{3^n}$ и как это меняется с ростом $n$

-- 13.11.2023, 18:59 --

Кажется, ведет она себя довольно стабильно, $0.8<e^{k_n}<0.9$ для $n\leqslant503$

waxtep · 07/01/16 1427 Аязьма

(прямо посчитал я ее только точечно, для $n$ от $2$ до $17$ и для отдельных значений $41,503$ )

-- 13.11.2023, 19:28 --

Dmitriy40 в сообщении #1617685 писал(а):

1. За исключением первых двух все оканчиваются или $1,5,4$ или $2,3,4$ , других вариантов так и не нашлось.

Ну да, это намекает, что процентов десять точно будет отожрано: $\begin{array}{l} \!(2,3,4): 1-\frac1{2^4}-\frac3{2^7}-\frac{3^2}{2^9}\approx0.8965\\ \!(1,5,4): 1-\frac1{2^4}-\frac3{2^9}-\frac{3^2}{2^{10}}\approx0.9229\end{array}$ Интересно, может ли $e^{k_n}$ быть сильно меньше $0.8$ ? Это должно быть много единиц подряд ближе к концу $m$ . Ну это в общем уже какая-то нумерология у меня пошла :-)

Dmitriy40 · 20/08/14 11214 Россия, Москва

По моим вычислениям по всем $n=1\ldots506$ получается $0.7993097182802851314455912217 < e^k < 0.9375$ . Максимум при $n=1$ , а без него при $n=291$ максимум $0.9199236932856538055199217545$ ( $R_{291}=105707199, \sum m_i=488$ ), больше $0.9$ лишь при $n=1,290,291$ , минимум при $n=301$ ( $R_{301}=203875591, \sum m_i=505$ ), меньше $0.8$ для $n=292,293,296\ldots301$ .

Из них много (11шт) единиц как раз в $n=290,291$ , где максимум $e^k$ .

waxtep · 07/01/16 1427 Аязьма

Dmitriy40, спасибо за уточнения! Получается, минимальные $R_n$ действительно похожи на $2^a/3^n$ "за вычетом НДС" :-)

Ну, по крайней мере, докуда досчитано. Надо тоже не полениться и расчехлить PARI/GP для всяческих интересных опытов, видимо ближе к концу недели. Кас. статистики - а Вы случаем не считали, сколько чисел в обсчитанном диапазоне приходят к единице за $1,2,\ldots$ и т.п. шагов?

Dmitriy40 · 20/08/14 11214 Россия, Москва

Неа, не считал, это же сильно зависит от границы диапазона.
К тому же есть A006878 и A006877 - увеличение количества шагов и на каком числе происходит. Видно что до $10^{16}$ количество шагов меньше $2000$ .
До сотен миллионов статистику можно и на PARI/GP получить за разумное время (часы):

Код:

? n=vector(2000); w=0; for(x0=2,10^4-1, q=valuation(x0,2); x=x0>>q; while(x>1, x=3*x+1; t=valuation(x,2); q+=t+1; x>>=t;); n[q]++; w=max(w,q);); print(n[1..w])
[1, 1, 1, 1, 2, 2, 4, 4, 6, 6, 8, 10, 14, 17, 23, 22, 28, 36, 32, 44, 59, 46, 65, 43, 64, 94, 61, 92, 60, 81, 125, 66, 105, 142, 82, 138, 60, 107, 175, 66, 127, 78, 87, 160, 55, 108, 184, 76, 142, 47, 92, 190, 59, 123, 32, 69, 149, 44, 94, 153, 56, 118, 30, 73, 142, 40, 86, 21, 53, 122, 29, 68, 102, 42, 95, 24, 53, 111, 23, 62, 15, 34, 82, 19, 49, 13, 29, 69, 19, 46, 76, 27, 65, 20, 43, 91, 30, 58, 17, 36, 77, 26, 52, 56, 33, 62, 22, 41, 84, 25, 54, 19, 35, 72, 29, 57, 27, 44, 80, 35, 64, 115, 44, 83, 32, 63, 121, 42, 84, 29, 59, 113, 39, 75, 100, 47, 93, 24, 51, 113, 34, 72, 15, 38, 86, 21, 48, 15, 32, 66, 15, 39, 94, 22, 52, 11, 29, 70, 12, 33, 4, 15, 42, 6, 22, 56, 10, 35, 6, 19, 47, 11, 31, 6, 15, 39, 10, 23, 11, 10, 29, 3, 13, 37, 1, 12, 0, 4, 19, 1, 6, 0, 1, 11, 0, 2, 12, 1, 6, 0, 2, 9, 0, 3, 0, 1, 3, 1, 2, 3, 0, 1, 0, 1, 2, 1, 2, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 2, 0, 0, 2, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1]
time = 296 ms.
? n=vector(2000); w=0; for(x0=2,10^6-1, q=valuation(x0,2); x=x0>>q; while(x>1, x=3*x+1; t=valuation(x,2); q+=t+1; x>>=t;); n[q]++; w=max(w,q);); print(n[1..w])
[1, 1, 1, 1, 2, 2, 4, 4, 6, 6, 8, 10, 14, 18, 24, 29, 36, 44, 58, 71, 90, 112, 132, 168, 215, 238, 312, 313, 413, 548, 509, 695, 623, 822, 1128, 894, 1272, 1795, 1342, 1923, 1308, 1954, 2880, 1866, 2819, 2110, 2615, 4021, 2305, 3645, 4756, 3136, 5030, 2566, 4247, 6880, 3401, 5690, 3056, 4529, 7666, 3493, 6048, 8232, 4586, 8028, 3365, 6031, 10624, 4403, 7941, 3080, 5696, 10380, 3998, 7474, 9271, 5231, 9785, 3599, 6873, 11586, 4698, 9034, 3142, 6142, 11829, 4091, 8021, 6368, 5352, 10476, 3406, 6861, 12169, 4500, 9049, 2912, 5891, 11781, 3824, 7794, 2415, 4977, 10146, 3162, 6551, 9342, 4196, 8665, 2695, 5549, 11099, 3535, 7321, 2242, 4693, 9715, 3014, 6292, 7542, 3977, 8214, 2572, 5300, 10392, 3448, 7133, 2309, 4670, 9556, 3125, 6324, 2101, 4211, 8516, 2833, 5653, 9704, 3774, 7589, 2602, 5108, 10163, 3464, 6822, 2328, 4625, 9205, 3096, 6122, 7045, 4064, 8119, 2666, 5400, 10620, 3567, 7220, 2304, 4734, 9529, 3006, 6178, 2524, 4045, 8228, 2582, 5342, 10626, 3370, 7000, 2081, 4454, 9237, 2736, 5831, 1683, 3634, 7675, 2251, 4816, 7321, 2973, 6320, 1791, 3909, 8246, 2376, 5112, 1398, 3091, 6766, 1856, 4103, 1611, 2466, 5498, 1475, 3331, 7191, 1914, 4366, 1065, 2528, 5728, 1441, 3355, 797, 1908, 4441, 1027, 2509, 5361, 1411, 3351, 746, 1849, 4386, 1001, 2467, 534, 1354, 3299, 732, 1820, 937, 966, 2413, 497, 1318, 3252, 695, 1816, 363, 948, 2441, 503, 1303, 245, 687, 1781, 360, 956, 2345, 537, 1342, 272, 726, 1862, 386, 987, 192, 534, 1358, 283, 744, 708, 384, 1017, 191, 542, 1381, 289, 776, 139, 399, 1060, 204, 564, 101, 306, 797, 165, 416, 1035, 220, 570, 105, 297, 814, 144, 417, 65, 204, 569, 93, 282, 472, 136, 399, 58, 190, 550, 81, 261, 40, 129, 389, 67, 207, 34, 103, 297, 55, 160, 412, 80, 233, 42, 118, 335, 55, 159, 24, 78, 232, 32, 111, 226, 51, 139, 23, 66, 209, 35, 99, 20, 52, 152, 25, 68, 32, 36, 102, 14, 47, 151, 18, 65, 11, 37, 106, 15, 48, 4, 22, 73, 8, 31, 100, 17, 51, 7, 21, 68, 8, 36, 2, 15, 51, 2, 16, 12, 6, 23, 4, 15, 48, 8, 23, 2, 9, 33, 2, 11, 0, 5, 25, 1, 10, 37, 3, 15, 1, 8, 24, 3, 7, 0, 2, 11, 0, 3, 6, 0, 3, 0, 1, 9, 0, 3, 0, 2, 8, 2, 5, 0, 1, 6, 0, 2, 9, 0, 3, 0, 1, 5, 0, 2, 0, 1, 5, 0, 2, 3, 0, 1, 0, 0, 3, 0, 1, 0, 1, 4, 0, 1, 1, 1, 3, 1, 2, 6, 0, 1, 0, 1, 3, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
time = 45,553 ms.

waxtep · 07/01/16 1427 Аязьма

Dmitriy40 в сообщении #1617685 писал(а):

2. $m_n$ бывает или $1$ или $2$ , других не обнаружено (за исключением $m_{n=1}=4$ ).

Dmitriy40 в сообщении #1617685 писал(а):

8. Достаточно часто (175 раз из 503) следующее $R_n$ получается как $R_n=(R_{n-1}\cdot2^1-1)/3$ , т.е. новое $m_n=1$ , а все остальные $m_i$ те же. И ещё 109 раз из 503 новое $m_n=2$ при тех же остальных $m_i$ . В сумме получается даже больше половины случаев. Из оставшихся 124 раза $2^2 > \frac{3 R_n + 1}{R_{n-1}} > 2^1$ и 95 раз $\frac{3 R_n + 1}{R_{n-1}} > 2^2$ и только 1 раз $\frac{3 R_n + 1}{R_{n-1}} > 2^4$ (переход $R_2 \to R_3$ ). Т.е. в 56% $R_n$ вычисляется прямо (но недоказуемо), и в 81% (или в 99.8% или даже 100%) можно ограничить $R_n$ сверху (и тоже недоказуемо).

Так, а это ведь можно и доказать:

если $R_n^{\min}\equiv2\pmod3$ , то $R_{n+1}^{\min}=\frac13(2R_n^{\min}-1)$
а если $R_n^{\min}\equiv1\pmod3$ , для $R_{n+1}^{\min}$ возможны два варианта: $\frac13(4R_n^{\min}-1)$ или $\frac13(2R_n^{\operatorname{(2)}}-1)$ , где $R_n^{\operatorname{(2)}}$ - наименьшее $R_n$ , дающее двойку по модулю три
и наконец если $R_n^{\min}\equiv0\pmod3$ , то $R_{n+1}^{\min}$ это $\frac13(2R_n^{\operatorname{(2)}}-1)$ или $\frac13(4R_n^{\operatorname{(1)}}-1)$

Последний случай коварен: один Диэдр знает, во сколько раз $R_n^{\operatorname{(2)}}$ или $R_n^{\operatorname{(1)}}$ больше, чем $R_n^{\min}$ . Впрочем, в силу $C(4x+1)=C(x)$ , можно сказать, что $R_n^{\operatorname{(1)}}\leqslant4R_n^{\min}+1,R_n^{\operatorname{(2)}}\leqslant16R_n^{\min}+5$ и тогда гарантированно $R_{n+1}^{\min}\leqslant\frac{16}3R_n^{\min}+1$

waxtep · 07/01/16 1427 Аязьма

waxtep в сообщении #1617908 писал(а):

если $R_n^{\min}\equiv2\pmod3$ , то $R_{n+1}^{\min}=\frac13(2R_n^{\min}-1)$

Оказывается, можно сказать лишь следующее: если $R_n^{\min}\equiv2\pmod3$ , то $R_{n+1}^{\min}\color{blue}{\leqslant}\color{black} \frac13(2R_n^{\min}-1)$ , и в целом всюду "равно" следует заменить на "не больше". Это сохраняет верной приведенную оценку сверху для $R_{n+1}^{\min}$ , но не позволяет реализовать простой и быстрый алгоритм вычисления $R_{n+1}^{\min}$ , опирающийся только на значения $R_n^{\operatorname{(1)}}, R_n^{\operatorname{(2)}}$ . Например, $R_3^{\operatorname{(1)}}=151$ двигается по цепочке $151\rightarrow227\rightarrow341\{=\frac13(2^{10}-1)\}\rightarrow1$ , проходящей мимо минимальных $R_2^{\operatorname{(i)}}, R_1^{\operatorname{(i)}}$ , которые приводят к большему значению $R_3^{\operatorname{(1)}}=277\rightarrow13\rightarrow5\{=\frac13(2^{4}-1)\}\rightarrow1$ . Это позже прямо скажется на величине $R_{9}^{\min}$ , "простой" алгоритм для нее даст завышенное значение $89$ , вместо корректного $43$ . Я пока не осознал, это лишь единственное "вторжение", или есть постоянный риск время от времени получать величины $R_{n+1}^{\min}$ , никак не связанные с $R_n^{\operatorname{(1)}}, R_n^{\operatorname{(2)}}$ (такие числа предлагаю называть "особо коварными").

Научный форум dxdy

Правила форума

Внутре гипотезы Коллатца

Кто сейчас на конференции