2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Вопрос о получении любого числа
Сообщение16.09.2017, 14:05 


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

 Профиль  
                  
 
 Posted automatically
Сообщение16.09.2017, 14:06 
Модератор


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

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

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

 Профиль  
                  
 
 Posted automatically
Сообщение16.09.2017, 14:46 
Модератор


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

 Профиль  
                  
 
 Re: Вопрос о получении любого числа
Сообщение16.09.2017, 16:07 
Заслуженный участник


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

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

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

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

Кстати,
dorofeev в сообщении #1248124 писал(а):
Числа от $3$ до $50$ получить можно (я проверял).
Странно, что вы не указали числа 1 и 2. :roll:

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


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

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

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


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

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


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

-- 16.09.2017, 19:45 --

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

 Профиль  
                  
 
 Re: Вопрос о получении любого числа
Сообщение16.09.2017, 22:02 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вопрос о получении любого числа
Сообщение16.09.2017, 22:06 
Заслуженный участник


08/04/08
8556
Да, только хотел напомнить:
Если начинать с числа $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]$ такое, что при возведении в квадрат давало бы то, что попадает в этот интервал?

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


16/07/14
8342
Цюрих
Числа, не большие $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$.

 Профиль  
                  
 
 Re: Вопрос о получении любого числа
Сообщение16.09.2017, 22:37 
Заслуженный участник


08/04/08
8556

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

Пусть надо получить $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]$, что сводится к уравнениям Пелля...

 Профиль  
                  
 
 Re: Вопрос о получении любого числа
Сообщение17.09.2017, 01:33 
Заслуженный участник


20/08/14
11061
Россия, Москва
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}.$

 Профиль  
                  
 
 Re: Вопрос о получении любого числа
Сообщение17.09.2017, 03:14 
Заслуженный участник


20/08/14
11061
Россия, Москва
А для числа $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$.

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


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

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

 Профиль  
                  
 
 Re: Вопрос о получении любого числа
Сообщение18.09.2017, 16:38 
Заслуженный участник


08/04/08
8556
Раз эта задача сложная, давайте сделаем себе задачу попроще :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$. Поскольку я уже достаточно отупел, я не могу это обосновать или сослаться на нужную теорему (даже книгу забыл про р.р. мод 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. Что-то типа сходимости ряда и функциональной сходимости ряда).
Так что тут какая-то загадка есть.

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

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



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

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


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

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