Алгоритм
.Чтобы определить наименьшее целое число, состоящее только из 7 или из комбинации семерок и нулей, которое без остатка делится на заданное положительное целое число, используется алгоритм, который выполняет итерации по возрастающим степеням числа 10, пока не будет найдено число, кратное n, состоящее только из семерок (например, 777777) или семерок и нулей (например, 777777000). Начальное пространство поиска находится в диапазоне от 1 до 10.
В каждой итерации к произведению предыдущего остатка на 10 прибавляется 7. Если остаток числа появляется более одного раза, это указывает на то, что данная последовательность цифр из семерок и нулей представляет число, кратное n, которое начинается с 7 и заканчивается на 0.
Если достигнут остаток 0, то это говорит о том, что число, начинающееся с цифры 7 и кратное числу n, найдено.
Если в текущем диапазоне поиска решение не обнаружено, то алгоритм расширяет диапазон поиска и продолжает итерации.
Ниже подробно описаны шаги алгоритма.
1. Создается словарь с именем remainder_positions для отслеживания остатков и их позиций в каждой итерации.
Создается переменная current_remainder с начальным значением 0.
2. Переменные digits_min и digits_max инициализируются начальными значениями 1 и 10 соответственно.
Они определяют пространство поиска числа из семерок и нулей, кратного n, и переменная num_digits изменяется
в диапазоне от digits_min до digits_max.
3. Затем запускается цикл while, который выполняется до тех пор, пока не будет найдено число из семерок и нулей, кратное n.
4. В цикле while переменная num_digits последовательно получает значение от digits_min до digits_max включительно.
5. Для каждого значения num_digits вычисляется остаток по формуле
(current_remainder ∗ 10 + 7) % n.
6. Если текущий остаток равен нулю, возвращается целое число, состоящее из последовательности семерок.
7. Если текущий остаток уже появлялся раньше, то из предыдущего и текущего блоков формируется число,
кратное числу n, которое начинается с 7 и заканчивается 0.
Для этого отыскивается позиция i предыдущего вхождения current_remainder в словаре remainder_ positions и целое число,
состоящее из последовательности 7, за которой следуют 0 с использованием выражения
'7' ∗ (num_digits – i) + '0' ∗ i.
8. Если текущий остаток ранее не появлялся, он добавляется в словарь
remainder_positions со своей позицией num_digits.
9. После завершения всех итераций в текущем пространстве поиска оно расширяется
путем установки digits_min равным digits_max и умножения digits_max на 10.
10. Шаги 4–9 повторяются до тех пор, пока не будет найдено число из семерок и нулей, кратное заданному числу n.
Если число из семерок и нулей не отыщется, то итерации будут продолжаться бесконечно.