Программа, которая для каждого 1<=n<=100 находит наименьшее треугольное число, кратное n, сумма цифр которого также кратна n. Как её ускорить?

Рейтинг: 3Ответов: 3Опубликовано: 01.03.2023
# Программа, 
# которая для каждого 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 требуемых чисел.

python оптимизация арифметика числовые-последовательности
Источник: Stack Overflow на русском

Ответы

▲ 3
  1. оптимизация 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
  1. Оптимизация основного цикла: Если перебирать 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.

▲ 2

Таблица результатов. Здесь не все. В графе 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                       0.25s
 50           11827924
 51               3434
 52        12480937143                       0.73s
 53        18915547890                       1.05s
 54               5291
 55              17314
 56        42163918223                       2.39s
 57              12368
 58       278563098696                      15.6s
 59           44465467
 60              37335
 61       871434446172                      45.4s
 62      1094247592547                      58.0s
 63              31590
 64              62848
 65      3097998999030                   5m 19s
 66              28248
 67     10862742746652                   8m 38s
 68          616441216
 69             109434
 70     44045204049839               1h 15m 
 71     39989998747083                  30m 48s
 72             117728
 73             107674
 74    126466516492619               1h 36m
 75             126474
 76    316223338133031               4h  8m
 77         4469652109
 78             243671
 79                  -          ~2d 15h
 80   4170347227749504              19h 38m
 81             311768
 82             362932
 83                  -          ~3d
 84             444296
 85                  -          ~5d
 86       126488560747
 87             720968
 88                  -        ~133d
 89                  -         ~29d
 90            2782044
 91            1548547
 92                  -        ~111d
 93            2365827
 94                  -        ~146d
 95      1837382921434
 96            3364223
 97                  -     ~18y
 98                  -      ~3y
 99            4168692
100           18920824
▲ 0

Например, 10-е треугольное число (55, шаг 10), следующее треугольное число получается прибавлением 11 к предыдущему числу (55+11 = 66),следующее, прибавлением 12 к числу 66 и так далее,то есть каждое следующее треугольное число равно предыдущему,увеличенному на шаг предыдущего, плюс единица.