Назовём основание системы счисления комфортным, если существует простое число, запись которого в этой системе счисления ровно по одному разу содержит каждую из её цифр. Например, 3 – комфортное основание, так как троичное число 102 – простое. Найдите все комфортные основания, не превосходящие 12.

задан 17 Окт '13 19:20

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

Как известно, в десятичной системе счисления имеет место признак делимости на $%9$%. В более общем виде его можно сформулировать так: разность числа и суммы его цифр в десятичной записи кратна $%9$%.

Аналогичный признак справедлив для любой системы счисления с основанием $%g > 1$%. Роль числа $%9$% при этом играет число $%g-1$%. Доказательство основано на том, что $%g^n-1$% делится на $%g-1$% при любом натуральном $%n$% (это хорошо известный факт). Тогда, если в разряде, который соответствует $%n$%-й степени $%g$%, стоит цифра $%a$%, то она вносит в число вклад $%ag^n$%, и если её вычесть, то получится $%a(g^n-1)$%, что кратно $%g-1$%. Суммируя такие значения по каждой цифре числа, мы получим то, что надо.

Предположим теперь, что $%g$%-значное число $%N$% представлено в системе счисления с основанием $%g$% своими цифрами, каждая из которых встречается в записи числа ровно по разу. Пусть $%a_0$%, $%a_1$%, $%\ldots$%, $%a_{g-1}$% -- цифры числа, прочитанные справа налево. Тогда разность числа и его суммы цифр кратна $%g-1$%. Поскольку цифры представляют собой перестановку цифр от $%0$% до $%g-1$% включительно, сумма цифр равняется $%1+2+\cdots+(g-1)=(g-1)g/2$%, согласно известной формуле. Таким образом, мы приходим к выводу, что разность $$N-\frac{(g-1)g}2$$ кратна $%g-1$%.

Если $%g$% чётно, что отсюда следует, что $%N$% кратно $%g-1$%. Случай $%g=2$% легко рассмотреть отдельно, придя к выводу, что это основание является комфортным, так как число $%10_2$% равно двум, то есть является простым. Во всех остальных случаях $%N$% будет составным, так как оно не равно $%g-1$% (последнее полагается очевидным). Таким образом, для чётных $%g$% подходит только значение $%g=2$%.

Пусть теперь $%g$% нечётно. Тогда $%(g-1)/2$% -- натуральное число, и из предыдущего ясно, что $%N$% кратно $%(g-1)/2$%. Случай $%g=3$% уже исследован, а при $%g > 3$% оказывается, что $%N$% имеет ещё хотя бы один делитель помимо $%1$% и себя самого (это $%(g-1)/2 > 1$%), и тем самым не является простым.

ссылка

отвечен 17 Окт '13 22:25

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×794

задан
17 Окт '13 19:20

показан
537 раз

обновлен
17 Окт '13 22:25

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

по почте:

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

по RSS:

Ответы

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

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