/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
/*
* partition.c
* Copyright (C) DMGualtieri 2011
*
* 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 .
*/
// 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
#include
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);
}