Обязательно ли в десятичной записи числа будут единицы?

[Ktina]

Рассмотрим последовательность:
1 11 12 111 112 1111 1112 1116... - числа, которые делятся на квадрат произведения своих десятичных цифр (или на произведение квадратов своих десятичных цифр, что одно и то же).
Обязательно ли в десятичной записи каждого из таких чисел бутет хотя бы одна цифра 1?

[svv]

Наименьшее такое число без единиц — это $2322432$. Произведение цифр $576$, квадрат $331776$, и $2322432/331776=7$.

[arseniiv]

(Оффтоп)

Опять десятичная.

[Ktina]

svv в сообщении #1233703 писал(а):

Наименьшее такое число без единиц — это $2322432$. Произведение цифр $576$, квадрат $331776$, и $2322432/331776=7$.

Большое спасибо!
А как нашли?

[svv]

С помощью программы.
Интересно, что второго примера найти не удалось, хотя проверил числа до трёх миллиардов.

[Dmitriy40]

Если нигде не ошибся, то следующего примера нет вплоть до $3 \cdot 10^{14}$.

[Ktina]

svv в сообщении #1233831 писал(а):

С помощью программы.

Она с закрытым кодом, что ли?

[Dmitriy40]

Ну вот простая программа:

Используется синтаксис Delphi

var     x, i, d: integer;
        s: string;
begin
        for x := 1 to 99999999 do begin
                s := IntToStr(x); d := 1;
                if Pos('0', s) > 0 then continue;
                if Pos('1', s) > 0 then continue;
                for i := 1 to Length(s) do d := d * (Ord(s[i]) - $30);
                if d > 46340 then continue;
                if (x mod (d * d)) <> 0 then continue;
                Writeln(x, '/', d, '^2=', x div (d * d));
        end;
end.

Найденный результат выдаёт за 0.6с, до 100 миллионов отрабатывает 30с. До триллионов ей не добраться, медленна.

[photon]

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

Ну вот простая программа:

Я думаю, для больших чисел быстрее будет идти по квадратам и проверять являются ли они подходящими для какого-нибудь числа, хотя код, конечно, немного усложнится.

[Dmitriy40]

Да и так уже ускорил программу, теперь время счёта с нуля до $10^{11}, 10^{12}, 10^{13}, 10^{14}, 10^{15}$: 1.5с, 6.3с, 34с, 168c, 940с. Видно что при увеличении диапазона в 10 раз время растёт лишь примерно в 5 раз. Так что примерно за сутки можно досчитать до $10^{18}$. Теперь мне интересно какой прирост скорости даст код внутреннего цикла (на интервале $10^{10}$) на асм64.

[Ktina]

Dmitriy40
Большое спасибо за код!

[Dmitriy40]

(Скорость на асм64)

Переписал, потестировал, время счёта с нуля до $10^{12}, 10^{13}, 10^{14}, 10^{15}$: 0.34с, 1.8с, 9.3с, 52с. Классно. Зависимость очевидно та же. За полдня можно добраться до $10^{19}$.

[photon]

Dmitriy40, больше решений нет пока?

[Dmitriy40]

photon
Нет, проверено уже до $10^{18}$, ничего не найдено.

(Оффтоп)

Забавная у меня программа получилась из-за оптимизации, чем ближе к степени 10 (больше девяток и вообще больших цифр в числе) тем быстрее идёт счёт. Это конечно логично, перебор обрывается как можно раньше, но всё равно забавно. К примеру от $982 \cdot 10^{15}$ до $10^{18}$ скорость была выше $10^{15}$ в секунду!

[kotenok gav]

А какая оптимизация?
Просто очень хочется проверить на моем очень мощном компьютере.