Наибольшее число, делящееся на произведение своих цифр

[Ktina]

Для первых трёх $n\in\mathbb N$ легко в уме найти наибольшее $n$ - значное натуральное число, делящееся нацело на произведение своих десятичных цифр:
9, 36, 816.
Существует ли способ, позволяющий без перебора продолжить эту последовательность?

[angor6]

Ktina, считая в уме, уже при числе цифр $n=2$ приходится заняться перебором...

[Sphinx Pinastri]

Наверно, нужно уточнить задачу.

111...111
311...111
311...113

Сколь угодно большие числа данного вида удовлетворяют условиям при известных требованиях к числу единиц.

[nnosipov]

Sphinx Pinastri в сообщении #902276 писал(а):

Наверно, нужно уточнить задачу.

Задача уже точно сформулирована. Вчитайтесь в условие.

[alexo2]

Хм.. следующие числа в последовательности:
8832
89712
863136
Однако, моя прога интеллектуального перебора не может найти закономерности...

[Sender]

Можно с уверенностью сказать, что у таких чисел с числом цифр $9k$, $9k+1$, $9k+6$ первая цифра будет девяткой. В качестве доказательства достаточно рассмотреть числа вида $91\dots 12$, $91\dots 1$, $91\dots 15$ соответственно.

-- Пн сен 01, 2014 09:54:48 --

alexo2, шестизначное число должно быть не меньше $911115$.

[alexo2]

Sender в сообщении #902521 писал(а):

alexo2, шестизначное число должно быть не меньше $911115$.

Уже заметил сам - у меня 9-ка как старший разряд не участвовала...
Прошу прощения, уточненный список следующих чисел:
9612
93744
973728
Для 9-ти разрядов, кстати,
997711344

[patzer2097]

Обозначим через $K(n)$ самое большое целое число, которое записывается в десятичной системе $n$ цифрами и делится на произведение этих цифр. Такие числа обсуждались в этой теме, а тут я бы хотел сформулировать проблему, которая кажется мне интересной: какова асимптотика последовательности $K(n)$?

Cформулирую более конкретный вопрос. Положим $P(n)=10^{-n}K(n)$; можем ли мы доказать, что $P(n)\rightarrow1$ при $n\rightarrow\infty$? Пока я могу только видеть, что один из частичных пределов последовательности $P(n)$ равен единице: в самом деле, среди чисел $9\ldots91\ldots1$ при любом фиксированном числе девяток $a$ найдется такое, которое делится на $9^a$.

(ДОКАЗАТЕЛЬСТВО)

Нужно показать, что при любом $a$ найдется такое $b$, при котором число

$$u(a,b)=\sum_{i=0}^{b-1}10^i+9\sum_{j=b}^{a+b-1}10^j$$

делится на $9^a$. Это условие равносильно тому, что число

$$9u(a,b)=10^b-1+9\cdot10^b(10^a-1)$$

делится на $9^{a+1}$. Иными словами, нужно найти такое $b$, при котором $10^b\cdot(9\cdot10^a-8)$ сравнимо с $1$ по модулю $9^{a+1}$. Заметим, что подгруппы порядка $9^u$ циклической группы $\mathbb{Z}_{9^{a+1}}^*$ состоят из элементов вида $\alpha9^{a+1-u}+1$; поэтому элемент $10\in\mathbb{Z}_{9^{a+1}}^*$ порождает подгруппу всех чисел вида $9\alpha+1$, которой принадлежит и $9\cdot10^a-8$.

Впрочем, числам вида $9\ldots91\ldots1$, похоже, весьма далеко до оптимальных: для двух девяток требуется взять $63$ единицы, для трех девяток - $702$ единицы.

Можем ли мы сказать что-то большее об асимптотике последовательности $P(n)$?

Темы объединены. // maxal

[maxal]

Добавил последовательность A246757.

[patzer2097]

maxal Следующее число 999641938176, как показывают мои вычисления.

[maxal]

patzer2097, всё верно. Сейчас там уже 18 членов, и процесс идёт дальше ;)

[patzer2097]

maxal
Вот это да! А можете поделиться секретом вычисления этих значений - Вы перебираете все числа подряд или есть какие-то результаты, сокращающие перебор?

Кстати, возможно, я зря писал этот пост в новой теме, и его по-хорошему нужно было писать в этой теме. Впрочем, возможно, все хорошо и так. В любом случае, похоже, что экспериментальные данные голосуют за то, что $10^{-n}A246757(n)$ стремятся к единице экспоненциально быстро..

[nnosipov]

У меня вопрос по доказательству утверждения

patzer2097 в сообщении #903165 писал(а):

среди чисел $9\ldots91\ldots1$ при любом фиксированном числе девяток $a$ найдется такое, которое делится на $9^a$.

Смущает то, что $10$ не является образующим группы $\mathbb{Z}_{9^{a+1}}^*$.

[maxal]

patzer2097, я добавил PARI/GP код в последовательность. Идея в том, чтобы искать члены с фиксированным числом $k$ девяток в начале, тогда идти можно с шагом $9^k$.

Темы объединил.

[alexo2]

Интересно, существуют ли СС, в которых количество решений конечно?

И, если с максимальным частным от деления все понятно (111....), то как быть с минимальным? (то есть, последовательность с минимальным частным от деления - навскидку, эта последовательность не имеет ничего коррелирующего с последовательностью максимальных чисел как в первоначальном условии)

Для 4-рех разрядов минимальное частное равно 9, для 5-ти - 18, для 6 - ти - 12, для 7 -ми - 13 (число 1886976)