Brute force calculation of P(200)

In summary, Major MacMahon calculated the number of partitions of 200 in the film "The Man Who Knew Infinity" by using a method that required 80,102 calculations. However, a more clever method was later discovered, reducing the number of calculations to 19,900. MacMahon's method involved adding known values of p(k,n) and had limitations when dealing with larger problems.
  • #1
Annoying Twit
1
0
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.

Code:
#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:

Code:
#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.
 
Last edited:
Mathematics news on Phys.org
  • #2
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.
 
  • #3
Thanks. I guess he did the nearly 20,000 additions then. I can't imagine doing that without making an error.
 

Related to Brute force calculation of P(200)

What is meant by "Brute force calculation of P(200)"?

The term "brute force" refers to a method of solving a problem by systematically trying every possible solution until the correct one is found. In this case, "P(200)" likely refers to a mathematical function or formula that needs to be calculated for the input value of 200.

Why would someone use brute force to calculate P(200)?

In some cases, it may be the only feasible method for finding a solution. Brute force calculations can be time-consuming and resource-intensive, but they can also be more accurate than other methods.

How long would it take to perform a brute force calculation of P(200)?

The time it takes to perform a brute force calculation of P(200) would depend on the complexity of the function and the computing power available. It could take anywhere from milliseconds to hours or even days.

Are there any drawbacks to using brute force for this calculation?

One major drawback of brute force calculations is that they can be very computationally expensive, especially for large or complex functions. This can make them impractical for certain applications.

Are there any alternatives to brute force for calculating P(200)?

Yes, there are often alternative methods for solving mathematical problems, such as using algorithms or mathematical formulas. These methods may be more efficient or accurate than brute force, but they may also have limitations depending on the specific problem.

Similar threads

  • Programming and Computer Science
Replies
3
Views
1K
Replies
6
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
8
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
  • Advanced Physics Homework Help
Replies
2
Views
1K
Replies
3
Views
840
Replies
13
Views
2K
Replies
3
Views
3K
  • Programming and Computer Science
Replies
1
Views
902
Back
Top