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

[Sonic86]

Доказать плотность всюду последовательности $2^n \log_23 \mod 1$ в $[0;1)$ у меня пока не получается, равномерность ее распределения - тоже.

Давайте тогда проведем все выкладки для исходной задачи.
Отображения $x\to \frac{x}{2}$ и $x\to \frac{x+1}{2}$ собираем в $f:x\to \lfloor\frac{x+1}{2}\rfloor$. Итерации его $f^{(k)}(x)=1+\lfloor\frac{x-1}{2^k}\rfloor$. При $2^k\geqslant x$, т.е. при $K=\lceil\log_2x\rceil$ получаем $f^{(K)}(x)=1$. Рассмотрим значения $f^{(K-r)}(x), r\geqslant 1$ - это будут числа из $[1+2^r; 2^{r+1}]$. Гипотеза та же: если квадрировать тройку достаточно долго, а потом брать $f^{(K-r)}(3^{2^m})$ то в получающейся последовательности будут всевозможные числа из $[2^r; 2^{r+1})$ (а значит вообще все натуральные числа, поскольку $r$ произвольное).
$f^{(K-r)}(3^{2^m})=1+\lfloor\frac{3^{2^m}-1}{2^{\lceil\log_23^{2^m}\rceil-r}}\rfloor =1+\lfloor2^r\frac{3^{2^m}-1}{2^{\lceil\log_23^{2^m}\rceil}}\rfloor$
Поскольку $\log_23^{2^m}$ нецелое для $m>0$, то $\lceil\log_23^{2^m}\rceil=1+[\log_23^{2^m}]$, значит
$f^{(K-r)}(3^{2^m})=1+\lfloor2^{r-1}{2^{\{2^m\log_23\}}\rfloor$
И снова: если $2^m \log_23 \mod 1$ всюду плотно в $[0;1)$, то значит $f^{(K-r)}(3^{2^m})$ пробегает все натуральные числа из $[1+2^r;2^{r+1}]$, а значит и можно с помощью указанных операцию построить все натуральные числа.
Т.е. здесь тоже все сводится к доказательству плотности последовательности $2^n \log_23 \mod 1$ в $[0;1)$.

[Dmitriy40]

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

Доказать плотность всюду последовательности $2^n \log_23 \mod 1$ в $[0;1)$ у меня пока не получается,

Поправьте меня если не прав, но это вроде и невозможно. Предварительно две леммы. 1. Число $\log_23$ - иррациональное. 2. Остаток справа после отрезания конечного числа левых цифр от любого иррационального числа является числом иррациональным.
Операция $y \bmod 1$ - отрезает сколько-то левых цифр, оставляя справа все остальные, и для иррационального $y=2^n \cdot x$ остаток будет тоже иррациональным. Т.е. остаются выколоты все рациональные числа. Вах.
В частности, ноль ну никак не получить, ведь тогда число $y=2^n\log_23$ должно быть целым, значит число $\log_23=y/2^n$ рациональным, но оно же иррационально по условию. Аналогично не получить и числа вида $1/2^n$.
Что однако не является доказательством невозможности получения всех натуральных чисел.

[arseniiv]

Как это мешает всюду плотности? Если вдруг среди двоичных цифр $\log_23$ попадается любая конечная последовательность, это как раз наоборот легко покажет её. Вот только если.

[Dmitriy40]

Выскажу такую гипотезу: любое число $x$ можно получить как $x=f(y^2), y \ne x, y<3x$. Т.е. из квадратов чисел не более чем $3x$. Как доказывать пока не знаю. И как именно использовать для доказательства исходного предположения тоже не знаю.
Из примеров: $57^2\to26$, $91^2\to33$, $363^2\to129$, $725^2\to257$, $1449^2\to513$ (похожи на $2^n+1$). Для чисел до миллиона коэффициент не превышает $2{,}8284271247462$, похоже это предел.

arseniiv в сообщении #1249081 писал(а):

Как это мешает всюду плотности?

Хм, я что, спутал плотность и непрерывность? Тогда извинтиляюсь.

[grizzly]

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

Т.е. здесь тоже все сводится к доказательству плотности последовательности $2^n \log_23 \mod 1$ в $[0;1)$.

Правильно ли я понимаю, что плотность последовательности $10^n \log_23 \mod 1$ в $[0;1)$ равносильна тому, что каждая конечная последовательность десятичных цифр встречается в числе $\log_23$ бесконечное число раз? Если да, то вряд ли это что-то простое. Сомнительно также, что с последовательностью $2^n \log_23 \mod 1$ дела обстоят сколько-то проще.

[mihaild]

arseniiv в сообщении #1249081 писал(а):

Если вдруг среди двоичных цифр $\log_23$ попадается любая конечная последовательность, это как раз наоборот легко покажет её.

Этого разве достаточно? Если скажем на всех позициях с номерами $2^n + 1$ в двоичной записи $\log_23$ стоят нули, то вся последовательность $2^n \log_23 \mod 1$ лежит в $[0; 0.5)$ и не всюду плотна в $[0; 1)$.

[arseniiv]

Я действительно не очень думал над тем аргументом, но это, кажется, тоже не опровержение, если прочитал его правильно. Если среди цифр $\log_23$ попадается последовательность 11, последовательность $2^n \log_23 \bmod 1$ содержит $0{,}11\ldots_2 \geqslant 0{,}75$ и т. д., и если в числе попадается любая последовательность цифр, то попадаются и последовательности, соответствующие приближениям любого вещественного числа из $[0;1)$.

[mihaild]

Да, соврамши. Умножение на $2^n$ - это перенос точки на $n$ цифр вправо (а я почему-то подумал что на $2^n$).

[Sonic86]

grizzly в сообщении #1249597 писал(а):

Правильно ли я понимаю, что плотность последовательности $10^n \log_23 \mod 1$ в $[0;1)$ равносильна тому, что каждая конечная последовательность десятичных цифр встречается в числе $\log_23$ бесконечное число раз?

Ну да. Раз она везде плотна, то д.б. число, достаточно близкое, например, к любому числу виду $(A+\frac{1}{4})\cdot 10^{-k}, 0\leqslant A <10^k, A\in\mathbb{Z}$. Его первые $k$ цифр должны давать число $A$.
Т.е. вопрос сводится к гипотеза о нормальности $\log_23$ по основанию $2$? Фигово... И тогда понятно, почему в книге сей вопрос молчаливо обходится. А начиналось все так позитивно...
(изначально я смотрел на это как возможность получить любую конечную комбинацию цифр в $3^{2^m}$ в двоичной системе счисления, это казалось правдоподобным...)

[mihaild]

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

Т.е. вопрос сводится к гипотеза о нормальности $\log_23$ по основанию $2$?

Кажется что слабее, чем нормальность - нам надо чтобы каждая последовательность встречалась, без ограничений на частоту.

[Sonic86]

mihaild в сообщении #1249637 писал(а):

Кажется что слабее, чем нормальность - нам надо чтобы каждая последовательность встречалась, без ограничений на частоту.

А, это обнадеживает.
Если брать требование одинаковости асимптотической частоты, то это как раз и получится р.р. $\mod 1$. (Равномерное распределение вообще вылезло потому, что его иногда проще доказать.)

[grizzly]

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

А, это обнадеживает.

Разве? Может я что-то пропустил и уже известно, что в десятичной записи числа $\log _23$ содержится бесконечно много единиц, например?

[arseniiv]

Для десятичной, может, и нет, но для двоичной это должно быть обязательно: если единиц или нулей конечное число, с какого-то разряда начинаются повторы, и число рационально. Хотя толку…

[Sonic86]

grizzly в сообщении #1249640 писал(а):

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

А, это обнадеживает.

Разве? Может я что-то пропустил и уже известно, что в десятичной записи числа $\log _23$ содержится бесконечно много единиц, например?

Я не в курсе Это тоже известная трудная проблема? Просто с нормальностью числа я бы точно бодаться не стал.

[grizzly]

Попалась на глаза похожа задача. Она раньше числилась в списке нерешённых и не так давно она была решена (для любой пары взаимно простых чисел). Там тоже требуется доказать, что любое натуральное число встретится в последовательности и только один раз. Единственность там доказывается попроще, а вот встречаемость...

Подозреваю, что наша ситуация намного хуже примерно такая же (это upd).

-- 21.09.2017, 23:21 --

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

Это тоже известная трудная проблема?

Думаю, да. Все проблемы такого рода пока весьма сложны.