Программа, которая для каждого 1<=n<=100 находит наименьшее треугольное число, кратное n, сумма цифр которого также кратна n. Как её ускорить?
# Программа,
# которая для каждого 1<=n<=100
# находит наименьшее треугольное число,
# кратное n, сумма цифр которого также n.
def triangle_number(n):
return n * (n + 1) // 2
def digit_sum(n):
return sum(map(int, str(n)))
for n in range(1, 101):
k = 1
while True:
tn = triangle_number(k)
if tn % n == 0 and digit_sum(tn) % n == 0 and digit_sum(tn) != 0:
print(f"n = {n}, k = {k}, tn = {tn}")
break
k += 1
Данная программа работает чересчур медленно, поэтому успевает вывести только первые 39 нужных чисел из ста. Получается последовательность: 1, 6, 3, 1128, 55, 6, 1596, 15576, 36, 190, 163878, 1128, 378885 тощо.
Пожалуйста, помогите оптимизировать код таким образом, чтобы выводились все 100 требуемых чисел.
Ответы (3 шт):
- оптимизация digit_sum :
digit_sum_divider = int(10**5) # подобрать оптимальное 10**5 ... 10**3, в зависимоти от размера кеша конкретного процессора
digit_sum_precalc = [ sum(map(int, str(n))) for n in range(digit_sum_divider) ]
def digit_sum(n):
ret =0
while True:
ret += digit_sum_precalc[ n%digit_sum_divider ]
n = n//(digit_sum_divider)
if n==0:
return ret
- Оптимизация основного цикла:
Если перебирать
k+=1, то будет много "пустых" циклов: в среднем, для каждого n-го будет выполнено условиеtriangle_number(k)%n==0. Полезно заранее рассчитеть размер шага по k.
Путь для k условие выполнено triangle_number(k)%n==0, найдем минимальное s для которого triangle_number(k+s)%n==0
Посчитаем:
triangle_number(k+s) % n ==0
(k+s)*(k+s+1)//2 %n ==0
(k+s)*(k+s+1) % (n*2) ==0
( k*(k+1) + s*(2*k+1 + s) ) % (n*2) ==0
( k*(k+1) % (n*2) + s*(2*k+1 + s) % (n*2) ) % (n*2) ==0 # транзитивность взятия остатка
( s*(2*k+1 + s) % (n*2) ) % (n*2) ==0 # k*(k+1) % (n*2) ==0 - поскольку для k выполнено условие triangle_number(k)%n==0
( (s%(n*2)) *( (2*k+1) % (n*2) + s % (n*2) ) ) % (n*2) ==0
Видим, что k входит в уравнение для шага по k, только в составе выражения (2*k+1) % (n*2), но это выражение пробегает ограниченное число значений, а значит, можно меморизовать величину шага как функцию (2*k+1) % (n*2).
Получим:
def add_for_k( a , nn ):
for s in range(1, nn+1 ):
if s*(s+a) % nn ==0 :
return s
def main():
for n in range(1, 45):
adds_k = [ add_for_k(i, 2*n) for i in range( n*2) ]
k = adds_k[1]
while True:
if digit_sum( (k*(k+1))//2) % n == 0:
break
k += adds_k[ (2*k+1) % (n*2) ]
print(f"n = {n}, k = {k}, tn = {triangle_number(k)}")
Что приведет к росту производительности, примерно в 10 раз, что, впрочем, все равно недостаточно, поскольку размер искомого k экспоненциально растет с ростом n.
Например, 10-е треугольное число (55, шаг 10), следующее треугольное число получается прибавлением 11 к предыдущему числу (55+11 = 66),следующее, прибавлением 12 к числу 66 и так далее,то есть каждое следующее треугольное число равно предыдущему,увеличенному на шаг предыдущего, плюс единица.
Таблица результатов. Здесь не все. В графе time написаны затраты времени на расчет. Знак ~ означает что это оценка времени, основанная на экстраполяции.
Пока считается грубой силой с парой оптимизаций из ответа Chorkov. Программа на C, работает на одном ядре процессора. Алгоритм допускает параллельную и распределённую работу. Кажется его можно перенести на GPU, что обещает сократить время до года по календарю. Пока не уверен что буду этим заниматься.
Есть некоторые наблюдения о том как ведёт себя функция. Ничего доказанного. Никаких идей по радикальному ускорению.
n k время 1 1 2 3 3 2 4 47 5 10 6 3 7 56 8 176 9 8 10 19 11 572 12 47 13 870 14 223 15 30 16 4223 17 3434 18 27 19 76 20 37335 21 56 22 28248 23 3151 24 176 25 126474 26 243671 27 107 28 223 29 720968 30 879 31 2365827 32 35776 33 572 34 6306932 35 8943690 36 368 37 1147 38 39441092 39 870 40 331300464 41 362932 42 1092 43 345452109 44 733484696 45 1890 46 3151 47 1239184328 48 4223 49 4214256612 1.9s 50 11827924 51 3434 52 12480937143 5.8s 53 18915547890 8.3s 54 5291 55 17314 56 42163918223 19s 57 12368 58 278563098696 2m 15s 59 44465467 60 37335 61 871434446172 6m 23s 62 1094247592547 8m 29s 63 31590 64 62848 65 3097998999030 20m 66 28248 67 10862742746652 ~1h 20m 68 616441216 69 109434 70 44045204049839 ~16h 71 39989998747083 ~8h 72 117728 73 107674 74 126466516492619 13h 75 126474 76 - ~3d 77 4469652109 78 243671 79 - ~23d 80 - ~19d 81 311768 82 362932 83 - 84 444296 85 - ~1y 86 126488560747 87 720968 88 - ~4y 89 - ~3y 90 2782044 91 1548547 92 - 93 2365827 94 - ~21y 95 1837382921434 96 3364223 97 - ~300y 98 - ~180y 99 4168692 100 18920824