/*
 *
 * vw.c -- This program tests sequences of natural
 * numbers to see if they satisfy the variant van der Waerden
 * property (VVW).  A sequence S satisfies VVW(S,k)
 * if for every k-coloring of the natural numbers, there are integers
 * a>0 and b>=0 such that a(S + b) is monochromatic.  When
 * VVW(S,k) holds, a simple compactness argument shows that
 * there is an integer M = M(S,k) such that for every k-coloring
 * of M = {0,1,...,M}, there are integers a>0 and b>=0 such
 * that a(S+b) is contained in M and is monochromatic.  This
 * program searches for M.  It uses a standard backtrack algorithm.
 *
 * This program was written by Kevin Compton in April 1997.  It
 * is available to the public on the condition that modifications
 * made to the program be noted here.
 *
 *
 * Questions may be directed to Kevin Compton at kjc@umich.edu.
 *
 */

#include <stdio.h>


#define Max_Colors 7            /* Maximum number of colors */
#define Max_Coloring 160	/* Upper bound for M(S,k) in search */
#define Max_Divisors 16         /* Maximum number of divisors of i<Max_Coloring */
#define Max_Pattern 10		/* Maximum size of S */
#define Out_Size 81             /* Size of output when test fails */

#define True 1
#define False 0

int coloring[Max_Coloring];	/* The coloring */
int largest_color[Max_Coloring];/* Largest color used so far */
int pattern[Max_Pattern];	/* Info on the elements of S */
int divisor[Max_Coloring][Max_Divisors];
                                /* Divisors of numbers 1..Max_Coloring-1 */
int num_colors;		        /* Number of colors (denoted k above) */
int set_size, largest;		/* Size of S  and its largest element */


/* Function Prototypes */

void main(void);
void init(void);
void divide(void);
void search(void);
int multichrome(int);


/*
 * main -- This function consists of one loop.  Each time through
 * there is a prompt for the number of colors, then a call to
 * functions that continue the input process and do the analysis.
 * The loop terminates if the user types 0 or a negative number
 * in response to the number of colors prompt.
 *
 */
void main()
{
    while(True)
    {
        printf("Number of colors (0 to stop): ");
        scanf("%d",&num_colors);
        if(0 >= num_colors) break;
        if (num_colors > Max_Colors) {
            printf("\n\nMust be at most %d.  ", Max_Colors);
            continue;
        }
        init();
        divide();
        search();
        printf("\n\n");
    }
}


/*
 * init -- This function initializes the coloring array and sets
 * the initial largest color to 0.  It then prompts for
 * the size of S, and the elements of S.  If S = {a[1],a[2],...,a[n]},
 * where a[1] < a[2] < ... < a[n], the integers a[1]-a[n],
 * a[2]-a[n],...,a[n-1]-a[n] are stored in the pattern array
 */
void init()
{
    int i;

    for(i=0; i<Max_Coloring; i++)
        coloring[i] = 0;
    largest_color[0]=0;

    for(printf("Size of S: "); ; ) {
        scanf("%d",&set_size);
        if((set_size <= Max_Pattern) && (1 < set_size)) break;
        printf("Must be at least 2 and at most %d.  Try again: ", Max_Pattern);
    }

    pattern[0] = -1;
    for(i=1; i < set_size; i++)
        for(printf("Element %d of S: ", i); ; ) {
            scanf("%d",pattern+i);
            if((pattern[i] > pattern[i-1]) &&
                (pattern[i] <= Max_Coloring-set_size+i)) break;
            printf("Must be at least %d and at most %d. Try again: ",
                pattern[i-1]+1, Max_Coloring-set_size+i);
        }

    for(printf("Element %d of S: ",i); ; ) {
        scanf("%d", &largest);
        if((largest > pattern[i-1]) &&
            (largest <= Max_Coloring)) break;
        printf("Must be at least %d and at most %d. Try again: ",
            pattern[i-1]+1, Max_Coloring);
    }

    for(i=1; i < set_size; i++)
        pattern[i] -= largest;
}

/* divide -- for integers i in the range 1,..,Max_Coloring-1
 * stores divisors of i which are at most
 * i/largest.  Divisors are stored in the 
 * array divisors[ ][ ].  divisors[n][0]
 * is the number of divisors of n, and divisors[n][k] is the k-th
 * divisor of n.  It makes sense to compute divisors before the search.
 */
void divide()
{
    int i,j,k;

    for(i=1; i<Max_Coloring; i++) {
        k = 0;
        for(j=1; j<=i/largest; j++) {
            if (i % j == 0) divisor[i][++k] = j;
        }
        divisor[i][0] = k;
    }
}


/*
 * search -- this function searches through possible colorings
 * of initial intervals {0,1,...,i} of the natural numbers
 * to see if VVW(S,k) holds.  This is a standard
 * backtrack algorithm.
 * If all instances of a(S+b) that fall in a colored interval are
 * multichromatic, the interval is expanded (i.e., i is incremented).
 * If the interval expands beyond the end of the partition array
 * then the test fails -- no M(S,k) is found, but it is possible
 * that Max_Coloring is too small for the search to succeed,
 * so no conclusions can be drawn.
 * If there is an instance of a(S+b) that is monochromatic,
 * this particular coloring is safe, so we move onto the next coloring.
 * We do this by increasing coloring[i].  To eliminate a search through
 * isomorphic colorings, we stipulate that if colors < j have
 * been used to color [0,..,i-1], then only the colors
 * < j+1 can be considered for i (or colors < k if j=k).
 * When the color possibilities have been searched,
 * the color cycles back to the original color 0 and
 * we backtrack by decreasing i.  If we backtrack all the way
 * back to i=0, every coloring we have considered has a monochromatic
 * a(S+b), and every coloring of the natural numbers has an
 * initial segment among the ones we considered.  Thus, M(S,k)
 * is the largest i that occurred.
 */
void search()
{
    int i=0, largest_i=0;

    while(True) {
        if(multichrome(i)) {
            if(++i >= Max_Coloring) {
                printf("Test failed.  No conclusion.\n");
                for(i=0;i<Out_Size;i++)putchar('0'+coloring[i]);
                return;
            }
            largest_color[i] = largest_color[i-1];
            if(largest_i < i) largest_i = i;
        }
        else {
            while((coloring[i]>=num_colors-1)||
                  (coloring[i]>largest_color[i-1])){
                coloring[i] = 0;
                if(--i == 0) {
                    printf("Test succeeded. M(S,k) = %d\n",largest_i);
                    return;
                }
            }
            ++coloring[i];
            if(coloring[i] > largest_color[i])
                largest_color[i]=coloring[i];
        }
    }
}

/*
 * multichrome -- checks if all instances of a(S+b) in the
 * present coloring of {0,1,...,i} are multichromatic.
 * This function is called only if it previously returned True
 * on the coloring restricted to {0,1,...,i-1}, so it is only
 * necessary to check the instance of a(S+b) whose last element
 * is i.  Thus, a(largest +b) = i.  This happens only when
 * a is a divisor of i and a <= i/largest.  The set a(S+b)
 * will be {i+a*pattern[1],i+a*pattern[2],...,i+a*pattern[set_size-1],i}
 * These will be the only elements we need to check
 */
int multichrome(int i)
{
    int a, j;

    for(a=1;a<=divisor[i][0];a++) {
        for(j=1; j<set_size; j++)
            if(coloring[i+divisor[i][a]*pattern[j]] != coloring[i])
                break;
        if(j == set_size)
            return(False);
    }
    return(True);
}