Pagina's

2016/02/10

Partition numbers


/*
                        ms    i7@3G6Hz
    P[0]...P[10000]    100  
    P[0]...P[20000]    305  
    P[0]...P[40000]    970   
    P[0]...P[80000]   3420  
    p[0]..P[160000]  13800 
    P[0]..P[320000]  53000    P[320000] 624 digits
*/
using System;                                                                         
using System.Diagnostics;
using Xint = System.Numerics.BigInteger;
class Program
{
    static Stopwatch sw = new Stopwatch();
    static void Main()
    {
        uint n = 10000;
        sw.Start();
        Xint[] P = A000041(n);
        sw.Stop();
        Console.Write(sw.Elapsed + "\n" + P[n]);
        Console.Read();
    }

    static Xint[] A000041(uint n)
    {
        int i, d, d0, d1; Xint S; Xint[] P;
        P = new Xint[n + 1]; P[0] = 1;
        for (i = 1; i <= n; i++)
        {
            S = d = d1 = 0; d0 = -2;
            do
            {
                d += d0 += 4; if (i >= d) S += P[i - d];
                d -= d1 += 1; if (i >= d) S += P[i - d];
                if (i <= d) break;
                d += d0 += 4; if (i >= d) S -= P[i - d];
                d -= d1 += 1; if (i >= d) S -= P[i - d];
            }
            while (i > d);
            P[i] = S;
        }
        return P;
    }
}