НОД чисел, отличающихся порядком цифр

[Димыч]

Давно хочу поделиться задачкой, которую я придумал еще школьником. Для dxdy.ru она слишком несерьезная (здесь был оффтоп, который я удалил), но тут должна прийтись в самый раз.

Предисловие 

Показать скрытый текст

Всем, наверное, хорошо известны задачи, где требуется найти числа, увеличивающиеся в несколько раз при перестановке цифр. Но при этом всегда рассматриваются частные случаи перестановок — когда цифры переставляются в обратном порядке или одна цифра переставляется из конца в начало/из начала в конец. Как ни странно, я не встречал рассмотрения случая произвольных перестановок. Но задача поиска таких чисел — это не совсем та задача, которую я хочу предложить. Одним из моих любимых развлечений с детства было решение интересных математических задач, но поскольку я лентяй, я обычно предпочитаю простые задачи, решением которых можно заняться в уме. Для только что упомянутой задачи не существует 2- и 3-значных решений, а 4-значные в уме искать уже трудновато, поэтому я решил придумать что-то попроще, что имело бы смысл и для более коротких чисел. И придумал.

В простейшем варианте, решаемом в уме за несколько минут, задача такая: какое максимальное значение может иметь НОД 2 двузначных чисел, отличающихся порядком цифр. Несмотря на свою простоту, задачка зацепила меня тем, что интуитивно я не смог догадаться об ответе, хотя, казалось бы, что может быть неизвестного в двузначных числах.
Естественно, задача легко обобщается: какое максимальное значение может иметь НОД k n-значных чисел, отличающихся порядком цифр.
В этой задаче мне кажется естественным понимать n-значные числа в расширенном смысле, разрешая 0 в качестве первой цифры, но, если хотите, можете ограничиться только «настоящими» n-значными числами.
Сам я (вроде бы) решил задачу для n=3 и всех k (т. е. k=2,3,4,5,6) и для k=2 и всех n (и даже послал эту последовательность в OEIS). Кроме того, довольно очевидны соображения для случаев, когда k максимально возможное для данного n или близко к нему.

[sek140675]

 

[Илья]

максимальное значение может иметь НОД 2 двузначных чисел, отличающихся порядком цифр.

Если возможно использование двухзначных цифр с одинаковыми цифрами, то напрашивается ответ 22.
Если с разными цифрами, то 

[square]

Давно хочу поделиться задачкой, которую я придумал еще школьником. Для dxdy.ru она слишком несерьезная (по-моему, она даже менее серьезная, чем поиск магических квадратов из чисел Смита ),

Показать скрытый текст

А что, вы можете ликвидировать пробелы в последовательности А170928 из магических констант квадратов из чисел Смита?

Впрочем, два знака вопроса я уже убрала (результаты будут завтра отправлены в Энциклопедию). Остался один неизвестный квдарат - 8-го порядка.
Если задача такая уж несерьёзная, давайте ваше решение.
Кстати, на dxdy.ru тема "Магические квадраты" активна уже 2 года.
И ещё: квадрат 3-го порядка из последовательных смитов с трудом нашёл профессор из США. А квадрат 4-го порядка из последовательных смитов и он пока не нашёл.
Может, у вас есть решение? А мы голову ломаем...

[General]

Интересно!
А почему думаете, что для dxdy несерьёзная. Там же тоже люди разными аспектами математики интересуются

Тема перестановки цифр мне очень близка, когда проводил интернет-олимпиаду, включил туда //текст доступен после регистрации//предпоследней цифры.

Про 2-значные, пока вариант навскидку: 9. Проверю, может, удастся улучшить

Не понял, что у Вас k и что n? Просто числа то k-значные, то n-значные

[General]

Илья, так дело в том, что числа, для которых вычисляется нОД, должны состоять из одинаковых цифр. НОД (18, 81)=9

[Димыч]

Числа n-значные, а k — это число чисел
Насчет магических квадратов и серьезности — не надо воспринимать то, что я пишу, слишком серьезно… Не только в данном случае, но и вообще, если только я не оговариваюсь, что пишу серьезно.
Пишу серьезно: если я кого-то обидел, прошу прощения.
Когда я пишу о числах, отличающихся порядком цифр, я имею в виду отличающиеся числа

[firemen]

отличающиеся или неотличающиеся, НОД будет все равно равен наименьшему положительному числу при вычитании с большего меньшее..
или я что-то пропутсил? ))
здаёмси!

[General]

Ну вот, например, НОД (19, 91)=1

[Smith]

ребят, расскажите - в чем прикол раскладывать цифры на составляющие? мне правда интересно, но пока я не понял - напоминает Кая в старом мультике о Снежной Королеве: он складывал льдинки и считал их... а для чего? для меня так и осталось загадкой с тех пор 

[General]

Брута поднял глаза. На самом верху башни металлическими полосами был закреплен сверкающий на солнце большой диск.
– Что это? – прошептал он.
– Причина, по которой у Омнии больше нет флота, – ответил Ом. – Вот почему так полезно иметь под рукой нескольких философов. Они размышляют себе на тему «Истина – это красота, или красота – это истина?» или «Производит ли шум падающее в лесу дерево, если никто его не слышит?», а потом, когда ты уже решишь, что они вообще вот-вот обслюнявятся, один из них и говорит этак невзначай: «Интересной демонстрацией принципов оптики будет размещение на высоком месте тридцатифутового параболического зеркала, способного направлять солнечные лучи на вражеский флот». Философам приходят в голову удивительные идеи. А незадолго до этого в целях демонстрации принципа рычага было изобретено замысловатое устройство, способное метать шары горящей серы на расстояние в две мили. А до этого, насколько я помню, было придумано какое-то подводное судно, которое втыкало в днища кораблей заостренные бревна.

"Мелкие Боги", Т.Пратчетт

[Илья]

Достойный ответ.

[General]

Подумал ещё над задачей: а ведь одной тройкой из девятки можно пожертвовать, зато получить четвёрку: НСД(84, 48)=12