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

[dorofeev]

Мы начинаем с числа $3$.Можно использовать три операции над этим числом:$(n+1)/2$,$n/2$ и $n^2$.Можно ли придумать алгоритм,который позволит при помощи некоторой последовательности таких операций(числа должны оставаться натуральными) получить любое натуральное число?Числа от $3$ до $50$ получить можно (я проверял).

[Karan]

Тема перемещена из форума «Загадки, головоломки, ребусы» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Karan]

Тема перемещена из форума «Карантин» в форум «Математика (общие вопросы)»

[arseniiv]

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

Далее, можно упростить набор операций. Раз разрешается получать только натуральные результаты, можно объединить $(n+1)/2$ и $n/2$ в $\lfloor(n+1)/2\rfloor$, и теперь заодно мы можем применять любую операцию к любому натуральному числу.

Далее, если мы считаем ноль натуральным, ответ отрицательный, потому что его нельзя получить ни из какого натурального числа.

-- Сб сен 16, 2017 18:08:26 --

Кстати,

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

Числа от $3$ до $50$ получить можно (я проверял).

Странно, что вы не указали числа 1 и 2.

[grizzly]

Посмотрел руками для числа 51. Получил его из числа 35 за 41 шаг (или что-то около того). Думаю, что можно получить любое число, но общего рассуждения пока не вижу.

Плюсую вопрос.

[mihaild]

Пусть $n$ - наименьшее число, которое так нельзя получить. Заметим, что любые числа, получаемые из $n$ дописыванием справа в двоичной записи $0$ или $1$ получить тоже нельзя. Хотелось бы, чтобы можно было дописать справа что-то, меньшее $n$, чтобы получился квадрат, но это можно не всегда:(

[dorofeev]

В начале ошибка:$1$ и $2$ также очень легко получить

-- 16.09.2017, 19:45 --

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

[Aritaborian]

«Здравый смысл» в таких случаях обычно лучше запихнуть подальше и дать ему поспать. Вспомните проблему $3n+1$, там здравый смысл тоже что-то, казалось бы, подсказывает, но толку от его подсказок никакого.

[Sonic86]

Да, только хотел напомнить:
Если начинать с числа $1$ и отображений $n\to 2n, n\to\frac{n-1}{3}$, то можем ли мы получить произвольное число? Или нет? А в этом вопросе отображения всего лишь линейные (но не всегда применимые). А у Вас - одно нелинейное.

-- Сб сен 16, 2017 19:14:26 --

А хотя нет:
По индукции с $3$:
$3$ получить можно.
Пусть можно получить все числа от $3$ до $a-1$. Надо получить число $a$.
$a \leftarrow [2a-1, 2a] \leftarrow [4a-3, 4a] \leftarrow... \leftarrow [2^k(a-1)+1, 2^ka]$ - ширина интервала аж $2^k$. Неужели мы ничего не найдем из $[3;a-1]$ такое, что при возведении в квадрат давало бы то, что попадает в этот интервал?

[mihaild]

Числа, не большие $152$, можно получить за не более чем $44$ шага (не используя в процессе чисел больше чем $10^{100}$ - но от них всё равно вернуться не получится), для получения $94$ нужно $44$ шага.
$51$ получается за $21$ шаг: 3 9 5 25 13 169 85 7225 3613 1807 904 452 226 113 57 3249 1625 813 407 204 102 51, быстрее нельзя.

-- 16.09.2017, 22:27 --

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

Неужели мы ничего не найдем из $[3;a-1]$ такое, что при возведении в квадрат давало бы то, что попадает в этот интервал?

Я это предлагал чуть выше. Можем не найти. Например, для $3,5,7,11,13,15,17,22,23,27,\ldots$. Среди первой тысячи $420$ таких чисел, среди первых десяти тысяч - $4186$.

[Sonic86]

(еще жалкая попытка)

Пусть надо получить $A$. Не теряя общности считаем, что $A$ - не квадрат. Значит $A$ получается после применения $k$ раз отображения $x\to [(x+1)/2]$. Если заменить $A$ на $A^2+1$, то $k$ не может быть четным - в отрезке-прообразе $[4^kA^2+1;4^kA^2+4^k]$ квадратов нет, значит $k$ нечетно, значит вопрос сводится к поиску квадрата в $[2\cdot 4^kA^2+1;2\cdot 4^kA^2+2\cdot 4^k]$, что сводится к уравнениям Пелля...

[Dmitriy40]

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

Пусть $n$ - наименьшее число, которое так нельзя получить. Заметим, что любые числа, получаемые из $n$ дописыванием справа в двоичной записи $0$ или $1$ получить тоже нельзя.

Мне кажется это утверждение не совсем верно. Дописывать $0$ конечно можно. А вот дописывать справа двоичную $1$ нельзя, ведь дописывание $1$ реализует операцию $n \to 2n+1$, но после выполнения якобы обратной операции $(x+1)/2$ получится вовсе не $n$: $((2n+1)+1)/2=n+1 \ne n$.
Так что непредставимость $n$ влечёт за собой и непредставимость $2n$ и $2n-1$ (а не плюс один).
По индукции, непредставимость $n$ влечёт за собой и непредставимость всех $[n\cdot2^k-2^k+1; n\cdot2^k], k \in \mathbb{N}$.
Вопрос существует ли число $x < n : x^{2^i} \in [n\cdot2^k-2^k+1; n\cdot2^k],\; k,i \in \mathbb{N}$ (а не только квадрат). Если б доказать что существует обязательно - получили бы противоречие. А вот если нет - это ничего не даёт.

-- 17.09.2017, 02:30 --

К примеру, $51$ можно получить из $57$ за семь шагов, но вот минимальное $k$ чтобы степень меньшего числа попала в нужный интервал аж $174$: $51\cdot2^{174}-2^{174}+1 \leqslant 7^{2^6} \leqslant 51\cdot2^{174}.$

[Dmitriy40]

А для числа $45$ вообще минимальное $k=1082: 45\cdot2^{1082}-2^{1082}+1\leqslant19^{256}\leqslant45\cdot2^{1082}.$
Следующее "неудобное" число будет $243: 243\cdot2^{3832}-2^{3832}+1\leqslant181^{512}\leqslant243\cdot2^{3832}.$

-- 17.09.2017, 04:04 --

Интересно число $31864$, для него надо проделать $970000$ шагов сдвига: $31863\cdot2^{970000}+1\leqslant28551^{65536}\leqslant31864\cdot2^{970000}.$ Если конечно программа не ошиблась.
В то же время его можно получить достаточно быстро: $4837^2 \to 45697^2 \to 31864$.

[grizzly]

Рискну предположить, что если для любых целых $m,k \ge 2$ вместо второй степени взять степень $m$, а вместо $\lfloor(n+1)/2\rfloor$ использовать $\lfloor(n+k-1)/k\rfloor$, то начав с любого числа, большего $k$, сможем заполнить весь натуральный ряд.

Это я к тому, что попытаться опровергнуть это обобщение должно быть не сложнее, чем первоначальное.

[Sonic86]

Раз эта задача сложная, давайте сделаем себе задачу попроще :
Дано число $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$. Поскольку я уже достаточно отупел, я не могу это обосновать или сослаться на нужную теорему (даже книгу забыл про р.р. мод 1 ). Надо там поискать или проверить, это д.б. несложный факт. А время у меня кончилось.

Если это получится доказать, то надо потом посмотреть - насколько сильно $k-$предпоследние итерации $x\to \lfloor\frac{x}{2}\rfloor$ отличаются от $k-$предпоследних итераций $x\to \lfloor\frac{x+1}{2}\rfloor$ - вроде не должны сильно отличаться и тогда исходная задача тоже должна несложно решаться.

upd: несущественные ошибки исправлены. Книжка - Нидеррайтер Равномерное распределение последовательностей. Нашел только теорему 4.1.:
Пусть $(a_n)$ - последовательность различных целых чисел. Тогда последовательность $(a_nx)$ р.р.мод.1 для почти всех $x$.
Можно было бы вставить в теорему $x=\log_23$, $a_n=2^n$ и проверить, получается ли правда, но мозгов не хватает - застреваю на переходе "Если $\int\limits_0^1\sum\limits_{n=1}^{\infty}|S(N^2,x)|^2dx<\infty$, то для почти всех $x$ $\sum\limits_{n=1}^{\infty}|S(N^2,x)|^2<\infty$".
Проверил опытным путем гипотезу - похоже на равномерное распределение, но размер типа double в PARI/GP заканчивается при удваивании довольно быстро.
С другой стороны, дальше есть теорема 5.3.:
Последовательность $(p^n \theta)$, где $p$ - целое, а $\theta$ - действительное не о.р.мод.1
(там о.р.мод1 - это сильнее, чем р.р.мод.1. Что-то типа сходимости ряда и функциональной сходимости ряда).
Так что тут какая-то загадка есть.