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

а) Доказать, что в системе исчисления по основанию $%q$% существует деформируемые дважды подряд числа тогда и только тогда, когда $%q\ne p^m$%, где $%p$% - простое число, $%m$% - натуральное.

б) В системе счисления по основанию $%30$% число $%151Q7F$% деформируемое четыре раза подряд. Существует ли в какой-либо позиционной системе счисления число, деформируемое пять раз подряд?

задан 3 Ноя '16 16:21

изменен 3 Ноя '16 23:15

10|600 символов нужно символов осталось
2

Пускай $%\left({\overline{a_1...a_kbc_1...c_n}}\right)_q=A\cdot q^{n+1}+b\cdot q^n+C$% - деформируемое число, у которого вычёркивается цифра $%b$%. Тогда $$\frac{A\cdot q^{n+1}+b\cdot q^n+C}{A\cdot q^n+C}=x$$ для некоторого натурального $%x$%. Оценим $%x$%: $$1< x=\frac{A\cdot q^{n+1}+b\cdot q^n+C}{A\cdot q^n+C}<\frac{A\cdot q^{n+1} +(q-1)\cdot q^n+q^n}{A\cdot {q^n}+0}=q+\frac qA\le 2q, \text{ то есть }1< x<2q.$$

Покажем, что $%A$% состоит из одной цифры, то есть вычёркивать можно только вторую цифру слева:

Если $%1< x< q$%, то $%A=\frac{C(x-1)}{q^n(q-x)}-\frac b{{q-x}}\le\frac{C(x-1)}{q^n(q-x)}< x-1< q$%.

Если $%x=q$%, то $%q^nb=C(q-1)$%, а поскольку $%(q,q-1)=1$%, то $%C$% делится на $%q$%. Противоречие.

Если $%q+1\le x\le 2q-1$%, то $%A=\frac b{x-q}-\frac{C(x-1)}{q^n(x-q)}<\frac b{x-q}\le b< q$%.

Пускай $%q=p^m$%, где $%p$% - простое число. Рассмотрим уравнение $$q^n(Aq-Ax+b)=C(x-1).$$ Поскольку $%C$% не делится на $%q$%, то максимальная степень $%p$%, на которую делится $%C$%, не превышает $%m-1$%, а максимальная степень $%p$%, на которую делится $%x-1(<2q-1< p^{m+1})$%, не превышает $%m$%, поэтому $%C(x-1)$% не делится на $%p^{2m}=q^2$%, следовательно $%n=1$%, и $%C$% состоит из одной цифры. Таким образом, в случае $%q=p^m$% деформируемые числа состоят из трёх цифр и не деформируемые дважды подряд.

В случае $%q\ne p^m$% возьмём разные простые делители $%p$% и $%p_1$% ($%p_1>p$%) числа $%q$%. Разделим один на другой: $%p_1=pt+r$%, где $%t$% и $%r$% - натуральные числа, причём $%1\le r\le p-1$%. Число $%q$% запишем в таком виде: $%q=dpp_1=dp(pt+r)$%, где $%d$% - некоторое натуральное число.

Четырехзначное число $%{\overline {(t)(2t)\left((dpr+1)t+dr^2\right)(dptr+dr^2)}_q}$% деформируемое дважды подряд : $${\overline{(t)(2t)\left((dpr+1)t+dr^2\right)(dptr+dr^2)}_q}=d(pt+r)^2(dp^2t+dpr+1)(dp^2t+1),$$ $${\overline{(t)\left((dpr+1)t+dr^2\right)(dptr+dr^2)}_q}=d(pt+r)^2(dp^2t+dpr+1),$$ $${\overline{(t)(dptr+dr^2)}_q}=d(pt+r)^2.$$

В десятичной системе таким числом будет 2475.

ссылка

отвечен 6 Ноя '16 12:50

изменен 6 Ноя '16 12:54

1

Много техники, но зато красиво по содержанию!

(6 Ноя '16 14:48) falcao

@falcao: Составил программку и получил:

Деформируемые трижды подряд существуют для оснований 24,30,33,36,42,44,48,50,52,54,60,66,70,72(нет!!),75,76,78,80,84,85,87,90,92,95,96,100,… Закономерности не нашёл.

Деформируемые четырежды подряд нашёл для оснований 30,42 и 48.

Деформируемых пять раз подряд не нашёл.

(6 Ноя '16 15:35) EdwardTur

Да, это всё интересно весьма! С учётом общего факта, что вычёркивать можно только первую (то есть вторую) цифру, тут есть "поле" для исследований на компьютере. Я, кстати, до этой "леммы" так и не дошёл -- над задачей только чуть-чуть удалось подумать.

(6 Ноя '16 15:42) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×127
×44

задан
3 Ноя '16 16:21

показан
1313 раз

обновлен
6 Ноя '16 15:42

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru