2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 2^n начинается на n
Сообщение13.04.2007, 15:09 
Модератор
Аватара пользователя


11/01/06
5710
Найти натуральные числа $n$ (хотя бы алгоритмически) такие, что десятичная запись числа $2^n$ начинается на $n.$

Например, известно такое решение: $n=72780032758751764.$ (см. A100129)
Можете ли вы найти еще большее решение?

 Профиль  
                  
 
 
Сообщение13.04.2007, 19:24 
Экс-модератор
Аватара пользователя


30/11/06
1265
Могу предложить только меньшее: $6$. 8-)

 Профиль  
                  
 
 
Сообщение13.04.2007, 20:33 


24/03/07
321
а что, в этом есть какой-то скрытый смысл?

 Профиль  
                  
 
 
Сообщение13.04.2007, 20:43 
Модератор
Аватара пользователя


11/01/06
5710
А что в большинстве остальных задач есть скрытый смысл?
Вообще-то я задал вполне конкретный вопрос и не давал повода для философствования. Так что, высказывайтесь, пожалуйста, по существу задачи.

 Профиль  
                  
 
 
Сообщение13.04.2007, 21:03 
Заслуженный участник
Аватара пользователя


11/01/06
3835
Прошу прощения, что не по теме, но в связи с этой задачей предлагаю такую задачку.
Доказать, что множество чисел $n$, удовлетворяющих условию, имеет нулевую плотность. Т.е. если обозначить через $A(N)$ количество искомых чисел $n\leqslant N$, то
$$\lim_{N\to\infty}\frac{A(N)}N=0.$$

Upd. Не, эта задача тривиальна. Лучше докажите, что ряд $\sum\frac1n$, где суммирование идёт по всем искомым $n$, сходится.

 Профиль  
                  
 
 Re: 2^n начинается на n
Сообщение13.04.2007, 21:51 
Заслуженный участник
Аватара пользователя


07/03/06
2103
Москва
maxal писал(а):
Найти натуральные числа $n$ (хотя бы алгоритмически) такие, что десятичная запись числа $2^n$ начинается на $n.$

Например, известно такое решение: $n=72780032758751764.$
Можете ли вы найти еще большее решение?


Maxal, мне кажется, вы ошибаетесь. У числа $2^{72780032758751764}$ первая цифра 1.

 Профиль  
                  
 
 Re: 2^n начинается на n
Сообщение13.04.2007, 22:10 
Заслуженный участник
Аватара пользователя


11/01/06
3835
Артамонов Ю.Н. писал(а):
Maxal, мне кажется, вы ошибаетесь. У числа $2^{72780032758751764}$ первая цифра 1.

Странно. Мой калькулятор говорит, что maxal не ошибается.

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


07/03/06
2103
Москва
Xм, не посмотрел, что у результата еще $10^{16}$. Так, что все верно. Sorry! Excuse me.

 Профиль  
                  
 
 Re: 2^n начинается на n
Сообщение13.04.2007, 22:37 
Модератор
Аватара пользователя


11/01/06
5710
Артамонов Ю.Н. писал(а):
Maxal, мне кажется, вы ошибаетесь. У числа $2^{72780032758751764}$ первая цифра 1.

PARI/GP утверждает следующее:
Код:
? 10^frac(72780032758751764*log(2)/log(10))
%1 = 7.2780032758751764578243794275606385634

Первые цифры результата в точности есть $72780032758751764.$

Добавлено спустя 3 минуты 14 секунд:

Артамонов Ю.Н. писал(а):
Дробная часть $n\lg2$ равна примерно 0.19, это меньше $\lg 2=0.3$

Она равна
Код:
? frac(72780032758751764*log(2)/log(10))
%2 = 0.86201224672894597707947155016544593664

 Профиль  
                  
 
 
Сообщение14.04.2007, 12:35 
Заслуженный участник


09/02/06
4401
Москва
По сути надо найти такие n, чтобы дробная часть $\{nlg2-lgn\}<\frac{1}{nln(10)}+O(\frac{1}{n^2}).$
Соответственно можно показать, что имеется бесконечно много таких n.

 Профиль  
                  
 
 
Сообщение14.04.2007, 12:50 
Модератор
Аватара пользователя


11/01/06
5710
Руст писал(а):
По сути надо найти такие n, чтобы дробная часть $\{nlg2-lgn\}<\frac{1}{nln(10)}+O(\frac{1}{n^2}).$
Соответственно можно показать, что имеется бесконечно много таких n.

Прошу, маэстро!

 Профиль  
                  
 
 
Сообщение14.04.2007, 13:29 
Заслуженный участник


09/02/06
4401
Москва
Пусть $lg2=\frac{P_k}{Q_k}+\frac{\theta }{Q_kQ_{k+1}},|\theta |<1$ соответствующие приближения, получаемые из непрерывных дробей. Тогда n можно искать в виде $n=Q_k+m.$
Это дает $\{nlg2-lgn\}=\{\frac{mP_k}{Q_k}-lg(Q_k+m)+\frac{\theta (1+m/Q_k)}{Q_{k+1}}\}<\frac{1}{\ln{10} (Q_k+m)}.$
Легко добиться того, чтобы первые два слагаемых были малы. Однако нам нужны более точные приближения из-за ln(10)>2. Если бесконечно много частных дробей больше некоторого числа порядка 6-7 то между $(0<m<Q_{k+1}-Q_k=(q_k-1)Q_k+Q_{k-1}$ можно подобрать m удовлетворяющее этому свойству.

 Профиль  
                  
 
 
Сообщение15.04.2007, 01:04 
Заслуженный участник
Аватара пользователя


11/01/06
3835
Руст писал(а):
Легко добиться того, чтобы первые два слагаемых были малы.

Никак не могу понять, как это сделать. :oops: Не мог бы кто-нибудь объяснить.

 Профиль  
                  
 
 
Сообщение15.04.2007, 09:37 
Заслуженный участник


09/02/06
4401
Москва
Задача эквивалентно
(1) $\{nlg2-lgn\}<lg(1+\frac{1}{n})=\frac{1}{nln{10}}+O(\frac{1}{n^2}).$
Будем искать решение в интервале
(2) $Q_k\le n<Q_{k+1}$.
Тогда можно искать n в виде $n_1+n_2, n_2<\sqrt n$. Фиксируя первое слагаемое находим
(3) $n=P_k^{-1}([lg(n_1)Q_k ]+ l), l<\sqrt n$
Примерно из $\sqrt n $ решений $\{nlg2 -lgn\}<\frac{1}{\sqrt n}$ находим самую точную, удовлетворяющую (1). Не в каждом интервале (2) такое решение найдётся. Вообще строгое доказательство существования бесконечного числа решений (1) является трудной задачей (ни такой простой, как казалось мне вначале). Поэтому, я изложил только идеи как найти такие числа.

 Профиль  
                  
 
 Re: 2^n начинается на n
Сообщение24.08.2013, 05:58 
Модератор
Аватара пользователя


11/01/06
5710
Robert Gerbicz пояснил, как числа порядка $72780032758751764$ можно найти с помощью метода встречи посередине.

Предположим, что мы ищем число n длиной в $D$ десятичных цифр, которое удовлетворяет неравенству:
$$\{\log_{10} n\} \leq \{n\cdot \log_{10}2\} < \{\log_{10}(n+1)\},$$
где $\{\dots \}$ обозначает дробную часть.
Разобьем цифры $n$ на две группы примерно одинаковой длины: $n=k\cdot 10^d + m$, где $d\approx \frac{D}{2}$ и $0\leq m< 10^d$.
Тогда мы, во-первых немного ослабим неравенство, исключив из оценок $m$:
$$\{\log_{10} k\} \leq \{\log_{10} n\} \leq \{n\cdot \log_{10}2\} < \{\log_{10}(n+1)\} < \{\log_{10}(k+1)\},$$
а во-вторых, заметим, что
$$\{n\cdot \log_{10}2\} = \{k\cdot 10^d\cdot \log_{10}2\} + \{m\cdot \log_{10}2\}-1?,$$
где ? указывает на возможный, но не обязательный член.

Итак имеем:
$$\{\log_{10} k\} - \{k\cdot 10^d\cdot \log_{10}2\} + 1? \leq \{m\cdot \log_{10}2\} < \{\log_{10}(k+1)\} - \{k\cdot 10^d\cdot \log_{10}2\} + 1?.$$

Теперь идея состоит в том, чтобы составить таблицу всех возможных $m$, упорядоченных по величине $\{m\cdot \log_{10}2\}$. Тогда для каждого $k$ мы быстро сможем найти по этой таблице подходящие $m$ (удовлетворяющие последнему неравенству), если такие существуют, скомбинировать их в $n$ и уже строго проверить, является ли оно решением.
Таким образом задача сводится к перебору порядка $10^{D/2}$ различных значений $k$.

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

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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