Наибольшее число без одинаковых остатков

[Ktina]

Число 129 обладает любопытным свойством: среди остатков от деления этого числа на каждую из его цифр нет двух одинаковых. А чему равно наибольшее натуральное число (без нулей в десятичной записи) с таким свойством?

[Dmitriy40]

Неплохой кандидат (подбор руками): $98756$
Из всех 9-ти цифр число состоять не может т.к. любое из них делится и на 3 и на 9.
Ответ: $98642375$
Интересно как его получить без существенного перебора ...
Код перебора на PARI/GP:

? m(x)=my(d);d=vecsort(digits(x));if(d[1]==0,return(0));return(#vecsort(vector(#d,i,x%d[i]),,8)==#d);
? forstep(x=98765432,1,-1,if(m(x)>0,print(x);break));
98642375

-- 14.09.2018, 22:44 --

Если не ошибся, то в десятичной системе существует всего $6254$ таких числа (включая и числа $1..9$).
По другим основаниям: $1_2, 4_3, 8_4, 21_5, 64_6, 155_7, 508_8, 2177_9$ штук.

[Ktina]

Dmitriy40
Большое спасибо!
Любопытно, что некто другой дал мне ответ, отличный от Вашего, а именно 87625439.
Интересно, где у него ошибка?

[Dmitriy40]

Это число тоже правильное, но далеко не наибольшее, только с левой девяткой их 55 штук.
Но раз я не знаю как получить число без перебора, то не знаю и в чём может быть ошибка.

(Список по уменьшению до 87000000, вдруг чем-то поможет разобраться)

98642375, 98624735, 98462375, 98264375, 98246735,
97564318, 97541638, 97516438, 97463518, 97415638,
96824375, 96745318, 96571438, 96543718, 96513478, 96482735, 96473158, 96428735, 96354718, 96347158, 96248375, 96135478,
95714638, 95674318, 95631478, 95346718, 95341678, 95316478, 95147638,
94862375, 94682375, 94671358, 94653718, 94517638, 94376518, 94286735, 94167358,
93764158, 93746518, 93645718, 93615478, 93514678, 93461758, 93456718, 93451678, 93146758,
92846375, 92648735, 92468375,
91745638, 91657438, 91647358, 91634758, 91536478, 91435678,
89642375, 89624735, 89426735, 89264375, 89246735,
87652439, 87642359, 87632495, 87625439, 87624935, 87564239, 87562439, 87526439, 87524639, 87426359, 87425639, 87364295, 87342695, 87326495, 87264359, 87263495, 87246935.

-- 15.09.2018, 00:41 --

Ktina
А, понял: 87625439 это наибольшее число, не делящееся ни на одну из своих цифр, т.е. все остатки не только различные, но и все больше 0. Но я этим не ограничивал так как уже Ваш пример 129 имеет один из остатков нулевой. Сколько раз говорили, точнее формулируйте условия.

[Ktina]

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

Сколько раз говорили, точнее формулируйте условия.

На сей раз с условием всё в порядке. Это тот человек, который дал неверный ответ, по-своему понял условие.

[Dmitriy40]

Угу, я про это и говорю.

[waxtep]

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

Интересно как его получить без существенного перебора

У меня получилось только следующее: в смелом предположении, что наибольшее число не содержит единицу, хорошо восстанавливается его структура остатков (двойственность только по модулю $7$ - остаток должен быть равен $4$ или $6$, остальные остатки определяются однозначно). И тогда два глобальных варианта: $9\ldots735$ или $9\ldots375$. Их можно исследовать при помощи Св.Перебориуса (уже совсем скромного), или более кропотливым анализом остатков. Но, из каких соображений нет единицы, - не пробовал доказать