Paraffins: Difference between revisions

</pre>This may be the fastest algorithm ever known, with complexity O(n^2). Computing for 1-1000 takes less than 1 second.<syntaxhighlight lang="c++">

#include <gmpxx.h>

#include <iostream>

using namespace std;

vector<mpz_class> A = {1}, b, a;

int main()

{

for (int m = 0; m < 1000; m++)

{

mpz_class tmp = 0;

for (int i = 0; i <= m / 2; i++)

if (i * 2 != m)

tmp += A[i] * A[m - i];

b.push_back(tmp);

tmp = 0;

for (int i = 0; i <= m; i++)

tmp += A[i] * b[m - i];

for (int i = 0; i <= m / 2; i++)

if (3 * i != m)

tmp -= A[i] * A[i] * A[m - 2 * i];

tmp /= 3;

a.push_back(tmp);

for (int i = 0; i <= m / 2; i++)

if (3 * i != m)

tmp += A[i] * (A[i] + 1) / 2 * A[m - 2 * i];

if (m % 3 == 0)

tmp += A[m / 3] * (A[m / 3] + 1) * (A[m / 3] + 2) / 6;

A.push_back(tmp);

}

for (int n = 0; n <= 1000; n++)

{

mpz_class B = 0;

for (int i = 1; i <= n / 2; i++)

if (i * 2 != n)

B += A[i] * A[n - i];

if (n % 2 == 0)

B += A[n / 2] * (A[n / 2] + 1) / 2;

int m = n - 1;

mpz_class C = 0;

for (int i = 0; i <= m; i++)

C += A[i] * a[m - i];

for (int i = 0; i <= m / 2; i++)

C -= A[i] * A[i] * b[m - 2 * i];

for (int i = 0; i <= m / 3; i++)

if (4 * i != m)

C += A[i] * A[i] * A[i] * A[m - 3 * i];

C /= 4;

for (int i = 0; i <= m / 2; i++)

C += A[i] * (A[i] + 1) / 2 * b[m - 2 * i];

for (int i = 0; i <= m / 3; i++)

if (4 * i != m)

C -= A[i] * (A[i] + 1) / 2 * A[i] * A[m - 3 * i];

if (m % 2 == 0)

for (int i = 0; i <= m / 4; i++)

if (4 * i != m)

C += A[i] * (A[i] + 1) / 2 * A[m / 2 - i] * (A[m / 2 - i] + 1) / 2;

for (int i = 0; i <= m / 3; i++)

if (4 * i != m)

C += A[i] * (A[i] + 1) * (A[i] + 2) / 6 * A[m - 3 * i];

if (m % 4 == 0)

C += A[m / 4] * (A[m / 4] + 1) * (A[m / 4] + 2) * (A[m / 4] + 3) / 24;

if (n % 2)

cout << C - B << endl;

else

cout << C - B + A[n / 2] << endl;

}

}

</syntaxhighlight>