Задание 25

Текст задачи:

Алгоритм решения:

Нужно найти такую последовательность чисел, длинною 5, начинающиюся с 700000, что каждый следующий элемент имеет больше делителей. Иными словами, нужно найти такие числа, что их количество делителей постоянно растёт. Особенность этой задачи в том, что числа могут идти неподряд, а c промежуток.

Функция для нахождения делителей числа:

def find_divisors(number):
    divisors_set = set()
    for divisor in range(1, int(number**0.5) + 1):
        if number % divisor == 0:
            divisors_set.add(divisor)
            divisors_set.add(number / divisor)
    return len(divisors_set)

Это основая часть кода. Функция принимает число, а затем ищет делители числа до корень + 1. Этот метод связан со свойством делителей числа. Данная функция универсальна, и применяется во многих задачах на ЕГЭ.

Более подробно познакомиться с этой функцией поможет Алексей Кабанов

Основное тело алгоритма:

last_divisors = find_divisors(700000) 
numbers_list = [700000]

for number in range(700001, 1000000):
    current_divisors = find_divisors(number)
    if current_divisors > last_divisors: 
        numbers_list.append(number)         
        last_divisors = current_divisors
    if len(numbers_list) ==  5:
        for num in numbers_list:
            print(num, find_divisors(num))
        break    

1. Вычисляем количество делителей для начального числа 700 000
2. Создаём лист последовательности, с начальным числом 700 000
3. Ищем числа от 700 001 до 1 000 000 (т.к 700 000 мы уже добавили)
4. Вычисляем количество делителей для текущего числа
5. Если у текущего числа количество делителей больше, то:
1. Добавляем это число в последовательность
2. Обновляем текущие количество делителей, для следующего числа
6. Если длинна последовательности равна 5, то выводим её вместе с делителями каждого числа

Как можно подметить, таким образом, можно вычислить бесконечную последовательность чисел, где кол-во делителей следующего числа больше, но по заданию она ограничена длинной 5 (по-факту, она ограничено 1 000 000).

Ответ:

700000 72
700128 144
702000 160
702240 192
720720 240

Полный код:

def find_divisors(number):
    divisors_set = set()
    for divisor in range(1, int(number**0.5) + 1):
        if number % divisor == 0:
            divisors_set.add(divisor)
            divisors_set.add(number / divisor)
    return len(divisors_set)
    
last_divisors = find_divisors(700000)
numbers_list = [700000]

for number in range(700001, 1000000):
    current_divisors = find_divisors(number)
    if current_divisors > last_divisors:
        numbers_list.append(number)
        last_divisors = current_divisors
    if len(numbers_list) == 5:
        for num in numbers_list:
            print(num, find_divisors(num))
        break       

Редактор: andy