Multiplicative.c

/* --- The following code comes from C:\lcc\lib\wizard\textmode.tpl. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 200  // how many numbers the computer will look at;
                  // in principle, increasing this number makes the computer smarter

// 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=2; j<40; j++)
				  {
					  while (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);
	  deduce();
      display();
 }