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

/*
This program computes A237668  A237667 forn n=0,..,100
Tested under linux and gcc, compiled  with -std=gnu99 

ric(k,k) generates recursively all partitions of k
and stores each partition in part[] and calls dec().

dec() checks if the current partition contains one
term which is the sum of two or more other terms.
 */

int part[100]; // a partition
int npart;     // number of parts in the current partition
int sum[100]; // sum[j] = sum of parts from part[j] to part[npart-1]
int totp;     // total number of partitions 
int ndec;     // number of decomposable partitions


// recursively check if value tot can be decomposed using
// current terms in part[from]...part[npart-1]
// na counts the number of addends in the current decomposition

int dek(int tot, int from, int na)
{
  // if tot=0 I've finished, the current decomposition is 
  // good if the number of addends is greater than 1
  if (tot==0) return (na>1);
  // if I've used all possible terms in part or if
  // all the still to be used terms are not enough, this is a dead end
  if (from==npart || tot>sum[from]) return 0;
  // otherwise, I try two decompositions, one with part[from]
  if (tot>=part[from] && dek(tot-part[from],from+1,na+1)) return 1;
  // and one without it
  if (dek(tot,from+1,na)) return 1;
  // nothing found
  return 0;
}

void dec()
{
  // I compute the partial sums of parts.
  // This helps when trying to decompose
  // one part as sum of others
  sum[npart-1]=part[npart-1];
  for (int j=npart-2; j>=0; j--) sum[j]=sum[j+1]+part[j];

  // for each part, I try to decompose it as a sum
  // of smaller parts. In case of success i 
  for (int j=0; j<npart-2; j++)
    {
      if (dek(part[j],j+1,0)) 
         {ndec++; return;}
    }
}

// this function generates partitions of parts in non-increasing
// size.
// r is the residue still to be partitioned
// lap is the size of last part
void ric(int r, int lap)
{
  // if r=0 I've completed a partition, so I
  // increase totp and call dec() to check decomposability
  if (r==0) {totp++; dec();}
  // otherwise I add other parts of size not greater than lap
  else
    {
      if (lap > r) lap=r;
      for (int p=1; p<=lap; p++)
	{
	  part[npart++]=p;
	  ric(r-p,p);
	  npart--;
	}
    }
}

int main(int argc, char *argv[])
{
  printf(" n     P(n)     A237668 A237667\n");
  printf("-------------------------------\n");
  printf("  0         1         0       1\n");
  //  printf("100 190569292 190400661  168631\n");
  for (int n=1; n<=100; n++)
    {
      totp=0; ndec=0;
      ric(n,n);
      printf("%3d %9d %9d  %6d\n",n,totp,ndec,totp-ndec);
    }
  printf("-------------------------------\n");
  return 0;
}