Вопрос о получении любого числа

[dorofeev]

Проблему я сам придумал.Я не знаю,возможно такая проблема уже кем-либо была поставлена,но я об этом не знаю.

[grizzly]

dorofeev в сообщении #1249837 писал(а):

Проблему я сам придумал.

Супер! А я как раз собирался спросить об этом. Я специально не интересовался, но вокруг подобных вопросов ходил частенько и не разу этой задачи не встречал.

Вы не хотели бы озвучить её на более широких площадках? (math.stackexchange, например -- с очень широкой англоязычной аудиторией.) Я предполагаю, что задача из разряда сложных или вообще пока неберущихся, но формулировку распространить было бы полезно, имхо.

[dorofeev]

Спасибо за совет,Grizzly!

[fractalon]

Sonic86 в сообщении #1248700 писал(а):

Раз эта задача сложная, давайте сделаем себе задачу попроще :
Дано число $3$ и множество отображений $f_1(x)=\frac{x}{2}, f_2(x)=\frac{x-1}{2}, f_3(x)=x^2$. Надо композицией $f_j$ получить произвольное число.
Первые 2 отображения мы объединяем в $f(x)=\lfloor\frac{x}{2}\rfloor$, его итерация $f^{(k)}(x)=\lfloor\frac{x}{2^k}\rfloor$. И мы попытаемся получить все натуральные числа как $f^{(k)} \circ f_3^{(m)}(3)=\lfloor\frac{3^{2^m}}{2^k}\rfloor$.
$\lfloor\frac{x}{2^k}\rfloor$ - это просто число $x$ в двоичной системе счисления, у которого стерли справа $k$ битов. При $k=[\log_2(x)]$ имеем $\lfloor\frac{x}{2^k}\rfloor=1$. Немного не доведем итерации $f$ до конца: $k:=[\log_2(x)]-r, r\geqslant 0$, тогда $\lfloor\frac{x}{2^k}\rfloor=[2^r\cdot 2^{\{\log_2x\}}] \in [2^r; 2^{r+1})$. Если это выражение пробегает весь $[2^r; 2^{r+1})$, то задача решена.
Заметим, что если $x=3^m$ (пока не $x=3^{2^m}$), то $[2^r\cdot 2^{\{\log_2x\}}]=[2^r\cdot 2^{\{m\log_23\}}]$, а поскольку $\log_23$ - обычное иррациональное число, то $\{m\log_23\}$ плотно заполняет $[0;1]$, т.е. если бы мы умели получать все числа $3^m$, то задача была бы решена.
Если же $x=3^{2^m}$, то первые $r$ бит числа равны $[2^r\cdot 2^{\{2^m\log_23\}}]$. Вроде как $\{2^m\log_23\}$ р.р.$\mod 1$.

Здесь на 34:15 говорится о доказанном через динамические системы результате, что $\{ 2^n 3^m \alpha \}$ всюду плотно в $(0;1)$ если $\alpha = \frac{\log n}{\log m} (m,n>1)$ и $\alpha$ не рационально. Возможно, это будет полезно здесь (если как-то ещё модифицировать множество операций). Но одним введением деления на три всё равно не обойдётся...

[grizzly]

fractalon в сообщении #1293918 писал(а):

если $\alpha = \frac{\log n}{\log m} (m,n>1)$ и $\alpha$ не рационально.

Нужно только второе из этих условий. Первое попало сюда в результате понятно какого недоразумения (на видео и в презентации всё правильно).

[fractalon]

Да, действительно, был невнимателен.
Выходит, если добавить к операциям Sonic86 $f_4(x)=x^3$, то для такого набора утверждение можно считать доказанным? Проверьте меня кто-нибудь.

[fractalon]

(Оффтоп)

Кстати, поделитесь, пожалуйста, кто знает, ссылкой на доказательство этого результата Фюрстенберга. А то в обзоре конкретная статья не указывается.

[grizzly]

fractalon в сообщении #1295104 писал(а):

поделитесь, пожалуйста, кто знает, ссылкой на доказательство этого результата Фюрстенберга.

Пожалуйста. Не уверен, что могу локализовать полное доказательство (не пытался, сложно да и стиль полувековой давности немного напрягает), но сам вывод можно найти в последних абзацах работы.