/******************************************************************************
 *                                                                            *
 * AUTHOR: Tim Morrow                                                         *
 * DATE  : March, 2004                                                        *
 * USAGE : cunningham.exe                                                     *
 *                                                                            *
 ******************************************************************************
 *                                                                            *
 * DISCLAIMER                                                                 *
 *                                                                            *
 * I can't vouch for the accuracy of this program or its fitness for purpose. *
 * Any errors are accidental. In any event use this program at your own risk. *
 *                                                                            *
 * Please credit me if you use any parts of this program, especially if you   *
 * manage to use it to prove or demonstrate something important such as       *
 * Riemann's or Goldbach's Conjectures ;-)                                    *
 *                                                                            *
 * BACKGROUND                                                                 *
 *                                                                            *
 * The Cunningham Project at http://www.cerias.purdue.edu/homes/ssw/cun/      *
 * have a long running project to factor numbers of the form b^n +- 1 for     *
 * b = 2, 3, 5, 6, 7, 10, 11, 12, up to high powers n. The site provides the  *
 * up to date factor tables made up of 3 files:                               *
 *                                                                            *
 * 1. pmain*.txt, the main table of factors with large primes and composite   *
 *    cofactors aliased as Pn and Cn where n denotes the length of the        *
 *    decimal expansion of the number.                                        *
 * 2. appa*.txt, table of Pn with fully expanded decimal expansion.           *
 * 3. appc*.txt, table of Cn with fully expanded decimal expansion.           *
 *    * is a short date - currently it is 104 denoting January, 2004          *
 *                                                                            *
 * The site also has 'wanted lists' for which composite cofactors they want   *
 * broken asap, the page of latest developments containing factors not yet    *
 * added to the above 3 text files and even a slow factor calculator for      *
 * factoring a single Cunningham number at a time. They also include a link   *
 * to http://www.ams.org/online_bks/conm22 where you can download a PDF copy  *
 * of "Factorizations of b^n+-1, b=2,3,5,6,7,10,11,12 Up to High Powers" for  *
 * free.                                                                      *
 *                                                                            *
 * This book is an excellent resource with detailed explanation on how to     *
 * read the tables and use them to manually generate other factors not        *
 * explicitly tabled - for instance Aurifeuillian factorisation.              *
 *                                                                            *
 * There is also a discussion of the development and history of factoring     *
 * techniques and primality tests from the start of the project in 1925 right *
 * up to the current day. Primality proof summaries are given and a list of   *
 * 348 references to key papers in the area of factorisation/primality.       *
 *                                                                            *
 * MOTIVATION                                                                 *
 *                                                                            *
 * To facilitate my understanding Cunningham numbers and their factorisation  *
 * I decided to write a program that would read in all the table data and     *
 * generate all the factors for each base b and exponent n.                   *
 *                                                                            *
 * In their original state, the tables are not exactly computer friendly so I *
 * decided that some preprocessing of the data to a more rigid record based   *
 * format more was in order prior to loading into my program.                 *
 *                                                                            *
 * Just for fun the program should generate both the standard text based      *
 * output plus a more interesting HTML format with some hyperlinking and      *
 * colour coding to move between the factors and spot primes and composite    *
 * cofactors.                                                                 *
 *                                                                            *
 * PROGRAM DESCRIPTION                                                        *
 *                                                                            *
 * This program reads preprocessed Cunningham Database files of factored      *
 * Cunningham numbers and produces a both a text file and HTML file of        *
 * complete factorisations - all factors are produced in all their glory :-)  *
 *                                                                            *
 * The data/process flow is as follows (replace MMYY to the short date)       *
 *                                                                            *
 * 1. Preprocess pmainMMYY.txt using the command line                         *
 *      awk -f pmain.awk pmainMMYY.txt > pmain.in                             *
 * 2. Preprocess appaMMYY.txt using the command line                          *
 *      awk -f appa.awk appaMMYY.txt > appa.in                                *
 * 3. Preprocess appcMMYY.txt using the command line                          *
 *      awk -f appc.awk appcMMYY.txt > appc.in                                *
 * 4. Modify html_header.txt to suit (the HTML wrapper)                       *
 * 5. Compile, link and run this C program                                    *
 * 6. Have look at the 16 text file and 16 HTML file outputs. Enjoy!          *
 *                                                                            *
 * ERROR RETURNS                                                              *
 *                                                                            *
 *  1 Unable to malloc the memory for exponent node                           *
 *  2 Unable to malloc the memory for factor node                             *
 *  3 Unable to malloc the memory for the factor                              *
 *  4 Attempted to add a nonexistent exponent node                            *
 *  5 Attempted to add a nonexistent factor node                              *
 *  6 Can't open file (Main Cunningham Table) (FILE_IN_1)                     *
 *  7 Unexpected table (Unknown Cunningham Table)                             *
 *  8 Can't open file (Appendix A or Appendix C file) (FILE_IN_2, FILE_IN_3)  *
 *  9 Can't determine table (when reading Appendix A or C)                    *
 * 10 Factor name does not match what's found in lookup                       *
 * 11 Unable to malloc the memory for the appendix factor                     *
 * 12 Cannot open input file (FILE_IN_4)                                      *
 * 13 Cannot open input file (FILE_IN_5)                                      *
 * 14 Invalid output table index [0,NUM_OUTPUT_TABLES)                        *
 * 15 Cannot open output file (one of the 16 output text files)               *
 * 16 Cannot open output file (one of the 16 output HTML files)               *
 *                                                                            *
 ******************************************************************************/
#include <windows.h>
#include <stdio.h>
#include <math.h>


// Constants
#define FILE_IN_1            "pmain.in"         // Main Cunningham table
#define FILE_IN_2            "appa.in"          // Appendix A
#define FILE_IN_3            "appc.in"          // Appendix C
#define FILE_IN_4            "text_header.txt"  // Text header file
#define FILE_IN_5            "html_header.txt"  // HTML header file
#define LENGTH_FILE_NAME     32                 // Length of longest file name
#define LINE_LENGTH          100000             // Longest input line length
#define MAX_EXPONENTS        2500               // Maximum number of exponents
#define MAX_EXPONENT_DIGITS  8                  // Maximum length of an exponent
#define MAX_DIGIT_LENGTH     1000               // Maximum digit length
#define MAX_FACTORS          1000               // Maximum number of factors
#define MAX_ANSWER_LENGTH    100000             // Length of longest answer
#define MAX_HTML_TAG         256                // Length of largest HTML tag
#define NUM_TABLES           18                 // Number of Cunningham tables
#define NUM_OUTPUT_TABLES    16                 // Number of output tables
#define AUR                  3                  // Aurifeuillian index
#define OUTPUT_RECORD_LENGTH 120                // Maximum record length
#define OUTPUT_MARGIN        12                 // Spaces before factors
#define dots(t,n) ((t)!=2&&(t)%2==0&&(n)%2==0)  // Indicates b^n-1 with even n


// Exponent node definition suitable for a linked list
typedef struct ExponentNodeType {
  char exp[MAX_EXPONENT_DIGITS];  // The exponent as a small string
  struct ExponentNodeType *next;  // Pointer to next exponent node
} ExponentNode;


// Factor node definition suitable for a linked list
typedef struct FactorNodeType {
  char *factor;                 // The factor as dynamic string
  struct FactorNodeType *next;  // Pointer to the next factor
} FactorNode;


// The [AUR] arrays support case of aurifeuillian factors (Normal=0, L=1, M=2)
typedef struct CunninghamTableType {
  int type;                 // 1 normal, 2 line & 3 line aurifeuillian
  char *unfactored;         // Set to decimal expansion Cn composite cofactor
  ExponentNode *exp[AUR];   // Linked list of previous exponents in table
  FactorNode *factor[AUR];  // Linked list of factors at current level
} CunninghamTable;


// The work table tracks the table and index that each factor occurs in
typedef struct TableInfoType {
  char name[32];                     // Name of table Cx(y,n), x=+/-,y=base
  int max;                           // Maximum index in table
  char file_text[LENGTH_FILE_NAME];  // Name of text file to store text table
  char file_html[LENGTH_FILE_NAME];  // Name of text file to store HTML table
  char href_prefix[MAX_HTML_TAG];    // Prefix of title attribute in href tag
  char title[MAX_HTML_TAG];          // HTML title for the table
  char header[MAX_HTML_TAG];         // HTML header line for the table
} TableInfo;


// The work table tracks the table and index that each factor occurs in
typedef struct WorkTableType {
  int table;                      // Table index the factor occurs in
  int index;                      // Index the factor occurs at in the table
  char *unfactored;               // Set to unfactored factor
  char factor[MAX_DIGIT_LENGTH];  // Decimal expansion of the factor
} WorkTable;


// The summary store summary information
typedef struct SummaryType {
  char table_name[MAX_HTML_TAG];  // Table title
  int num_nofactors;              // Number of records with no known factors
  int num_somefactors;            // Number of records with some known factors
} Summary;


// Globals - the Cunningham table & work area for factoring current exponent
CunninghamTable lookup[NUM_TABLES][MAX_EXPONENTS];
short notprime[MAX_EXPONENTS];       // Prime array (0=prime,1=not prime)
TableInfo table[NUM_OUTPUT_TABLES];  // Table info array
Summary summary[NUM_OUTPUT_TABLES];  // Summary array to store results
WorkTable work[MAX_FACTORS];         // Work array to store factors, indexes
int w;                               // Index into working array
int prime_count;                     // How many b^n+-1 are prime in the table


// Create an exponent
ExponentNode *MakeExponent(
  char *item)  // Item to load into created exponent node
{
  ExponentNode *p;  // Pointer to malloc'ed exponent

  // Allocate memory for exponent
  if ((p=(ExponentNode *)malloc(sizeof(ExponentNode)))==NULL) {
    printf("Unable to malloc the memory for exponent node\n");
    exit(1);
  }

  // Populate the node
  strncpy(p->exp,item,MAX_EXPONENT_DIGITS);
  p->next=NULL;
  return(p);
} // MakeExponent


// Create a factor
FactorNode *MakeFactor(
  char *item)  // Item to load into created factor node
{
  FactorNode *p;  // Pointer to malloc'ed factor

  // Allocate memory for factor node
  if ((p=(FactorNode *)malloc(sizeof(FactorNode)))==NULL) {
    printf("Unable to malloc the memory for factor node\n");
    exit(2);
  }

  // Allocate memory for the factor string
  if ((p->factor=(char *)malloc(strlen(item)+1))==NULL) {
    printf("Unable to malloc the memory for the factor\n");
    exit(3);
  }

  // Populate the node
  strcpy(p->factor,item);
  p->next=NULL;
  return(p);
} // MakeFactor


// Free the memory for the exponent list by recursion
void FreeExponentList(
  ExponentNode *e)  // Exponent sublist to free
{ 
  if (!e)
    return;
  if (e->next)
    FreeExponentList(e->next);
  free(e);  // Free the exponent node
} // FreeExponentList


// Free the memory for the factor list by recursion
void FreeFactorList(
  FactorNode *p)  // Factor sublist to free
{ 
  if (!p)
    return;
  if (p->next)
    FreeFactorList(p->next);
  free(p->factor); // Free the dynamic factor string field first
  free(p);         // Free the factor node
} // FreeFactorList


// FreeCunninhamTable frees all dynamically allocated memory used by the table
void FreeCunninghamTable(
  void)  // No parameters
{
  int t,i,j;  // Loop counter for normal + aurifeuillian factors

  for (t=0; t<NUM_TABLES; t++) {
    for (i=0; i<MAX_EXPONENTS; i++) {
      for (j=0; j<AUR; j++) {
        FreeExponentList(lookup[t][i].exp[j]);
        FreeFactorList(lookup[t][i].factor[j]);
      }
    }
  }
} // FreeCunninghamTable


// InsertExponent adds a new node to the head of the current exponent list
ExponentNode *InsertExponent(
  ExponentNode *h,  // Head of the exponent list
  ExponentNode *n)  // New exponent node to insert
{
  if (n==NULL) {
    printf("Attempted to add a nonexistent exponent node\n");
    exit(4);
   }   
	else if (h==NULL)
    h=n;
	else {
		n->next=h;
		h=n;
	}
  return(h);
} // InsertExponent


// InsertFactor adds a new node to the head of the current factor list
FactorNode *InsertFactor(
  FactorNode *h,  // Head of the factor list
  FactorNode *n)  // New factor node to insert
{
  if (n==NULL) {
    printf("Attempted to add a nonexistent factor node\n");
    exit(5);
   }   
	else if (h==NULL)
    h=n;
	else {
		n->next=h;
		h=n;
	}
  return(h);
} // InsertFactor


// PrintCunninhamTable prints all fields in one element of the table
void PrintCunninghamTable(
  int t,  // Input table index - [0,NUM_TABLES)
  int i)  // Exponent whose exponents and factors are to be traversed
{
  ExponentNode *e;  // Loop pointer to traverse exponent nodes
  FactorNode *f;    // Loop pointer to traverse factor nodes
  int j;            // Loop counter for normal + aurifeuillian factors

  for (j=0; j<AUR; j++) {
    printf("  exponents:\n");
    for (e=lookup[t][i].exp[j]; e; e=e->next)
      printf("    %s\n", e->exp);
    printf("  factors:\n");
    for (f=lookup[t][i].factor[j]; f; f=f->next)
      printf("    %s\n", f->factor);
  }
} // PrintCunninghamTable


// Read the main Cunningham factor table into memory
void GetInputPmain(
  char *file)  // Main factor file to load
{
  FILE *in;                    // Input file handle
  char buf[LINE_LENGTH]="\0";  // Buffer to hold an input line
  int t=0,s,i1=0,i2,r;         // t,s=table index, i1=exponent, i2=index, r=type
  ExponentNode *e;             // Handle to current exponent
  FactorNode *f;               // Handle to current factor

  // Open the main Cunningham table
  if ((in=fopen(file,"r"))==NULL) {
    printf("Cannot open %s\n",file);
    exit(6);
  }
  
  // Read in the data
  fgets(buf,LINE_LENGTH-1,in);
  while (strstr(buf,"Table")) {

    // Determine the current table being read
    if (strstr(buf,"12+"))
      t=17;
    else if (strstr(buf,"12-"))
      t=16;
    else if (strstr(buf,"11+"))
      t=15;
    else if (strstr(buf,"11-"))
      t=14;
    else if (strstr(buf,"10+"))
      t=13;
    else if (strstr(buf,"10-"))
      t=12;
    else if (strstr(buf,"7+"))
      t=11;
    else if (strstr(buf,"7-"))
      t=10;
    else if (strstr(buf,"6+"))
      t=9;
    else if (strstr(buf,"6-"))
      t=8;
    else if (strstr(buf,"5+"))
      t=7;
    else if (strstr(buf,"5-"))
      t=6;
    else if (strstr(buf,"3+"))
      t=5;
    else if (strstr(buf,"3-"))
      t=4;
    else if (strstr(buf,"2+(4k)"))
      t=3;
    else if (strstr(buf,"2LM"))
      t=2;
    else if (strstr(buf,"2+(odd)"))
      t=1;
    else if (strstr(buf,"2-"))
      t=0;
    else {
      printf("Unexpected table: %s",buf);
      exit(7);
    }
 
    // Keep reading until next table or EOF is reached
    while (fgets(buf,LINE_LENGTH-1,in) && strstr(buf,"Table")==NULL) {

      // Read the next record
      i1=atoi(buf);
      fgets(buf,LINE_LENGTH-1,in);
      lookup[t][i1].type=r=atoi(buf);
      fgets(buf,LINE_LENGTH-1,in);
      buf[strlen(buf)-1]='\0';

      // Handle type1 (normal) factors
      if (r==1) {
        i2=0;
        if (buf[0]=='(') {
          fgets(buf,LINE_LENGTH-1,in);
          buf[strlen(buf)-1]='\0';
          while (buf[0]!=')') {
            e=MakeExponent(buf);
            lookup[t][i1].exp[i2]=InsertExponent(lookup[t][i1].exp[i2],e);
            fgets(buf,LINE_LENGTH-1,in);
            buf[strlen(buf)-1]='\0';
          }
          fgets(buf,LINE_LENGTH-1,in);
          buf[strlen(buf)-1]='\0';
        }
        while (buf[0]!='#') {
          f=MakeFactor(buf);
          lookup[t][i1].factor[i2]=InsertFactor(lookup[t][i1].factor[i2],f);
          fgets(buf,LINE_LENGTH-1,in);
          buf[strlen(buf)-1]='\0';
        }
      }

      // Handle type=2 and type=3 factors (aurifeuillian)
      else {

        // Type=3 factors have a separate exponent set & L.M aurifeuillians
        if (r==3) {
          i2=0;
          if (buf[0]=='(') {
            fgets(buf,LINE_LENGTH-1,in);
            buf[strlen(buf)-1]='\0';
            while (buf[0]!=')') {
              e=MakeExponent(buf);
              lookup[t][i1].exp[i2]=InsertExponent(lookup[t][i1].exp[i2],e);
              fgets(buf,LINE_LENGTH-1,in);
              buf[strlen(buf)-1]='\0';
            }
            fgets(buf,LINE_LENGTH-1,in);
            buf[strlen(buf)-1]='\0';
          }
        }

        // Both type=2 & type=3 have L & M exponents/factors - process L
        i2=1;
        fgets(buf,LINE_LENGTH-1,in);
        buf[strlen(buf)-1]='\0';
        if (buf[0]=='(') {
          fgets(buf,LINE_LENGTH-1,in);
          buf[strlen(buf)-1]='\0';
          while (buf[0]!=')') {
            e=MakeExponent(buf);
            lookup[t][i1].exp[i2]=InsertExponent(lookup[t][i1].exp[i2],e);
            fgets(buf,LINE_LENGTH-1,in);
            buf[strlen(buf)-1]='\0';
          }
          fgets(buf,LINE_LENGTH-1,in);
          buf[strlen(buf)-1]='\0';
        }
        while (buf[0]!='M') {
          f=MakeFactor(buf);
          lookup[t][i1].factor[i2]=InsertFactor(lookup[t][i1].factor[i2],f);
          fgets(buf,LINE_LENGTH-1,in);
          buf[strlen(buf)-1]='\0';
        }

        // Both type=2 & type=3 have L & M exponents/factors - process M
        i2=2;
        fgets(buf,LINE_LENGTH-1,in);
        buf[strlen(buf)-1]='\0';
        if (buf[0]=='(') {
          fgets(buf,LINE_LENGTH-1,in);
          buf[strlen(buf)-1]='\0';
          while (buf[0]!=')') {
            e=MakeExponent(buf);
            lookup[t][i1].exp[i2]=InsertExponent(lookup[t][i1].exp[i2],e);
            fgets(buf,LINE_LENGTH-1,in);
            buf[strlen(buf)-1]='\0';
          }
          fgets(buf,LINE_LENGTH-1,in);
          buf[strlen(buf)-1]='\0';
        }
        while (buf[0]!='#') {
          f=MakeFactor(buf);
          lookup[t][i1].factor[i2]=InsertFactor(lookup[t][i1].factor[i2],f);
          fgets(buf,LINE_LENGTH-1,in);
          buf[strlen(buf)-1]='\0';
        }
      }
    }
    // Determine maximum output table index
    s=(!t)?0:((t>3)?t-2:1);
    if (table[s].max<i1)
      table[s].max=i1;
  }
  fclose(in);
} // GetInputPmain


// Read Appendix into memory - used to load Appendicies A & C
void GetInputAppendix(
  char *file)  // Appendix file to load
{
  FILE *in;                    // Input file handle
  char buf[LINE_LENGTH]="\0";  // Buffer to hold an input line
  char t1;                     // Used with t2 to determine table index
  int t2;                      // Used with t1 to determine table index
  int t=0,i1,i2;               // t=input table index, i1=exponent, i2=index

  // Open the appendix file
  if ((in=fopen(file,"r"))==NULL) {
    printf("Cannot open %s\n",file);
    exit(8);
  }
  
  // Read in the file
  while (fgets(buf,LINE_LENGTH-1,in)) {
    // Determine the table
    buf[strlen(buf)-1]='\0';
    t1=buf[strlen(buf)-1];
    t2=atoi(buf);
    // Get the exponent and determine the table
    fgets(buf,LINE_LENGTH-1,in);
    buf[strlen(buf)-1]='\0';
    i1=atoi(buf);
    i2=(t1=='M')?2:(t1=='L'?1:0);
    switch (t2) {
    case 2:
      if (t1=='-')
        t=0;
      else {
        switch (i1%4) {
        case 0:
          t=3;
          break;
        case 1: case 3:
          t=1;
          break;
        case 2:
          t=2;
          break;
        }
      }
      break;
    case 3:
      t=(t1=='-')?4:5;
      break;
    case 5:
      t=(t1=='+')?7:6;
      break;
    case 6:
      t=(t1=='-')?8:9;
      break;
    case 7:
      t=(t1=='-')?10:11;
      break;
    case 10:
      t=(t1=='-')?12:13;
      break;
    case 11:
      t=(t1=='-')?14:15;
      break;
    case 12:
      t=(t1=='-')?16:17;
      break;
    default:
      printf("Can't determine table: %d%c\n",t2,t1);
      exit(9);
      break;
    }

    // Check the alias matches in the lookup table
    fgets(buf,LINE_LENGTH-1,in);
    buf[strlen(buf)-1]='\0';
    if (strcmp(lookup[t][i1].factor[i2]->factor,buf)!=0) {
      printf("Factor name does not match what's found in lookup: %s\n",buf);
      exit(10);
    }
    // Replace alias with actual decimal expansion, then free discarded memory
    fgets(buf,LINE_LENGTH-1,in);
    buf[strlen(buf)-1]='\0';
    free(lookup[t][i1].factor[i2]->factor);
    if ((lookup[t][i1].factor[i2]->factor=(char *)malloc(strlen(buf)+1))==NULL){
      printf("Unable to malloc the memory for the appendix factor\n");
      exit(11);
    }
    strcpy(lookup[t][i1].factor[i2]->factor,buf);
    if (!strcmp(file,FILE_IN_3))
      lookup[t][i1].unfactored=lookup[t][i1].factor[i2]->factor;
  }
  fclose(in);
} // GetInputAppendix


// Factor a Cunningham number by using the lookup tables
void factor(
  int t,  // Input table index - [0,NUM_TABLES)
  int i)  // Exponent to factor
{
  ExponentNode *e;   // Loop pointer to traverse exponent nodes
  FactorNode *f,*g;  // Loop pointers to traverse factor nodes
  int j,k,m,s;       // Various indexes

  // Determine output table index
  s=(!t)?0:((t>3)?t-2:1);

  // Traverse the lists collecting the factors into the work area
  for (j=0; j<AUR; j++) {
    for (e=lookup[t][i].exp[j]; e; e=e->next) {
      // Determine which index to use for exponent lookups
      if (strchr(e->exp,'L'))
        k=1;
      else if (strchr(e->exp,'M'))
        k=2;
      else
        k=0;
      m=atoi(e->exp);
      for (g=lookup[t][m].factor[k]; g; g=g->next) {
        work[w].table=s;
        work[w].index=m;
        work[w].unfactored=lookup[t][m].unfactored;
        strcpy(work[w].factor,g->factor);
        w++;
      }
    }
    for (f=lookup[t][i].factor[j]; f; f=f->next) {
      work[w].table=s;
      work[w].index=i;
      work[w].unfactored=lookup[t][i].unfactored;
      strcpy(work[w].factor,f->factor);
      w++;
    }
  }
} // factor


// Sort the factors by size (not lexicographically)
int compare(
  const void *a,  // 1st string
  const void *b)  // 2nd string
{
  int i,j;                      // String lengths
  WorkTable *c=(WorkTable *)a;  // Cast a to correct type
  WorkTable *d=(WorkTable *)b;  // Cast b to correct type

  if ((i=strlen(c->factor)) != (j=strlen(d->factor)))
    return(i-j);
  else
    return(strcmp(c->factor,d->factor));
} // compare


// Use recursion to do the factoring for b^n-1, since they aren't listed
// explicitly for even n in the published tables. In the case of even n we need
// to use b^n-1 = (b^(n/2)-1)(b^(n/2)+1) recursively until RHS exponent is odd.
void FindFactors(
  int t,  // Input table index - [0,NUM_TABLES)
  int i)  // Exponent being factored
{
  int j;  // Temp variable

  // Handle the special cases - not in published tables
  if (!t && i==1) {
    work[w].table=0;
    work[w].index=1;
    work[w].unfactored=NULL;
    strcpy(work[w].factor,"1");
    w++;
    return;
  }
  if (!t && i==2) {
    work[w].table=0;
    work[w].index=2;
    work[w].unfactored=NULL;
    strcpy(work[w].factor,"3");
    w++;
    return;
  }
  
  // Determine whether it is a difference of two squares case
  if (!dots(t,i)) {
    factor(t,i);
    return;
  }

  // Dots case - handle the b^(i/2)-1 factor
  j=i/2;
  if (j%2==0)
    FindFactors(t,j);
  else
    factor(t,j);

  // Dots case - handle the b^(i/2)+1 factor - select the appropriate table
  if (!t) {
    if (j%2==1)
      factor(1,j);
    else if (j%4==2)
      factor(2,j);
    else
      factor(3,j);
  }
  else
    factor(t+1,j);
} // FindFactors


// Determine primes up to i. Store results in prime array (0=prime,1=not prime)
void EratosthenesSieve(
  int i)  // Determine all primes up to i
{
  int j,k;  // Loop counters
  int max;  // floor(sqrt(i))

  // Remove 1
  notprime[1]=1;

  // Remove the multiples of 2
  for (j=4; j<=i; j+=2)
    notprime[j]=1;

  // Perform the main Eratosthenes algorithm
  for (j=3,max=(short)sqrt((double)i); j<=max; j+=2)
    for (k=2*j; k<i; k+=j)
      notprime[k]=1;
} // EratosthenesSieve


// Output text header
void OutputTextHeader(
  FILE *file,  // Text output file handle
  int t)       // Output table index [0,NUM_OUTPUT_TABLES)
{
  int i;                  // Loop counter
  FILE *in;               // Input file handle
  char buf[LINE_LENGTH];  // Buffer to hold an input line

  // Open text header file for reading
  if ((in=fopen(FILE_IN_4,"r"))==NULL) {
    printf("Cannot open %s\n",FILE_IN_4);
    exit(12);
  }

  fprintf(file,"%s\n",table[t].title);
  while (fgets(buf,LINE_LENGTH-1,in))
    fprintf(file,"%s",buf);
  for (i=0; i<OUTPUT_RECORD_LENGTH; i++)
    fprintf(file,"=");
  fprintf(file,"\n\n   n  #Fac  Factorisation\n");
} // OutputTextHeader


// Output HTML header (read in from FILE_IN_4)
void OutputHTMLHeader(
  FILE *file,  // HTML output file handle
  int t)       // Output table index [0,NUM_OUTPUT_TABLES)
{
  FILE *in;               // Input file handle
  char buf[LINE_LENGTH];  // Buffer to hold an input line

  // Open HTML header file for reading
  if ((in=fopen(FILE_IN_5,"r"))==NULL) {
    printf("Cannot open %s\n",FILE_IN_5);
    exit(13);
  }

  while (fgets(buf,LINE_LENGTH-1,in)) {
    buf[strlen(buf)-1]='\0';
    if (!strcmp(buf,"VARIABLE1\">"))
      sprintf(buf,"    %s\">",table[t].title);
    else if (!strcmp(buf,"VARIABLE1")) 
      sprintf(buf,"    %s",table[t].title);
    else if (!strcmp(buf,"VARIABLE2")) 
      sprintf(buf,table[t].header);
    fprintf(file,"%s\n",buf);
  }
  fprintf(file,"   n  #Fac  Factorisation\n");
  fclose(in);
} // OutputHTMLHeader


// Output the factors in increasing order, in a tabular format with line breaks
void OutputFactorText(
  FILE *out,  // Output handle
  int t,      // Table index
  int i)      // Exponent being factored
{
  int j,m;                      // Loop counter & m is multiplicity of a factor
  char prev[MAX_DIGIT_LENGTH];  // Previous factor
  char tmp[MAX_DIGIT_LENGTH];   // Work string
  char fac[MAX_ANSWER_LENGTH];  // Factored expression all on one line
  char *str;                    // String pointer for traversing fac
  int margin;                   // Space used for continued lines

  // Determine if there are any terms unfactored - these are marked with +
  sprintf(tmp,"%3d",w);
  for (j=0; j<w; j++) {
    if (work[j].unfactored) {
      strcat(tmp,"+");
      if (w==1)
        summary[t].num_nofactors++;
      else
        summary[t].num_somefactors++;
      break;
    }
  }

  // Generate the factors expression in one long string
  sprintf(fac,"%4d  %4s  ",i,tmp);
  strcpy(prev,work[0].factor);
  for (j=0,m=0; j<w; j++) {
    if (strcmp(work[j].factor,prev)==0)
      m++;
    else {
      if (m>1)
        sprintf(tmp,"%s^%d.",prev,m);
      else
        sprintf(tmp,"%s.",prev);
      strcat(fac,tmp);
      strcpy(prev,work[j].factor);
      m=1;
    }
  }
  if (m>1)
    sprintf(tmp,"%s^%d",prev,m);
  else
    sprintf(tmp,"%s",prev);
  if (w!=0)
    strcat(fac,tmp);

  // Print factor expression in a presentable format with decent line breaks
  str=fac;
  margin=0;
  while (strlen(str)+margin>OUTPUT_RECORD_LENGTH) {
    if (str[OUTPUT_RECORD_LENGTH-1-margin]=='.') {
      fprintf(out,"%*s%.*s\n",margin,"",OUTPUT_RECORD_LENGTH-margin,str);
      str+=OUTPUT_RECORD_LENGTH-margin;
    }
    else {
      if (str[OUTPUT_RECORD_LENGTH-2-margin]=='.')
        fprintf(out,"%*s%.*s\n",margin,"",OUTPUT_RECORD_LENGTH-1-margin,str);
      else
        fprintf(out,"%*s%.*s\\\n",margin,"",OUTPUT_RECORD_LENGTH-1-margin,str);
      str+=OUTPUT_RECORD_LENGTH-1-margin;
    }
    margin=OUTPUT_MARGIN;
  }
  fprintf(out,"%*s%s\n",margin,"",str);
} // OutputFactorText


// Output the factors in increasing order, in a tabular HTML format with line
// breaks, colour coding and hyperlinks. The colour coding and hyperlinks are as
// follows:
//   1. Prime exponents in <b class="orange">orange</b>
//   2. b^n+-1 prime in <b class="green">green</b>
//   3. Unfactored composites in <b class="red">red</b>
//   4. Hyperlinked numbers occur in previous exponents
void OutputFactorHTML(
  FILE *out,  // Output handle
  int t,      // Output table index [0,NUM_OUTPUT_TABLES)
  int i)      // Exponent being factored
{
  char tmp[MAX_DIGIT_LENGTH];     // Work string
  char line[MAX_ANSWER_LENGTH];   // Factored expression all on one line
  char margin[OUTPUT_MARGIN+2];   // Margin
  char html_begin[MAX_HTML_TAG];  // Begin tag
  char html_middle[MAX_HTML_TAG]; // HTML between tags
  char html_end[MAX_HTML_TAG];    // End tag
  char prime_type[32]="\0";       // Prime type in {"Prime", "Mersenne Prime"}
  char suffix[32];                // Suffix in {"st", "nd", "rd", "th"}
  int j;                          // A loop counter
  int l;                          // Length of a string
  int usol;                       // Current unused space on line
  char *p;                        // String pointer

  // Generate the n and #Fac (number of factors) fields
  strcpy(html_begin,"<a name=\"");
  strcpy(html_middle,"\">");
  strcpy(html_end,"</a>");
  sprintf(tmp,"%3d",w);
  for (j=0; j<w; j++) {
    if (work[j].unfactored) {
      strcat(tmp,"+");
      break;
    }
  }
  if (notprime[i])
    fprintf(out,"%s%04d%s%4d%s  %4s  ",html_begin,i,html_middle,i,html_end,tmp);
  else
    fprintf(out,"%s%04d%s<b class=\"orange\">%4d</b>%s  %4s  ",
      html_begin,i,html_middle,i,html_end,tmp);

  // Loop through all factors, wrapping html and creating line breaks
  sprintf(margin,"\n%*s",OUTPUT_MARGIN,"");
  usol=OUTPUT_RECORD_LENGTH-OUTPUT_MARGIN;
  line[0]='\0';
  for (j=0; j<w; j++) {
    p=work[j].factor;
    // Determine HTML wrapper
    if (work[j].table!=t) {
      sprintf(html_begin,"<a href=\"%s#%04d\" title=\"%s%d)\">",
        table[work[j].table].file_html,work[j].index,
        table[work[j].table].href_prefix,work[j].index);
      strcpy(html_end,"</a>");
    }
    else if (work[j].index!=i) {
      sprintf(html_begin,"<a href=\"#%04d\" title=\"%s%d)\">",work[j].index,
        table[work[j].table].href_prefix,work[j].index);
      strcpy(html_end,"</a>");
    }
    else if (work[j].unfactored && !strcmp(work[j].unfactored,work[j].factor)) {
      strcpy(html_begin,"<b class=\"red\">");
      strcpy(html_end,"</b>");
    }
    else if (!(t==0 && i==1) && w==1 && !work[j].unfactored) {
      prime_count++;
      // Set the type of prime
      if (t==0)
        strcpy(prime_type,"Mersenne Prime");
      else
        strcpy(prime_type,"Prime");
      // Set the suffix
      switch(prime_count%10) {
      case 1:
        strcpy(suffix,"st");
        break;
      case 2:
        strcpy(suffix,"nd");
        break;
      case 3:
        strcpy(suffix,"rd");
        break;
      default:
        strcpy(suffix,"th");
      }
      if (prime_count>=11 && prime_count<=13)
        strcpy(suffix,"th");
      strcpy(html_begin,"<b class=\"green\">");
      sprintf(tmp," [%d%s %s]</b>",prime_count,suffix,prime_type);
      strcpy(html_end,tmp);
    }
    else {
      strcpy(html_begin,"");
      strcpy(html_end,"");
    }
    // Generate the formatted lines of data for this factor with HTML imbedded
    strcat(line,html_begin);
    while ((l=strlen(p))>usol) {
      if (usol==1)
        strcpy(tmp,margin);
      else
        sprintf(tmp,"%.*s\\\n%*s",usol-1,p,OUTPUT_MARGIN,"");
      strcat(line,tmp);
      p+=usol-1;
      usol=OUTPUT_RECORD_LENGTH-OUTPUT_MARGIN;
    }
    if (j==w-1) {
      sprintf(tmp,"%s%s",p,html_end);
      usol-=l;
    }
    else {
      if (usol==l) {
        sprintf(tmp,"%.*s\\\n%*s%c%s.",l-1,p,OUTPUT_MARGIN,"",p[l-1],html_end);
        usol=OUTPUT_RECORD_LENGTH-OUTPUT_MARGIN-2;
      }
      else {
        sprintf(tmp,"%s%s.",p,html_end);
        usol-=(l+1);
      }
    }
    if (!usol && j!=w-1) {
      usol=OUTPUT_RECORD_LENGTH-OUTPUT_MARGIN;
      strcat(tmp,margin);
    }
    strcat(line,tmp);
  }
  fprintf(out,"%s\n",line);
} // OutputFactorHTML


// Generate table information of filenames, titles and headers
void GenerateTableInfo(
  void)  // No parameters
{
  char s[MAX_HTML_TAG];  // Temp string
  int i;                 // General purpose index
  int b;                 // Base

  for (i=0; i<NUM_OUTPUT_TABLES; i++) {
    switch (i) {
    case 0: case 1:
      b=2;
      break;
    case 2: case 3:
      b=3;
      break;
    case 4: case 5:
      b=5;
      break;
    case 6: case 7:
      b=6;
      break;
    case 8: case 9:
      b=7;
      break;
    case 10: case 11:
      b=10;
      break;
    case 12: case 13:
      b=11;
      break;
    case 14: case 15:
      b=12;
      break;
    default:
      printf("Invalid output table index [0,%d): %d\n",NUM_OUTPUT_TABLES,i);
      exit(14);
    }
    sprintf(table[i].name,"C%c(%d,n)",i%2?'+':'-',b);
    sprintf(s,"c%02d%s.txt",b,i%2?"plus":"minus");
    strcpy(table[i].file_text,s);
    sprintf(s,"c%02d%s.html",b,i%2?"plus":"minus");
    strcpy(table[i].file_html,s);
    sprintf(s,"Factor From C%c(%d,",i%2?'+':'-',b);
    strcpy(table[i].href_prefix,s);
    sprintf(s,"Factorisations Of Cunningham%s Numbers C%c(%d,n) = %s%d^n %c 1",
      i?"":"/Mersenne",i%2?'+':'-',b,i?"":"M(n) = ",b,i%2?'+':'-');
    strcpy(table[i].title,s);
    sprintf(s,"Factorisations Of Cunningham%s Numbers "
      "C<sup>%c</sup>(%d,n) = %s%d<sup>n</sup> %c 1",
      i?"":"/Mersenne",i%2?'+':'-',b,i?"":"M(n) = ",b,i%2?'+':'-');
    strcpy(table[i].header,s);
  }
} // GenerateTableInfo


// Program entry point
int main(
  void)  // This program takes no command line parameters
{
  int t;           // Output table index
  int u=0;         // Input table index
  int i;           // General purpose index
  FILE *out_text;  // Output file handle to text file
  FILE *out_html;  // Output file handle to HTML file

  // Read in the input tables
  GetInputPmain(FILE_IN_1);
  GetInputAppendix(FILE_IN_2);
  GetInputAppendix(FILE_IN_3);

  // Generate array indicating which exponents are prime
  EratosthenesSieve(MAX_EXPONENTS);

  // Generate table information of filenames, titles and headers
  GenerateTableInfo();

  // Loop through each output index and generate the output files
  for (t=0; t<NUM_OUTPUT_TABLES; t++) {

    // Open text output file for writing
    if ((out_text=fopen(table[t].file_text,"w"))==NULL) {
      printf("Cannot open %s\n",table[t].file_text);
      exit(15);
    }

    // Open HTML output file for writing
    if ((out_html=fopen(table[t].file_html,"w"))==NULL) {
      printf("Cannot open %s\n",table[t].file_text);
      exit(16);
    }

    // Output header for text/HTML output
    OutputTextHeader(out_text,t);
    OutputHTMLHeader(out_html,t);

    // Determine the input table to use for t!=1
    if (t>1)
      u=t+2;
    else if (t==0)
      u=t;

    // Set summary information
    strcpy(summary[t].table_name,table[t].name);

    // Generate the factor expression for b^n+-1
    for (i=1,prime_count=0; i<=table[t].max; i++) {
      // 2^n+1 uses 1 of 3 tables (2k+1,4k+2,4k)
      if (t==1) {
        if (i%2==1)
          u=1;
        else if (i%4)
          u=2;
        else
          u=3;
      }
      w=0;
      FindFactors(u,i);                         // Factor by lookup algorithm
      qsort(work,w,sizeof(WorkTable),compare);  // Sort the factors
      OutputFactorText(out_text,t,i);           // Generate text output
      OutputFactorHTML(out_html,t,i);           // Generate HTML output
    }

    // Output trailer for text/HTML output
    fprintf(out_html,"</pre>\n\n</blockquote>\n\n</body>\n\n</html>\n");

    // Close the output files
    fclose(out_text);
    fclose(out_html);
  }

  // Print summary report
  printf("%-8s  %4s  %4s\n","--------","----","----");
  printf("%-8s  %4s  %4s\n","Table","Some","None");
  printf("%-8s  %4s  %4s\n","--------","----","----");
  for (t=0; t<NUM_OUTPUT_TABLES; t++) {
    printf("%-8s  %4d  %4d\n",summary[t].table_name,summary[t].num_somefactors,summary[t].num_nofactors);
  }
  printf("%-8s  %4s  %4s\n","--------","----","----");

  // Uncomment these or set DEBUG to examine the tables loaded into memory
  #ifdef DEBUG
  for (i=1; i<101; i++) {
    printf("---%d---\n",i);
    PrintCunninghamTable(3,i);
  }
  #endif

  // Freeing memory & files only an excerise in good practice at this point
  FreeCunninghamTable();
  return(0);
} // main