Brute force calculation of P(200)

[Annoying Twit]

In the film "The Man Who Knew Infinity" about S. Ramanujan, Major MacMahon calculated the number of partitions of 200, so that the accuracy of Ramanujan & Hardy's estimate could be established.

How would MacMahon have calculated this? I looked into how this number would be calculated by brute force, but my method requires 80,102 calculations to be performed. Which I would think would take one heck of a long time, even with the mental arithmetic skills MacMahon demonstrated.

Is there a more clever way of calculating this number that MacMahon would have used? Otherwise, how long would he have taken to calculate it?

Here's my program, which shows the method I used. I'm not good at describing things in mathematical notation.

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

#define MAX_N 500
#define NO_ANSWER -1

long working[MAX_N+1][MAX_N+1];
long solve( int target, int max );

int numCalcs = 0;

int main( int argc, char *argv[] )
{
  int target;
  long answer;
  int i,j;

  if ( argc < 2 )
  {
    fprintf( stderr, "usage partition N\n" );
    exit( -1 );
  }

  target = atoi( argv[1] );

  if ( target < 1 || target > MAX_N )
  {
    fprintf( stderr, "Can only do numbers 1 .. %d\n", MAX_N );
    exit( -1 );
  }

  // Working will be used to store answers.
  // working[target][max] where target is the number we want to add to,
  // and max is the maximum number we can use to add to it.

  for ( i = 0; i <= target; i++ )
  {
    for ( j = 0; j <= target; j++ )
    {
      working[i][j] = NO_ANSWER;
    }
  }

  // No matter what number we're looking for, if we can only use ones, then
  // there is only one partition.

  for ( i = 1; i <= MAX_N; i++ )
  {
    working[i][1] = 1;
  }

  answer = solve( target, target );

  printf( "The answer is %li number of calculations is %d\n", answer, numCalcs );
}

long solve( int target, int max )
{
  int reps;
  int remainder;

  // If we've calculated this answer before, just return it.

  if ( working[target][max] != NO_ANSWER ) return working[target][max];

  // Not found before, calculate it.

  working[target][max] = 0;

  // For every feasible number of uses of the maximum value

  for ( reps = 0; reps * max <= target; reps++ )
  {
    remainder = target - reps * max;

    numCalcs++;

    if ( remainder == 0 ) // exact fit
    {
      working[target][max]++;
    }
    else if ( max > 1 ) // recurse to solve sub-problem of remainder
    {
      working[target][max] += solve( remainder, max-1 );
    }
  }

  // NOW we've calculated it.

  return working[target][max];
}

I did find a better way of doing this. If p( k, n ) means "the number of partitions of n which include a number of at least k", then we have the equality

p( k, n ) = p( k + 1, n ) + p( k, n - k )

The boundary conditions are: p( k, n ) = 0 if k > n, and p( k, n ) = 1 if k = n. Also note that p(n) = p( 1, n ).

That leads to this program:

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

#define MAX_N 500
#define NO_ANSWER -1

long working[MAX_N+1][MAX_N+1];
long p( int k, int n );

int numCalc = 0;

int main( int argc, char *argv[] )
{
  int i, j;
  int target;
  long answer;

  target = atoi( argv[1] );

  for ( i = 0; i <= MAX_N; i++ )
  {
    for ( j = 0; j <= MAX_N; j++ )
    {
      working[i][j] = NO_ANSWER;
    }
  }

  answer = p( 1, target );

  printf( "P(%d) is %li number of calculations %d\n", target, answer, numCalc );
}

long p( int k, int n )
{
  if ( k > n ) return 0;
  if ( k == n ) return 1;

  if ( working[k][n] != NO_ANSWER ) return working[k][n];

  numCalc++;

  working[k][n] = p( k + 1, n ) + p( k, n - k );

  return working[k][n];
}

And the number of calculations that actually needs to be performed now reduces to 19,900. They are also much simpler, simple additions of two known values of p( k, n ). The limitation here is only that even using the long data type in C, the program rapidly runs out of digits when problems larger than p( 460 ) are attempted.

Previously I gave my source for this method. But, my posting then disappeared to be moderated, and when it returned the url to my source had disappeared. I'm not sure why, but won't give it here in case my post disappears again.

 

[e2theipi2026]

In that movie they say he calculated it painstakingly by hand. Could be a different movie I'm thinking of, but that is what was stated.

 

[Annoying Twit]

Thanks. I guess he did the nearly 20,000 additions then. I can't imagine doing that without making an error.