Задание №25. Делители и маски чисел

В задании №25 требуется найти числа, удовлетворяющие нескольким условиям, и вывести их вместе с вычисленной величиной. Условия могут относиться к делителям числа, его простым множителям или десятичной записи. Решение состоит из двух частей: перебора кандидатов в нужном порядке и точной проверки каждого кандидата. Сначала определяется, какие числа перебираются и что означает второй столбец ответа.

Делитель и его пара

Натуральные числа здесь начинаются с единицы. Натуральное число d является делителем числа n, если деление происходит без остатка. В Python это условие n % d == 0. Операция % возвращает остаток, а // даёт целую часть частного. После проверки делимости n // d равно точному частному.

У каждого делителя есть парный: если n=dq, то q=n/d тоже делитель. Хотя бы одно число пары не превосходит \sqrt n: если бы оба были больше корня, их произведение оказалось бы больше n. Поэтому достаточно искать меньшие делители до корня включительно и получать большие делением.

У числа 20 пары равны (1,20), (2,10) и (4,5). Исключение единицы и самого числа удаляет первую пару. При суммировании всех различных делителей каждый учитывается один раз; у квадрата совпавшие элементы пары нельзя складывать дважды. Но сумма минимального и максимального значений определяется иначе.

Первые пять чисел с нужной суммой крайних делителей

В задаче о сумме, оканчивающейся на 4 ↗ перебираются целые числа, строго большие 700\,000. Величина M равна сумме минимального и максимального натуральных делителей без единицы и самого числа. Если таких делителей нет, M=0. Нужны первые пять подходящих чисел по возрастанию и соответствующие значения M.

Почему достаточно первого делителя

Пусть d оказался первым делителем при поиске от двух вверх. Тогда он минимальный, а n/d максимальный среди разрешённых. Большему делителю соответствовал бы меньший парный, которого по выбору d нет. Поэтому после первого успеха поиск заканчивается:

M=d+\frac nd.

Если делителей от двух до корня включительно нет, число простое: у него только два натуральных делителя, единица и оно само. Оба исключены условием, поэтому возвращается ноль. Для 49 единственный разрешённый делитель равен 7. Он одновременно минимум и максимум, так что M=7+7=14. Это сумма двух крайних значений, а не сумма различных элементов множества.

Начало перебора

Строгое неравенство задаёт первое проверяемое число 700\,001. Оно простое и даёт ноль. У следующего числа минимальный делитель равен двум: M=2+350\,001=350\,003. Последняя цифра не подходит. Для 700\,003 первый делитель равен 37, сумма 37+18\,919=18\,956 также не подходит.

Первая строка ответа появляется при n=700\,004: сумма 2+350\,002=350\,004 оканчивается на четыре. Последняя десятичная цифра равна остатку при делении на десять, поэтому в программе используется M % 10 == 4. Следующее подходящее число 700\,009 имеет минимальный делитель 17: M=17+41\,177=41\,194.

Программа и результат

Функция edge_sum вычисляет сумму для одного числа. isqrt(n) возвращает целую часть квадратного корня без вычислений с дробными числами. Верхняя граница range не включается, поэтому прибавляется единица: сам корень тоже требуется проверить. Переменная found считает найденные строки, а не количество выполненных проверок.

from math import isqrt

def edge_sum(n):
    for d in range(
        2, isqrt(n) + 1
    ):
        if n % d == 0:
            return d + n // d
    return 0

n = 700001
found = 0
while found < 5:
    M = edge_sum(n)
    if M % 10 == 4:
        print(n, M)
        found += 1
    n += 1

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

Последние три строки получаются из пар (3,233341), (2,350012) и (2,350022). Все суммы оканчиваются на четыре, все числа больше заданной границы. Полноту первых пяти обеспечивает последовательный перебор, а не одна лишь проверка этих пяти строк.

Что меняется при другом наборе делителей

Сумма всех делителей и делитель с окончанием

Если требуется сумма всех различных делителей, остановка на первой паре уже неверна. Поиск проходит до корня полностью; в сумму добавляются обе стороны каждой пары, а при их равенстве только одна. В сумме всех натуральных делителей ↗ учитываются также единица и само число. Для 20 получается 1+2+4+5+10+20=42. В сумме без единицы и самого числа ↗ остаётся 2+4+5+10=21.

В поиске минимального делителя с окончанием 9 ↗ дополнительно запрещены сам делитель 9 и исходное число. У каждой пары проверяются обе стороны: подходящее окончание может оказаться только у большой. Среди всех разрешённых значений сохраняется минимум. Первый найденный большой парный делитель не обязательно минимален, поэтому ранняя остановка из основного примера сюда не переносится.

Простые делители и повторяющиеся множители

Простой делитель должен сам быть простым числом. Парный к минимальному делитель n/d может быть составным, то есть иметь делители кроме единицы и самого себя. Поэтому для суммы крайних простых делителей ↗ требуется разложение на простые множители. Оно получается последовательным делением: найденный множитель удаляется из остатка столько раз, сколько возможно.

def prime_factors(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

Функция принимает натуральное число. Каждый раз найденный множитель записывается в список, а остаток уменьшается. Найденный множитель прост: составной содержал бы меньший простой делитель, уже полностью удалённый из остатка. После цикла остаток больше единицы тоже прост: меньших делителей у него уже нет, и он добавляется. Список prime_factors(12) равен [2, 2, 3]. Для различных простых делителей из него получается множество set(factors), содержащее только 2 и 3.

Если исходное число простое, список состоит из самого числа. В задачах, исключающих само число, разрешённых простых делителей тогда нет и сумма равна нулю. У составного числа берутся минимум и максимум множества. При единственном различном простом делителе он занимает обе позиции: для 49 сумма опять равна 14.

Для произведения ровно двух простых множителей ↗ нужен список с повторениями: его длина должна быть равна двум. Число 49=7\cdot7 выполняет именно это требование, хотя дальнейшее условие на цифры ещё проверяется отдельно. Число 12=2\cdot2\cdot3 не выполняет: множителей три. У каждого из двух проверяется собственная запись. Требование ровно одной цифры 1 выражается как str(p).count("1") == 1, где p обозначает проверяемый множитель.

Выводимый множитель также определяется условием. В предыдущей задаче нужен больший, а в произведении множителей с единственным вхождением 43 ↗ меньший. Подстрока 43 означает соседние цифры в указанном порядке; наличие отдельно четвёрки и тройки недостаточно.

Проверка вычисленной величины

После получения суммы все дополнительные требования применяются к ней одновременно. Палиндром одинаково читается в обе стороны: для записи s = str(M) проверяется s == s[::-1]. В задаче о палиндроме также требуется M>50000. В условии о полном квадрате ↗ используются isqrt(M)**2 == M и отдельное строгое ограничение M>70000.

В сумме с окончанием 63 и условием кратности ↗ нужны одновременно M % 100 == 63 и делимость на количество различных простых делителей. Для 12 такое количество равно двум, а не трём. В условии об остатке 3 при делении на 7 ↗ используется M % 7 == 3; это не проверка последней цифры.

В поиске простой суммы с единственным вхождением 567 ↗ проверяются нижняя граница, простота самой суммы и число вхождений подстроки. Простота слагаемых не гарантирует простоты суммы: например, сумма двух нечётных простых чётна и больше двух. Простота проверяется отсутствием делителей от двух до корня; числа меньше двух простыми не являются.

Маска числа: проверка десятичной записи

Маска описывает допустимую запись числа. Обычная цифра должна совпасть с такой же цифрой. Знак ? заменяет ровно одну произвольную цифру, а * любую последовательность цифр, в том числе пустую. Совпадать должна вся запись, а не только её фрагмент.

В задаче с маской 1234*54 и делением на 21 ↗ нужны все натуральные числа, не превышающие 10^8. Число одновременно соответствует маске и делится на 21. Вместо всех чисел можно сразу перебирать только кратные: 21,42,63,\ldots. Ни один подходящий результат так не теряется.

Функция fnmatchcase сопоставляет строку с маской целиком. В общем случае её знаки заменяют символы; здесь строка str(n) состоит только из цифр, поэтому совпадение имеет нужный смысл. Название функции не означает работу с файлами: ей передаются две обычные строки.

from fnmatch import (
    fnmatchcase,
)

for n in range(
    21, 10**8 + 1, 21
):
    if fnmatchcase(
        str(n), "1234*54"
    ):
        print(n, n // 21)

Прибавление единицы к верхней границе сохраняет формулировку "не превышающие". В этой конкретной маске число 10^8 не подходит, но проверка границы остаётся точной. Счётчика пяти успехов здесь нет: условие требует все результаты. Во втором столбце выводится частное, а не сумма делителей.

Результат можно проверить через длину подстановки. Без звёздочки уже шесть цифр, поэтому она заменяет ноль, одну или две цифры. Пустая подстановка даёт 123454, остаток от деления на 21 равен 16. Если подставляется одна цифра a, получается n=1234054+100a: справа от неё остаются две цифры 54. Перебор a от нуля до девяти оставляет только a=2.

Для подстановки длины две её значение x меняется от 00 до 99, а число равно n=12340054+100x. Проверка делимости на 21 оставляет подстановки 11, 32, 53, 74, 95. Вместе с одноцифровой подстановкой они дают ровно шесть строк таблицы.

В маске 12345?7?8 ↗ длина всегда девять цифр. Два вопросительных знака дают 10\cdot10=100 подстановок. Например, подстановка 0 и 9 даёт 123450798, а деление на требуемое 23 даёт 5367426. При малом числе свободных разрядов перебор подстановок короче перебора всех кратных. У звёздочки дополнительно перебираются все допустимые длины, включая нулевую; внутренние нули вроде 00 сохраняются. Полученные числа сортируются численно и при необходимости очищаются от повторов.

Возможные ловушки

• Остановиться после пяти проверок. В поиске первых пяти чисел ↗ неподходящие кандидаты не занимают строк ответа. Счётчик увеличивается только при выполнении всех требований, а начало строго больше указанной границы.
• Потерять корень или дважды сложить его. Поиск с границей меньше корня пропускает квадрат простого. При сумме различных делителей ↗ совпавшие элементы пары считаются один раз; при сумме минимума и максимума одно значение может занимать обе позиции.
• Заменить простые делители всеми делителями. В сумме крайних простых ↗ парный максимум может быть составным и потому запрещён. Нужны крайние значения именно множества простых делителей.
• Удалить повторения раньше проверки произведения. Для ровно двух простых множителей ↗ длина множества не заменяет длину разложения. Повторения учитываются до проверки количества; условие на запись применяется к каждому множителю.
• Запретить пустую звёздочку или разрешить пустой вопросительный знак. Это меняет множество кандидатов в маске со звёздочкой ↗ и маске с вопросительными знаками ↗. У * длина может быть нулевой, у ? она всегда равна единице.