Алгоритмы поиска натуральных чисел в заданном диапазоне на Python

Расширенные примеры поиска натуральных чисел с необычными условиями

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

Пример 1: Поиск совершенных чисел (числа, равные сумме своих собственных делителей)

def perfect_numbers(limit):
    perfects = []
    for n in range(2, limit+1):
        # сумма делителей, исключая само число
        divisors_sum = 0
        for i in range(1, int(n**0.5) + 1):
            if n % i == 0:
                divisors_sum += i
                if i != 1 and i != n // i:
                    divisors_sum += n // i
        if divisors_sum == n:
            perfects.append(n)
    return perfects

print(perfect_numbers(10000))

[6, 28, 496, 8128]

Пояснение:

Для каждого числа n ищем делители до sqrt(n). Если делитель i найден, добавляем i и, если он не равен квадратному корню, добавляем n//i. Сравниваем сумму с n. Важно начинать с 2, так как 1 не считается совершенным (сумма собственных делителей 1 равна 0).

Пример 2: Поиск дружественных чисел (два числа, сумма делителей каждого равна другому)

def divisor_sum(n):
    s = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            s += i
            if i != 1 and i != n // i:
                s += n // i
    return s

def amicable_pairs(limit):
    pairs = []
    for a in range(2, limit+1):
        b = divisor_sum(a)
        if b > a and b <= limit and divisor_sum(b) == a:
            pairs.append((a, b))
    return pairs

print(amicable_pairs(10000))

[(220, 284), (1184, 1210), (2620, 2924), (5020, 5564), (6232, 6368)]

Пояснение:

Функция divisor_sum вычисляет сумму собственных делителей. Для каждого a вычисляем b = divisor_sum(a). Если b > a (чтобы избежать дублирования), b не превышает limit и сумма делителей b равна a, то пара дружественная.

Пример 3: Поиск чисел Фибоначчи в заданном диапазоне с помощью генератора

def fibonacci_in_range(start, end):
    a, b = 1, 1
    while a <= end:
        if a >= start:
            yield a
        a, b = b, a + b

result = list(fibonacci_in_range(1, 1000))
print(result)

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]

Пояснение:

Классическая итерация Фибоначчи с условием остановки. Генератор экономит память, так как числа не хранятся все сразу. Обратите внимание: первое число 1 встречается дважды (по определению последовательности).

Пример 4: Поиск чисел, являющихся палиндромами сразу в десятичной и двоичной системах

def is_palindrome(num, base):
    s = ''
    temp = num
    while temp > 0:
        s = str(temp % base) + s
        temp //= base
    return s == s[::-1]

def double_palindromes(limit):
    res = []
    for n in range(1, limit+1):
        if is_palindrome(n, 10) and is_palindrome(n, 2):
            res.append(n)
    return res

print(double_palindromes(500))

[1, 3, 5, 7, 9, 33, 99, 313, 585]

Пояснение:

Функция is_palindrome преобразует число в строку в указанной системе счисления и проверяет, является ли строка палиндромом. Затем перебираем числа и проверяем оба условия.

Пример 5: Поиск чисел Харшад (делятся на сумму своих цифр) с кэшированием суммы цифр

from functools import lru_cache

@lru_cache(maxsize=None)
def digit_sum(x):
    return sum(int(d) for d in str(x))

def harshad_numbers(limit):
    return [n for n in range(1, limit+1) if n % digit_sum(n) == 0]

print(harshad_numbers(200))

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 18, 20, 21, 24, 27, 30, 36, 40, 42, 45, 48, 50, 54, 60, 63, 70, 72, 80, 81, 84, 90, 100, 102, 108, 110, 111, 112, 114, 117, 120, 126, 132, 133, 135, 140, 144, 150, 152, 153, 156, 162, 171, 180, 190, 192, 195, 198, 200]
Пояснение:
Декоратор @lru_cache запоминает результаты функции digit_sum, что ускоряет повторные вызовы (полезно, если одинаковые числа встречаются часто, но в данном примере каждое число проверяется один раз). В более сложных задачах кэш может дать выигрыш.
Пример 6: Использование рекурсии для поиска чисел по условию (например, числа, сумма цифр которых равна заданному числу K)
Пример 
def find_by_digit_sum(current, remaining_digits, target_sum, results):
    if remaining_digits == 0:
        if current > 0 and sum(int(d) for d in str(current)) == target_sum:
            results.append(current)
        return
    # последняя цифра может быть от 1 до 9, остальные от 0
    start = 1 if current == 0 else 0
    for d in range(start, 10):
        find_by_digit_sum(current*10 + d, remaining_digits-1, target_sum, results)

# найти все трёхзначные числа, сумма цифр которых равна 15
res = []
find_by_digit_sum(0, 3, 15, res)
res.sort()
print(res)
[159, 168, 177, 186, 195, 249, 258, 267, 276, 285, 294, 339, 348, 357, 366, 375, 384, 393, 429, 438, 447, 456, 465, 474, 483, 492, 519, 528, 537, 546, 555, 564, 573, 582, 591, 609, 618, 627, 636, 645, 654, 663, 672, 681, 690, 708, 717, 726, 735, 744, 753, 762, 771, 780, 807, 816, 825, 834, 843, 852, 861, 870, 906, 915, 924, 933, 942, 951, 960]
Пояснение:
Рекурсивно строим числа, добавляя цифры. Параметр current хранит частично сформированное число, remaining_digits - сколько цифр ещё добавить. Для первой цифры диапазон от 1 до 9, для остальных от 0 до 9. Когда число построено (remaining_digits == 0), проверяем сумму цифр. Такой подход позволяет избежать перебора всех чисел от 100 до 999, а сразу генерирует подходящие по разрядности.