/*
*
* 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
#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= 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 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) {
printf("Test failed. No conclusion.\n");
for(i=0;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