Partitions Calculator:

Partitions

public static String simpleQuickPartitions (int total) 
        {if (total<0)    // no partitions in such a useless case
            {return "0";
            }          
         int dePent = (int) Math.sqrt(1.0d+total);
         int signArray[] = new int[2*dePent+2];
         int pentArray[] = new int[2*dePent+2];
         signArray[0]=-1; signArray[1]=1;
         pentArray[0]=0; pentArray[1]=1;
         for (int i=1; i<=dePent; i++)
            {signArray[2*i]=-signArray[2*i-2];
             signArray[2*i+1]=-signArray[2*i-1];
             pentArray[2*i]=(i*(3*i+1))/2;
             pentArray[2*i+1]=((i+1)*(3*i+2))/2;
            }  
         BigInteger partitionArray[] = new BigInteger[total+1];            
         partitionArray[0]=BigInteger.valueOf(1l);
         for (int j=1; j<=total; j++)
            {BigInteger partSum=BigInteger.valueOf(0l);
             for (int k=1; pentArray[k]<=j; k++)                 
                {if (signArray[k]==1)
                    {partSum = partSum.add(partitionArray[j-pentArray[k]]);
                    }
                 else
                    {partSum = partSum.subtract(partitionArray[j-pentArray[k]]);
                    }
                }
 
             partitionArray[j] = partSum;
            }        // end of j loop
         return partitionArray[total].toString();
        }

Yes! I have finally gotten my partitions calculator online. Without a doubt, this is the fastest partitions calculator you will ever see in your life. Calculating partitions up to 1000 (this will increase, but honestly who needs partitions of that big numbers?) Java code above. Very fast in its own right, but the speed is due to a programming technique called "pre-calculation" which is very often used in programming contests due to the time constraint. Basically, viewing my "source code" above you will see a humungous declared array of partitions of all numbers up to 1000 for now. Now, the program just needs to see what value is stored for your input, and returns it very quickly. Pretty nifty, as waiting for long partitions doesn't seem that fun. Anyways, for those that don't know, partitions of a number (integer) are the number of ways you can split it up into the sum of different numbers. 5 has 7 partitions: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1. Pretty cool, right? Its actually fairly hard to calculate and the numbers get big quickly (try it!) and the time it takes to compute grows exponentially (not with mine though!). For interest, here is the list of partitions up to 1000. See if you can find a pattern/cool things about the list. Note that I will expand the calculator to find even greater numbers soon.