Утверждение с числами

[Keter]

Утверждение: если $a$ - натурльное число больше еденицы, $r$ - любая цифра десятичной системы счисления, то существует натуральное число $b$ такое, что $a$-я цифра по счету с конца в десятичной записи числа $2^b$ и есть цифра $r.$

Где посмотреть доказательство? Как можно доказать, если нет где посмотреть?

[Sonic86]

Неверно. Контрпримеры очевидны.

[Dave]

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

Неверно. Контрпримеры очевидны.

Что-то ни одного не вижу. Приведите, пожалуйста.

У меня возникла такая

Гипотеза. При любом натуральном $n$ целое число $t$ от $0$ до $10^n-1$ включительно является окончанием степени двойки некоторого целого числа $b \geqslant n$ тогда и только тогда, когда $\frac t {2^n}$ - целое число, не делящееся на $5$.

Предлагаю доказать или опровергнуть её. Если она верна, то т.к. при $n>1$ шаг между соседними "хорошими" $t$ не превосходит $2^{n+1}<10^{n-1}$, то всё должно быть в ажуре.

[Mathusic]

Dave в сообщении #746940 писал(а):

Приведите, пожалуйста.

$a=2, r = 3.$

[Someone]

$2^5=32$

Период последовательности $2^k$ по модулю $10^n$, если не ошибаюсь, начинается с $k=n$ и имеет длину $4\cdot 5^{n-1}$. Так что, видимо, Dave прав.

[Dave]

Да, доказал свою гипотезу. Можно даже реализовать алгоритм дискретного логарифмирования полиномиальной сложности в данном конкретном случае, т.е. для задачи $2^x \equiv c \pmod {5^n}$.

[Sonic86]

Dave в сообщении #746940 писал(а):

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

Неверно. Контрпримеры очевидны.

Что-то ни одного не вижу. Приведите, пожалуйста.

А нет, я нашел у себя ошибку, извините.

Dave в сообщении #747216 писал(а):

Можно даже реализовать алгоритм дискретного логарифмирования полиномиальной сложности в данном конкретном случае, т.е. для задачи $2^x \equiv c \pmod {5^n}$.

Для фиксированного $p$ реализовать полиномиальный по $n$ алгоритм дискретного логарифмирования можно и в общем случае для $a^x\equiv c\pmod{p^n}$. Или у Вас он получается асимптотически быстрее?

[Dave]

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

Для фиксированного $p$ реализовать полиномиальный по $n$ алгоритм дискретного логарифмирования можно и в общем случае для $a^x\equiv c\pmod{p^n}$. Или у Вас он получается асимптотически быстрее?

Вот этого не скажу, ибо не знаю, с чем сравнивать.

[Mathusic]

Объясните, пожалуйста, почему 4 пост невалиден.

(Оффтоп)

Самому лень смотреть

(Оффтоп)

"Конец" десятичной записи как высший разряд определяем?

[Dave]

Mathusic в сообщении #747611 писал(а):

Объясните, пожалуйста, почему 4 пост невалиден.

Потому что 5 пост валиден. В $2^5$, (как и в $2^{25}$ и т.д.) вторая цифра с конца какая?

[Keter]

Я кое-что понимаю, но не совсем могу записать алгоритм доказательства... Подскажите с чего начать

[Dave]

1. Докажите индукцией по $n$, что все числа $2^x$ при $x=0,1,\dots,4\cdot 5^{n-1}-1$ дают разные остатки при делении на $5^n$.
2. Выясните, как выглядит множество таких остатков, используя результат п. 1.
3. Что изменится, если мы прибавим $n$ ко всем $x$ и будем брать остатки от деления $2^x$ не на $5^n$, а на $10^n$?

[Keter]

Dave, я прав, что нам нужно доказать, что на какой-то позиции $b_a$ в числе $2^k$ могут быть цифры от нуля до девяти? Пусть, например, $2^k=\overline{b_n b_{n-1} ... b_a b_{a-1} ... b_1}.$ При домножении на двойку получим $2^{k+1},$ заметим, что $b_{a-1}$ может отдать только $0$ или $1$ цифре $b_a.$ Таким образом, поднимая степень $2^k,$ $b_a$ пробегает все цифры от нуля до девяти.

[Dave]

Keter в сообщении #748252 писал(а):

Dave, я прав, что нам нужно доказать, что на какой-то позиции $b_a$ в числе $2^k$ могут быть цифры от нуля до девяти?

Да, именно это мы и доказываем для любого $a>1$.

Keter в сообщении #748252 писал(а):

...$b_{a-1}$ может отдать только $0$ или $1$ цифре $b_a.$...

Проблема в том, что $b_a$ при этом каждый раз ещё и увеличивается в два раза.

[Keter]

Dave в сообщении #748356 писал(а):

Проблема в том, что $b_a$ при этом каждый раз ещё и увеличивается в два раза.

А эту маленькую деталь можно как-то обойти в рамках моих тривиальных рассуждений?
Просто я понимаю то, что Вы написали выше по пунктам, у меня получилось доказать по индукции, посмотреть на остатки. Но я не могу въехать как мы к этому пришли и чем нам это поможет.
Почему на $5^n$? Что нам это даёт для задачи?