Выразить k, чтобы выполнялось равенство

[z3x]

$\left[\frac {a\cdot5^x} {2^q}\right] - \left[ a\cdot \left[\frac {5^x} {2^k}\right]\cdot\frac {2^k} {2^q}\right] = 0, q = \left[x\cdot \log_2(5)\right], a \in N, x \in N, k \in N$
Квадратные скобки - целая часть числа. Требуется дать оценку числу k, такую, чтобы выполнялось равенство выше.
Какие попытки предпринимал лично я:
Заметим, что у нас есть две целые части в выражении: та из которой вычитаем и та, которую вычитаем. Очевидно, что $\frac {5^x} {2^q}$ - представимо числом 1.ZXCVB...., а значит при умножении на $a$, целой частью можем получить числа от $[a, 2 \cdot a) $. Далее, я попытался провести для данного интервала равенства для каждой из частей, однако какого - то ощутимого результата это не принесло. В том плане, что не получается никак выразить k, ибо оно под целой частью. То есть, положим что $\left[ a\cdot \left[\frac {5^x} {2^k}\right]\cdot\frac {2^k} {2^q}\right] = a$, тогда получим неравенство: $2^q \leqslant \left[\frac {5^x} {2^k}\right] \cdot 2^k < 2^q\left( \frac {a + 1} {a} \right)$
И как вытащить k - мне не очень понятно. Надеюсь на помощь профессиональных математиков. Спасибо.

[worm2]

Я погонял различные варианты на компьютере: $a\leqslant 100$, $x\leqslant 20$, $k\leqslant 50$.

1) Должен сразу предупредить, что я не проверял вручную ни одного варианта, кроме $a=x=1$, для которого у меня результаты машинного и ручного счёта совпали: $k\leqslant 2$. В остальных вариантах могут быть ошибки!

2) Не для всех пар $(a, x)$ есть решения. Но похоже на то, что когда решения есть, они составляют "непрерывный" отрезок: $1\leqslant k\leqslant k_{\max}$.

3) Похоже на то, что (когда решения есть, т.е. $k_{\min}$ определено) минимальная граница $k_{\min}$ нестрого монотонно возрастает (не убывает) как при возрастании $a$, так и при возрастании $x$. Ошибся в вычислениях. Похоже на то, что всегда $k_{\min}=1$

4) А вот с максимальной границей $k_{\max}$ всё очень непросто. Она скачет туда-сюда, хотя и обнаруживает тенденцию к убыванию при возрастании $a$ и к возрастанию при возрастании $x$.

Например, вот таблица $k_{\max}$ при $19\leqslant a \leqslant 25$, $4 \leqslant x \leqslant 6$:

\begin{tabular}{|c|ccc|} \hline a\backslash x &4 &5 &6\\ \hline 19 &4 &10 &8\\ 20 &4 &10 &8\\ 21 &4 &2 &8\\ 22 &5 &10 &10\\ 23 &4 &4 &10\\ 24 &4 &10 &10\\ 25 &4 &4 &8\\ \hline \end{tabular}

Так что не ждите красивой формулы, скорее всего, её нет. А она есть

[DeBill]

worm2 в сообщении #1409418 писал(а):

Так что не ждите красивой формулы, скорее всего, её нет.

Ага, сильно похоже на это....
Вот еще какие то замечания:
Разность эта - неотрицательна.
Можно написать необходимое условие равенства:
$\frac{a\cdot 5^x}{2^q}<a\cdot[\frac{5^x}{2^k}]\cdot \frac{2^k}{2^q}+1$
А можно - достаточное для необходимого: $a\cdot 2^{k-q}< 1$, откуда получить оценку на $k$. Да вот только достаточное для необходимого - это полная фигня...
Но если по честному, то можно получить все же достаточное условие в виде:
$a\cdot 2^{k-q}< \{\frac{a\cdot 5^x}{2^q}\}$, (скобки - дробная часть) откуда и получим оценку на $k$.
Интересно бы сравнить со счетом worm2, но для меня такая задача - не по силам

[B@R5uk]

$2^q=2^{\left[x\cdot \log_2(5)\right]}=2^{x\cdot \log_2(5)-\log_2(\gamma)}=5^x/\gamma$
$-1/2<-\log_2(\gamma)<1/2$
$\left[\frac {a\cdot5^x} {2^q}\right] - \left[ a\cdot \left[\frac {5^x} {2^k}\right]\cdot\frac {2^k} {2^q}\right] = \left[\gamma a\right] - \left[\gamma a\cdot \left[\frac {5^x} {2^k}\right]\frac {2^k} {5^x}\right]$
Теперь должно стать по-проще, вроде.

-- 09.08.2019, 18:20 --

Не, надо ещё такую замену: $b=\frac {5^x} {2^k}$. Тогда уравнение

$\left[\gamma a\right]= \left[\frac {\gamma a \left[b\right]} {b}\right]$

решается относительно b однозначно (получится какой-нибудь отрезок наверняка). После чего можно найти и отрезок для k.

[Dmitriy40]

z3x в сообщении #1409282 писал(а):

тогда получим неравенство: $2^q \leqslant \left[\frac {5^x} {2^k}\right] \cdot 2^k < 2^q\left( \frac {a + 1} {a} \right)$

В этом неравенстве в середине стоит обнуление младших $k$ разрядов в двоичной записи числа $5^x$.
А слева $2^q$ - одна лишь старшая единица двоичной записи числа $5^x$ и $q$ - уменьшенный на 1 номер старшей единицы в двоичной записи $5^x$.
Значит левое неравенство выполняется всегда пока среднее число не обнулилось ($k < q $, т.е. $k$ не обнулило старшую единицу).
Справа стоит та же старшая единица, домноженная на некое число немногим больше $1$. Соответственно правое неравенство точно выполняется при $k=q-1$ (т.е. в числе $5^x$ обнуление всех двоичных цифр кроме самой старшей) и любом $a$, плюс если $a=1$, то $k$ может быть $0 \le k \le q$ (лишь для правого неравенства, не для левого), плюс при $a=2$ правое неравенство выполняется только для $k = q-1$ (в этом случае все младшие биты в правом числе и так нулевые, а неравенство строгое), плюс при $a>2$ правое неравенство выполняется для $0 \le k < q-1$ (тут ошибся).
В итоге получается что $k$ может принимать значения от номера младшей единицы в двоичной записи числа $[2^q(a+1)/a]$ до номера старшей единицы минус 1 - только при этих условиях число в середине не обнуляется и в то же время становится меньше правого числа.

Почему это отличается (если отличается) от данных worm2 мне непонятно, скорее всего неравенства не равносильные.

PS. Я везде подразумевал что $[]$ - округление до целого вниз (к $-\infty$), как в математике, а не округление к ближайшему.

-- 09.08.2019, 19:44 --

Dmitriy40 в сообщении #1409545 писал(а):

$k$ может принимать значения от номера младшей единицы в двоичной записи числа $[2^q(a+1)/a]$

А максимальным эта величина будет вероятно при $a=2^t$, т.е. когда $a$ равно степени $2$. Тогда $q-t \le k < q$.

[DeBill]

Dmitriy40 в сообщении #1409545 писал(а):

В этом неравенстве

Это неравенство ТС получил, предполагая, что вторая целая часть в точности равна $a$ (что вовсе не гарантирует выполнение равенства). Так что решение этого неравенства реально ничего почти не дает...

-- 09.08.2019, 22:23 --

B@R5uk в сообщении #1409525 писал(а):

решается относительно b однозначно

Ну да, это дает
$\frac{[b]}{b}\geqslant\frac{[z]}{z}$, где $z=a\gamma$.
Вот только графическое решение этого неравенства дает (вроде бы) кучку интервалов, и луч. Находя отсюда (натуральные) $k$, получим $k\leqslant k_0$ для некоторого $k_0$ (его , видимо, я выше и указал), и, мобыть, еще несколько штук.....

[Dmitriy40]

Вообще если преобразовать исходное равенство примерно так:
$\left[\frac {a\cdot5^x} {2^q}\right] - \left[ a\cdot \left[\frac {5^x} {2^k}\right]\cdot\frac {2^k} {2^q}\right] = 0$
$\left[\frac {5^x} {2^k}\right]\cdot 2^k = 5^x - 2^k\left\{\frac{5^x}{2^k}\right\}$ (фигурные скобки - дробная часть, при домножении на $2^k$ это фактически выделение младших $k$ битов числа $5^x$)
$\left[a\frac {5^x} {2^q}\right] = \left[\frac{a}{2^q}\left(5^x - 2^k\left\{\frac{5^x}{2^k}\right\}\right)\right]$
$\left[a\frac {5^x} {2^q}\right] = \left[a\frac{5^x}{2^q} - a\frac{2^k}{2^q}\left\{\frac{5^x}{2^k}\right\}\right]$
Справа стоит вся левая часть за вычетом чего-то положительного. Значит равенство возможно лишь если справа вычитаемое не превышает дробную часть вычитаемого:
$\left\{a \frac{5^x}{2^q}\right\} \ge a \frac{2^k}{2^q}\left\{\frac{5^x}{2^k}\right\}$
$2^q\left\{a \frac{5^x}{2^q}\right\} \ge a 2^k\left\{\frac{5^x}{2^k}\right\}$
Вот это $2^k \left\{\frac{5^x}{2^k}\right\}$ снова взятие младших $k$ битов числа $5^x$, а $2^q\left\{a\frac{5^x}{2^q}\right\}$ - взятие младших $q$ битов числа $a 5^x$.

В итоге получается что $q$ младших битов $a 5^x$ должны быть не меньше чем $k$ младших битов $5^x$, домноженных на $a$.

[z3x]

$0\leqslant k \leqslant \log_2( \frac {(a \cdot 5^x) mod 2^q } {a} )$
Вот типа того у меня получается. Но это гарантированная оценка, а не самая точная. Можно ли точнее?

[worm2]

Dmitriy40 в сообщении #1409578 писал(а):

В итоге получается что $q$ младших битов $a 5^x$ должны быть не меньше чем $k$ младших битов $5^x$, домноженных на $a$.

Это совпадает с моими расчётами (для верхней границы $k_{\max}$).

-- Сб авг 10, 2019 14:01:48 --

Нашёл в своей программе ошибки. На самом деле всегда $k_{\min}=1$ (ограничения снизу нет).
Теперь совпадение полное.

[Dmitriy40]

Увидев сообщение z3x хотел возмутиться левым неравенством, точнее условием $k=0$, но подставив это значение в исходное выражение получил тождество при любых $a,x,q \in N$. А значит $k_{\min}=0$. Впрочем раз оно тоже натуральное, то разницы с $k_{\min}=1$ нет.

[z3x]

В задаче, где нужно решение x как правило велик, в стандартные машинные типы влазит, но вот пять в степени икса - нет. То есть, проверки такие не поделать :)

[Dmitriy40]

Для небольших $k$ и $a$, суммарно влезающих в машинное слово, проделать можно, ведь всё число не нужно, лишь его младшие биты, а их можно получить вычислениями по модулю машинного слова. Т.е. $k$ вполне реально до примерно $60$. А ещё есть длинная арифметика ...