Multiplicative.c

/* --- The following code comes from C:\lcc\lib\wizard\textmode.tpl. */

1. include <stdio.h>
2. include <stdlib.h>
3. include <string.h>

1. define SIZE 500

// our knowledge is encoded in the following array

int vals[SIZE+1]; // vals[i] = +a means f(i) = +f(a); vals[i] = -a means f(i) = -f(a). int up[SIZE+1]; // best known upper bound for f[1,n] int low[SIZE+1]; // best known lower bound for f[1,n]

void deduce(void); void exit_display(void);

void init( void )

{

int i; int j;

vals[0] = 0; up[0] = 0; low[0] = 0;

for (i=1; i <= SIZE; i++) { vals[i] = i; for (j=1; j<40; j++) { if (vals[i] % (j*j) == 0) vals[i] /= j*j; } if (i % 2 == 0) { up[i] = 2; low[i] = -2; } else { up[i] = 1; low[i] = -1; } }

}

int modified=0;

void set( int p, int s ) // set f(p) = s

{

int i; int pred, sred;

if (vals[p] == s) return;

    if (vals[p] == -s)

{ printf("Contradiction! f(%d) = 1 and f(%d) = -1\n", p, p); exit_display(); }

if (vals[p] == p) { pred = p; sred = s; } else // need to reduce f(p)=s to f(pred)=sred { if (vals[p] > 0) { pred = vals[p]; sred = s; } else { pred = -vals[p]; sred = -s; } }

printf("Setting f(%d)=%d...\n",pred,sred);

for (i=1; i<SIZE; i++) while (vals[i] % pred == 0) { vals[i] /= pred; vals[i] *= sred; }

modified=1;

}

void newup( int i, int new) // add f[1,i] <= new to knowledge

{

if (up[i] <= new) return; // is redundant

if (low[i] > new) { printf("Contradiction! %d <= f[1,%d] <= %d\n", low[i], i, new); exit_display(); }

// printf(" (up[%d] = %d)", i, new);

    up[i] = new;
    modified = 1;
}

void newdown( int i, int new) // add f[1,i] >= new to knowledge

{

if (low[i] >= new) return; // is redundant

if (up[i] < new) { printf("Contradiction! %d >= f[1,%d] >= %d\n", up[i], i, new); exit_display(); }

//   printf(" (low[%d] = %d)", i, new);

    low[i] = new;
    modified = 1;
}

void cut(int i) // we learn that f[1,i] = 0 { if (up[i] == 0 && low[i] == 0) return;

if (up[i] < 0) { printf("Contradiction! f[1,%d]=-2 but f(%d)=f(%d+1)\n", i, i, i); exit_display(); } if (low[i] > 0) { printf("Contradiction! f[1,%d]=+2 but f(%d)=f(%d+1)\n", i, i, i); exit_display(); }

// printf(" (cut[%d])", i);

up[i]=0; low[i]=0; modified=1; }

void deduce( void )

{

int i;

do { printf("Deducing...\n"); modified = 0;

// begin forward scan to update up,low

for (i=1; i < SIZE; i++) if (vals[i] == 1 || vals[i] == -1) { newup(i, up[i-1]+vals[i]); newdown(i, low[i-1]+vals[i]); }

// begin backward scan to update up,low

for (i=SIZE-1; i > 0; i--) if (vals[i] == 1 || vals[i] == -1) { newup(i-1, up[i] - vals[i]); newdown(i-1, low[i] - vals[i]); }

// look for cuts

for (i=1; i < SIZE; i++) if (i % 2 == 1 && vals[i] == vals[i-1]) cut(i-1);

// look for peaks and troughs

for (i=1; i < SIZE-1; i++) { if (up[i] <= low[i-1]) set(i,-1); if (low[i] >= up[i-1]) set(i, 1); } }

      while(modified);
}

void display( void )

{

int i;

printf("\n");

  for (i=0; i < SIZE; i++)

{ if (up[i-1] == 0 && low[i-1] == 0) printf("|"); else if (low[i-1] == 2) printf("^"); else if (up[i-1] == -2) printf("v"); else printf(" ");

printf(" %4d ", vals[i]);

if (i % 10 == 9) printf("\n"); }

printf("\n");

 }

void exit_display(void)

{

display(); exit(1);

}

void main()

{

init();

set(2, 1); deduce();

     display();
}