Можно ли используя только цифры 0, 5, 8 записать три...

[gipokrat]

Можно ли используя только цифры 0, 5, 8 записать три числа, одно из которых равно произведению двух других?

[Gagarin1968]

Можно. Например используя ноль в качестве сомножителя и, понятно, произведения.

[gipokrat]

Gagarin1968 в сообщении #1722758 писал(а):

Можно. Например используя ноль в качестве сомножителя и, понятно, произведения.

Так задача становится совсем тривиальной. Есть пример для трёх ненулевых чисел.

[Gagarin1968]

gipokrat в сообщении #1722759 писал(а):

Есть пример для трёх ненулевых чисел.

Вы меняете условия на ходу? В стартовом посте ставился единственный вопрос: можно ли. Я ответил, что можно, и привёл пример (пусть и тривиальный).
Вот пример ненамного сложней:

$\dfrac {58}{85}\cdot \dfrac {85}{58}=\dfrac {85085058}{85085058}$

Это устроит?

[gipokrat]

Gagarin1968
Увы, не устроит. Есть пример для трёх ненулевых чисел, в котором не используются дроби. И не меняю на ходу, а уточняю.

[Booker48]

gipokrat в сообщении #1722765 писал(а):

Есть пример для трёх ненулевых чисел

Наверное, стоит уточнить ещё
$5^0 \cdot 8^0 = 58^0$

[eugensk]

$5 \cdot 8 = 50_8$

[gipokrat]

Booker48 в сообщении #1722769 писал(а):

Наверное, стоит уточнить ещё
...

Уточняю.
Можно ли, используя только цифры 0, 5, 8, записать три попарно различных натуральных числа, десятичная запись каждого из которых не содержит цифр, отличных от выше упомянутых, причём одно из этих трёх чисел равно произведению двух других?

[gris]

интересная задача.
Конечно, тыканьем в калькулятор несложно найти примерчик
$5888 \times 85055805885 = 500808585050880 $
да ещё ноликов сзади наставить
но наверняка есть теоретические соображения, которые в голову не пролезают

[EUgeneUS]

gris в сообщении #1722810 писал(а):

но наверняка есть теоретические соображения, которые в голову не пролезают

У меня теоретических соображений хватило только на то, что произведение должно оканчиваться на $080$ или $880$. А дальше перебором

[ex-math]

gris
Интересно, это минимальный пример?

[gris]

ex-math, минимальный по произведению? Я слепил примитивный алгоритм перебора по сомножителям, на котором решение нашлось за десять минут на хилой железяке. Повезло. Думаю, что решение минимальное, но не единственное. Мне интересен сам алгоритм перебора, а не его многочасовая реализация. А решения с двумя сомножителями, не кратными 10, можно скорее всего обосновать теоретическими соображениями. Типа сконструировать с большим количеством нулей в серединках.
Ждём ТС. Он излечит мою неуверенность

[gipokrat]

gris в сообщении #1722827 писал(а):

ex-math, минимальный по произведению? Я слепил примитивный алгоритм перебора по сомножителям, на котором решение нашлось за десять минут на хилой железяке. Повезло. Думаю, что решение минимальное, но не единственное. Мне интересен сам алгоритм перебора, а не его многочасовая реализация. А решения с двумя сомножителями, не кратными 10, можно скорее всего обосновать теоретическими соображениями. Типа сконструировать с большим количеством нулей в серединках.
Ждём ТС. Он излечит мою неуверенность

Проверил полный перебор с отсечениями по разрядам.

Минимальный по произведению пример таков:

$$5888\cdot 85055805885 = 500808585050880.$$

Меньшего произведения не существует. Более того, на этом уровне разложение единственно с точностью до перестановки сомножителей.

Идея алгоритма такая. Перебирается меньший сомножитель $a\le \sqrt N$, где $N=500808585050880$, причём в десятичной записи $a$ разрешены только цифры $0,5,8$.

Далее, для фиксированного $a$ и фиксированной длины второго сомножителя $b$, цифры числа $b$ строятся справа налево. Если $a$ имеет $m$ цифр, то очередная цифра произведения $c=ab$ однозначно определяется состоянием

$$(j,\kappa,d_1,\dots,d_{m-1}),$$

где $j$ --- номер разряда, $\kappa$ --- текущий перенос, а $d_1,\dots,d_{m-1}$ --- последние $m-1$ уже выбранных цифр числа $b$.

Если очередная цифра $c$ не принадлежит множеству $\{0,5,8\}$, соответствующая ветвь сразу отбрасывается. То есть перебор идёт не по всем сомножителям подряд, а только по допустимым разрядным продолжениям.

В результате до числа $500808585050880$ решений нет, а на этом уровне имеется решение

$$500808585050880 = 5888\cdot 85055805885.$$

[gris]

хотя огорчает привязка к десятичной системе, но есть простор для исследований. Даже если зафиксировать <как это называется? не паттерн же...> множество допустимых цифр [0,5,8]. Ну или его длину — 3. Ровно три. Здесь есть такие направления: есть множества, которые сразу отсекаются например по одной последней цифре: [2,3,7] как не перемножай на конце допустимую цифру не получишь; или по двум последним цифрам всех сомножителей, например, [4,7,9]. Некоторые множества имеют варианты нескольких последних цифр. И наверное это и есть алгоритм построения примера у ТС. А я всё больше перебором с предварительным построение вектора допустимых сомножителей. Много их, миллиарды! Памяти не хватает, но есть ухищрения. Некоторые первые примеры находятся довольно далеко: $997 \times 7099007 = 7077709979 [0, 7, 9]$ и требуют долгого ожидания результатов перебора. Но исследования и поиск эффективных алгоритмов продолжаются. Хотелось бы, чтобы ТС закинул ещё парочку примеров с [0,5,8]. Тема интересная.

[gipokrat]

gris, спасибо! Думаю, это естественно называть не «паттерном», а, например, алфавитом цифр или множеством разрешённых цифр.

То есть фиксируем множество

$$ A\subset\{0,1,\ldots,9\} $$

и рассматриваем натуральные числа, десятичная запись которых является словом над алфавитом $A$.

С этой точки зрения задача действительно становится задачей о замкнутости/незамкнутости такого «цифрового языка» относительно умножения: существуют ли различные натуральные числа $a,b,c$, записанные только цифрами из $A$, такие что

$$ ab=c. $$

Для $A=\{0,5,8\}$ из одного примера сразу получается бесконечно много новых. Например, из

$$ 5888\cdot 85055805885=500808585050880 $$

получаем при любом $t\geq 15$:

$$ 5888\cdot(85055805885\cdot 10^t+85055805885) = 500808585050880\cdot 10^t+500808585050880. $$

Так как между блоками просто вставляются нули, все цифры по-прежнему принадлежат множеству $\{0,5,8\}$.

Например:

$$ 5888\cdot 85055805885000085055805885 = 500808585050880500808585050880. $$

Ещё один пример:

$$ 5888\cdot 850558058850000085055805885 = 5008085850508800500808585050880. $$

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