Преобразование условного суммирования в решение закрытой формы

Question

Часто суммирование можно преобразовать в замкнутое решение формы.

Например

for (int i=0;i<n;i++) 
    result += i; 

эквивалентно result += max(0, n * (n - 1)/2)

for (int i=0;i<n;i++) 
    for (int j=0;j<m;j++) 
    result += i; 

эквивалентно result += max(0, m * n * (n - 1)/2)

for (int i=0;i<n;i++) 
    for (int j=0;j<m;j++) 
    if (i < j) 
     result += i; 

эквивалентно

for (int i=0;i<n;i++) 
    for (int j=i+1;j<m;j++) 
    result += i; 

и, таким образом, эквивалентна

for (int i=0;i<n;i++) 
    if (i+1 < m) 
    result += i * (m-i); 

и, таким образом, эквивалентна

for (int i=0;i<min(n,m-1);i++) 
    result += m * i - i * i; 

и, таким образом, наконец, что эквивалентно result += max(0, m * min(n,m-1) * (min(n,m-1) - 1)/2 - (min(n,m-1) - 1) * ((min(n,m-1) - 1) + 1) * (2 * (min(n,m-1) - 1) + 1)/6) или, возможно, легче записать как result += max(0, m <= n ? m * (m-1) * ((m-1) - 1)/2 - ((m-1) - 1) * (((m-1) - 1) + 1) * (2 * ((m-1) - 1) + 1)/6) : m * n * (n - 1)/2 - (n - 1) * ((n - 1) + 1) * (2 * (n - 1) + 1)/6)

Когда такое преобразование к закрытым возможно ли решение формы?

Кажется, что допускаются только условия, сложение и умножение (т. Е. Полиномы), всегда можно начинать с самого внутреннего цикла, отслеживать диапазон разрешенных min/max и добавленный многочлен.

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

Есть ли инструмент для автоматического создания решения закрытой формы из итеративной версии?

Насколько тяжелее это становится, когда разрешено разделение?

for (int i=2;i<n;i++) 
    if (i % 2 == 0) 
    result += 1; 

довольно легко, как for (int i=2;i<n;i+=2) result += 1; и эквивалентно max(0, (n/2) * (n/2 + 1))

С другой стороны

for (int i=2;i<n;i++) 
    if (n % i == 0) 
    result += 1; 

, кажется, очень трудно преобразовать.

Answer 1

Несмотря на то, что для многих сумм существуют выражения замкнутых форм, есть также много других, для которых никто не смог найти их, как гармонические числа (обратите внимание, что количество таких сумм зависит от того, какие функции вы разрешаете в закрытая форма).

Кажется, если только условия, сложение и умножение (то есть полиномы) разрешено, то всегда можно начать на внутренней петле большей, отслеживать диапазон допустимых мин/макс и добавленного полинома.

Вы почти правы, если условие затрагивает только параметры суммирования (первого или последнего члена, или, возможно, размер шага, как if (i % 2 == 0)), то всегда существует замкнутая форма, которая может быть выражена как рациональное функция.Эти, среди других выражений, могут быть вычислены с использованием, например, finite calculus.

Для более широкого спектра выражений вы можете использовать generating functions (см. Раздел 17.2.2 для очень мягкого введения). Они могут в значительной степени использоваться для вычисления замкнутых форм для некоторых выражений (либо сумм, либо рекуррентных отношений).

Насколько тяжелее это становится, когда разрешено разделение?

Как я уже сказал, if (i % 2 == 0) довольно легко, так как все это делает увеличить шаг суммы, например

for (int i = 0; i <= n; i++) 
    if (i % 2 == 0) 
    result += i; 

фактически становится

for (int i = 0; i <= n/2; i++) 
    result += 2*i; 

, который хорошо вписывается в закрытая форма для n. Другие условия, например if (n % i == 0), предоставленные вами, будут намного сложнее. Например, рассмотрим очень похожее выражение, которое вычисляет сумму делителей

for (int i = 1; i < n; i++) 
    if (n % i == 0) 
    result += i; 

Если разрешено для закрытой формы выражения, то это может быть легко использован фактор чисел с двух простых делителей, которые, как правило, предполагается, что жесткий.