/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
/*
 * partition.c
 * Copyright (C) DMGualtieri 2011 <gualtieri**AT**ieee.org>
 * 
 * Euler_Partition is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * Euler_Partition is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along
 * with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
 // Finds the total number of partitions of numbers up to 121
 // This is the limit of a long integer in C
 // Runs quite fast
 // You can use a large number library, such as the
 // GNU Multiple Precision Arithmetic Library to go farther
 // Reference: http://www.math.temple.edu/~melkamu/html/partition.pdf
 // (The reference includes a Basic program that's translated into C here)

#include <stdio.h>
#include <stdlib.h>

long int p[400];
int n, s, k, f;
FILE *outdata;

int main()
{

//Open output datafile
if ((outdata = fopen("partition_data.txt","w"))==NULL)
	{printf ("\nOutput file cannot be opened.\n");
	exit (1);}
else
{
printf("Output file = partition_data.txt\n");
}

p[0] = 1;

// Main loop, for each n find P[n]
// Limit of n=121 is because of long integer precision
for(n=1; n<122;n++)
{
s = 1;
p[n] = 0;

for(k=1;k<101;k++)
// Loop should always break before k limit. The value of k never goes above 9
// in this implementation.  If you use a large number library
// to extend the program, some test of k might be needed to detect an error
{
//Calculate two terms in recursion relation for p[N]
f = k * (3 * k - 1) / 2;
// Exit loop if argument is negative
if(n - f < 0) break;
p[n] = p[n] + s * p[n - f];
f = k * (3 * k + 1) / 2;
// Exit loop if argument negative
if(n - f < 0) break;
p[n] = p[n] + s * p[n - f];
s = -s;
}

//Print results
printf("%d\t%ld\n", n, p[n]);
fprintf(outdata, "%d\t%ld\n", n, p[n]);

}

//Close output file
fclose(outdata);

	return (0);
}