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 200

// 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;

// 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; }

if (vals[pred] == sred) return;

    if (vals[pred] == -sred)

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

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, j;

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); }

// look for multiplicativity opportunities for (i=2; i <SIZE; i++) for (j=2; j*i<SIZE; j++) { if (vals[i]== -1 || vals[i]==1) if (vals[j] == -1 || vals[j] == 1) if (vals[i*j] > 1 || vals[i*j] < -1) { printf("f(%d)=f(%d)f(%d)=%d... ", i*j,i,j,vals[i]*vals[j]);

 				  	               set(i*j, vals[i]*vals[j]);

}

if (vals[i]== -1 || vals[i]==1) if (vals[i*j] == -1 || vals[i*j] == 1) if (vals[j] > 1 || vals[j] < -1) { printf("f(%d)=f(%d)/f(%d)=%d... ", j,i*j,j,vals[i*j]*vals[i]);

 				  	               set(j, vals[i]*vals[i*j]);

} }

}

      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(" [%d-%d]\n", i-9,i); }

printf("\n");

 }

void exit_display(void)

{

display(); exit(1);

}

void main()

{

init(); set(2, 1); set(19, -1); set(37, 1); deduce();

     display();
}