条件付き総和を閉形式解に変換する

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; 

と等価であること

01と同等です

したがって

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)

として書き込ますることと等価と等価フォームソリューションは可能ですか？

条件、加算および乗算（すなわち多項式）のみが許される場合、常に最も内側のループから開始し、許容される最小/最大の範囲および追加された多項式を追跡することが可能であるようである。

ただし、手動でこの変換を行うと、範囲がすべてのループで分割されて指数関数的に増加するため、エラーが発生しやすく時間がかかります。

反復バージョンからクローズフォームソリューションを自動的に生成するツールはありますか？

分割が許可されると、どれくらい難しくなりますか？

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

は

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

一方むしろfor (int i=2;i<n;i+=2) result += 1;ように簡単かつmax(0, (n/2) * (n/2 + 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; 

除数の和を計算し、非常に類似した発現を検討し、これは容易に一般的であると考え2個の素因数を持つ数を因数分解するために使用することができますハード。