2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Вопрос о получении любого числа
Сообщение22.09.2017, 20:02 


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

 Профиль  
                  
 
 Re: Вопрос о получении любого числа
Сообщение22.09.2017, 20:08 
Заслуженный участник
Аватара пользователя


09/09/14
5448
dorofeev в сообщении #1249837 писал(а):
Проблему я сам придумал.
Супер! А я как раз собирался спросить об этом. Я специально не интересовался, но вокруг подобных вопросов ходил частенько и не разу этой задачи не встречал.

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

 Профиль  
                  
 
 Re: Вопрос о получении любого числа
Сообщение22.09.2017, 23:15 


16/09/17
11
Спасибо за совет,Grizzly!

 Профиль  
                  
 
 Re: Вопрос о получении любого числа
Сообщение23.02.2018, 14:52 


08/09/13
205
Sonic86 в сообщении #1248700 писал(а):
Раз эта задача сложная, давайте сделаем себе задачу попроще :D :
Дано число $3$ и множество отображений $f_1(x)=\frac{x}{2}, f_2(x)=\frac{x-1}{2}, f_3(x)=x^2$. Надо композицией $f_j$ получить произвольное число. :D
Первые 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$ не рационально. Возможно, это будет полезно здесь (если как-то ещё модифицировать множество операций). Но одним введением деления на три всё равно не обойдётся...

 Профиль  
                  
 
 Re: Вопрос о получении любого числа
Сообщение23.02.2018, 15:17 
Заслуженный участник
Аватара пользователя


09/09/14
5448
fractalon в сообщении #1293918 писал(а):
если $\alpha = \frac{\log n}{\log m} (m,n>1)$ и $\alpha$ не рационально.
Нужно только второе из этих условий. Первое попало сюда в результате понятно какого недоразумения (на видео и в презентации всё правильно).

 Профиль  
                  
 
 Re: Вопрос о получении любого числа
Сообщение01.03.2018, 21:05 


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

 Профиль  
                  
 
 Re: Вопрос о получении любого числа
Сообщение02.03.2018, 00:07 


08/09/13
205

(Оффтоп)

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

 Профиль  
                  
 
 Re: Вопрос о получении любого числа
Сообщение02.03.2018, 00:56 
Заслуженный участник
Аватара пользователя


09/09/14
5448
fractalon в сообщении #1295104 писал(а):
поделитесь, пожалуйста, кто знает, ссылкой на доказательство этого результата Фюрстенберга.
Пожалуйста. Не уверен, что могу локализовать полное доказательство (не пытался, сложно да и стиль полувековой давности немного напрягает), но сам вывод можно найти в последних абзацах работы.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 38 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group