Программа для поиска приветливых чисел

Question

Программа для поиска приветливых чисел

Рейтинг: 9Ответов: 3Опубликовано: 12.04.2023

Назовём натуральное число приветливым, если для любого натурального n⩾2 энная цифра этого числа равна остатку этого числа при делении на n . Например, число 2123 является приветливым, так как даёт остаток 1 при делении на 2, остаток 2 при делении на 3 и остаток 3 при делении на 4.

Вот все приветливые числа, не превышающие 10 млн:

10 11 20 21 30 31 40 41 50 51 60 61 70 71 80 81 90 91 211 300 302 511 600 602 811 900 902 1002 1022 1101 1121 2103 2123 3000 3020 4002 4022 4101 4121 5103 5123 6000 6020 7002 7022 7101 7121 8103 8123 9000 9020 11013 11031 11113 11131 11213 11231 20004 20022 20104 20122 20204 20222 30000 30100 30200 41013 41031 41113 41131 41213 41231 50004 50022 50104 50122 50204 50222 60000 60100 60200 71013 71031 71113 71131 71213 71231 80004 80022 80104 80122 80204 80222 90000 90100 90200 101044 110133 212105 300000 302222 311311 401044 410133 512105 600000 602222 611311 701044 710133 812105 900000 902222 911311 1123151 2121353 3103035 5010040 5012146 5113015 7020020 7022126

Разумеется, эти числа были найдены с помощью программы:

def is_friendly(number):
    str_number = str(number)
    length = len(str_number)

    for i in range(2, length + 1):
        if int(str_number[i - 1]) != number % i:
            return False

    return True

def main():
    for number in range(10, 10000001):
        if is_friendly(number):
            print(number)

if __name__ == "__main__":
    main()

Однако программа эта работает чудовищно медленно, поэтому не годится для поиска приветливых чисел, превышающих 10 млн.

Пожалуйста, помогите оптимизировать код и ускорить программу. Заранее благодарю!

python оптимизация теория-чисел арифметика

Источник: Stack Overflow на русском

Answer 1

▲ 11Принят

Простой перебор m-значных чисел требует просмотреть 10^m - 10^m-1 чисел.

Эникейщик предложил сократить перебор цифр для небольших номеров разрядов - остаток от деления должен быть строго меньше номера разряда.

Ещё один способ сократить перебор - учесть связи между разрядами i и j если первый делится на второй. В этом случае для любого n верно что n % j = (n % i) % j (% - взятие остатка от деления). Левая часть равенства - цифра в разряде j (d_j), в скобках в правой части цифра в разряде i (d_i). Следовательно d_i % j = d_j.

Например: d₃ = 2, тогда d₁₂ может принимать значения 2, 5 или 8.

Для сравнения таблица числа кандидатов:

 m     все       с учётом            с учётом
      числа   малых разрядов      малых разрядов и
                               связи между разрядами

 1       9              9                9
 2      90             18               18
 3     900             54               54
 4     9e3            216              108
 5     9e4           1080              540
 6     9e5           6480              540
 7     9e6          45360             3780
 8     9e7         362880             7560
 9     9e8        3265920            22680
10     9e9       32659200            22680
11    9e10      3.26592e8           226800
12    9e11      3.26592e9           189000
13    9e12     3.26592e10          1890000
14    9e13     3.26592e11          1350000
15    9e14     3.26592e12           918000
.
.
.
42    9e41     3.26592e39       2970000000
43    9e42     3.26592e40      29700000000

Код ниже использует и малые разряды и связь. Это рекурсивный поиск от второго разряда до младшего. Если поиск сумел построить все цифры, к заготовке добавляется старший разряд. Получившееся число проверяется is_friendly. За четыре минуты будут найдены все известные мне приветливые числа. Самое большое из них - двадцатизначное:

for m in range(1, 21):
    found = []

    d = [0] * (m + 1)

    def is_friendly(n):
        return all(n % i == d[i] for i in range(2, m + 1))

    def make_pred(j):
        return lambda e: e % j == d[j]

    preds = tuple(
        tuple(make_pred(j) for j in range(2, i) if i % j == 0)
        for i in range(m + 1)
    )

    def digits(i):
        digits = range(min(i, 10))
        for p in preds[i]:
            digits = filter(p, digits)
        return digits

    def search(i, n):
        if i > m:
            for e in range(1, 10):
                # d[1] = e
                n1 = 10 ** (m - 1) * e + n
                if is_friendly(n1):
                    found.append(n1)
            return

        for e in digits(i):
            d[i] = e
            search(i + 1, 10 * n + e)

    search(2, 0)

    print(m, len(found))
    for n in sorted(found):
        print(f'    {n}')

Карта местности:

 m: количество: примеры

 1: 10: 1 2 3 4 5 6 7 8 9
 2: 18: 10 11 20 21 30 31 40 41 50 51 60 61 70 71 80 81 90 91
 3:  9: 211 300 302 511 600 602 811 900 902
 4: 24: 1002 ... 9020
 5: 45: 11013 ... 90200
 6: 18: 101044 ... 911311
 7:  8: 1123151 2121353 3103035 5010040 5012146 5113015 7020020 7022126
 8: 17: 11133163 ... 91232567
 9:  9: 101044444 ... 900000540
10: 96: 1000405404 ... 9123455759
11:  3: 30204244844 60200244500 90022046622
12: 14: 101044141444 ... 901044647404
13:  5: 2103034705335 3111312173713 6002202202362 8010442044544 9111211577917
14: 11: 10004044347084 ... 80222222822282
15: 19: 101044241414524 ... 910133510389353
16:  5: 4020322088789288 ... 8010446444540644
17:  1: 81031327310329671
18:  1: 902232028812008258
19:  0:
20:  3: 10000024006072048020 21111111710181114721 80200240800854581880
21:  0:
.
. здесь нет ни одного числа
.
60:  0:

С помощью китайской теоремы об остатках можно ускорить перебор ещё примерно в пятнадцать раз. Если известны около 2/3 старших разрядов, младшие разряды можно восстановить без перебора. Программу это сильно раздувает, я её тут не привожу.

Главный вопрос - есть ли приветливые числа большие 10²⁰? Перебор уже дошёл до 10⁶⁰ - ничего не найдено. Я думаю что их нет, доказать не могу.

Answer 2

▲ 4

Я бы использовал Pool из модуля multiprocessing, чтобы создать пул процессов для параллельных вычислений. Это ускорит работу. Метод map из класса Pool вычисляет значения для всех чисел в диапазоне от 10 до 100лямов (или сколько нужно) и потом создаем список дружественных чисел. Обработка идет быстрее. До 100 лямов у меня занял просчет 5 секунд

from multiprocessing import Pool

def generate_friendly_numbers(max_value):
    # Создаем пул проц. для параллельных вычислений
    with Pool() as pool:
        # Вычисляем значения для всех чисел френдли в диапазоне от 10 до 100 лямов
        friendly_numbers = pool.map(is_friendly, range(10, max_value + 1))
    return [number for number, is_friendly in zip(range(10, max_value + 1), friendly_numbers) if is_friendly]

def is_friendly(number):
    str_number = str(number)
    length = len(str_number)

    for i in range(2, length + 1):
        if int(str_number[i - 1]) != number % i:
            return False

    return True

def main():
    friendly_numbers = generate_friendly_numbers(100000000)
    for number in friendly_numbers:
        print(number)

if __name__ == "__main__":
    main()

Answer 3

▲ 2

Я использовал numba для ускорения процесса поиска чисел.

from numba import njit, prange


@njit(fastmath=True)
def to_int(number): # так как в нумбе не работает int() надо выворачиваться таким образом
    int_number = 0
    for i in range(len(number)):
        i_number = 0
        for j in range(10):
            if (number[i] == str(j)):
                i_number = j
        int_number += i_number * 10 ** (len(number) - i - 1)
    return int_number

@njit(fastmath=True) # ускоряет выполнение вычислений
def is_friendly(number):
    str_number = str(number)
    length = len(str_number)

    for i in range(2, length + 1):
        if to_int(str_number[i - 1]) != number % i:
            return False

    return True

@njit(fastmath=True, parallel=True) # включаем распараллеливание и ускорение вычислений
def main():
    for number in prange(10, 10_000_001): # prange тот же самый range но поддерживает распараллеливание
        if is_friendly(number):
            print(number)

if __name__ == "__main__":
    main()

Программа для поиска приветливых чисел

Ответы