Условие задачи
Последовательность треугольных чисел образуется путем сложения натуральных чисел. К примеру, 7-ое треугольное число будет 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Первые десять треугольных чисел:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Перечислим делители первых семи треугольных чисел:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
Как мы видим, 28 - первое треугольное число, у которого более пяти делителей.
Каково первое треугольное число, у которого более пятисот делителей?
Решение
Задача состоит из 2-х этапов:
- Этап 1. Собственно генерация числа
- Этап 2. Поиск делителей или на математическом языке "факторизация числа.
С этапом 1 особых проблем не возникло. Достаточно применить следующую конструкцию:
num=sum([c for c in range(1,x+1)])
То есть генерируем список чисел и суммируем данный список.В цикле увеличиваем x.
А вот с факторизацией проблемы. Для нашего объема задачи 500 делителей неподъемная величина если тупо перебирать делители. В математике я не силен, но мне попался ресурс где подробно описан оптимальный алгоритм факторизации:
1. Первоначальное количество делителей = 2 (чтобы не перебирать 1 и само число)
2. Делители рассматриваем в промежутке от 2 до квадратного корня числа.
3. При нахождении делителя увеличиваем их количество на 2 (т.к делители всегда ходят парами)
4. Если число представляет собой точный квадрат (имеет целый корень) уменьшаем результирующее количество делителей на 1.
Для начала реализуем функцию определения точного квадрата.
Проблема в том, что результат корня числа в Python всегда float и определить целый ли корень задача усложнена. Я решил эту проблему в лоб - если округленный корень числа в квадрате = изначальному числу число точный квадрат
import math
def is_perf_sq(n):
x=math.ceil((math.sqrt(n)))
if x*x==n:
return True
else:
return False
Далее функция, возвращающая первое треугольное число
def max_triangular(m):
x=3
n=2
while n<=m:
n=2
num=sum([c for c in range(1,x+1)])
for i in range(2,math.ceil(math.sqrt(num))):
if num%i==0:
n+=2
if is_perf_sq(num):
n-=1
x+=1
return num
print(max_triangular(500))
Если тупой перебор делителей не завершался и за час, то эта конструкция возвращает результат за 20 секунд.