A Nearly Complete Solution to Hamming's Problem

input: A list of prime numbers in increasing order entered in the command tail
output:



 A stream of integers, each having at least one of the given prime
numbers as a factor and only prime numbers from the given list of
primes as factors. The integers are placed in the output stream
in increasing order.
limits:


Since the stream is infinite and computer resources are bounded, not all of
the stream can be constructed. However, the code below makes no attempt at
determining when a resource bound is reached.

Conceptual Description of the Code.

Let ham(p) be the stream of integers representing the solution to the instance of Hamming's problem given by the list of primes p. Let hamming(p,T) be the stream ham(p) multiplied by the positive integer T. Let car(p) be the first element of the list of primes p. Let cdr(p) be the list of primes equal to p with car(p) removed. Let + denote stream concatenation. Then 
   hamming(p,T) =
        if (p == NULL) return(NULL);
        else
        return(car(p)*T + merge(hamming(p,car(p)*T),hamming(cdr(p),T)))

Implementation Notes

The recursive solution specified above cannot be implemented directly in C. One must first build an abstraction and then compose a solution based on that abstraction. The abstract "machine" which we call queue simulates the suspension of the computation of stream tails. This is accomplished by storing enough state to uniquely define the future of the computation of the stream from the point of suspension. The current implementation of queue is based on maintaining a linear list and is, therefore, not optimally efficient. 

#include < stdio.h >

#define ADD 1
#define POP 2

long a[1000][4],head = 1,tail = 0;

/**********************************************************************
 *
 *  queue:  < ADD > X < state-array > -> suspends process & stores state-array
 *          < POP > X < state-array > -> resume process of least "value"
 *                                   (state-array is output)
 *
 **********************************************************************/
long queue(int func, long q[])
{
   long tptr, i, val_arg, ptr_arg, t_arg;

   val_arg = q[1];
   ptr_arg = q[2];
   t_arg   = q[3];

   if (func == ADD)
   {
      tptr = ++tail;
      while (a[tptr-1][1] > val_arg && tptr > head)
      {
         for (i=1; i<=3; i++) a[tptr][i] = a[tptr-1][i];
         tptr -= 1;
      }
      a[tptr][3] = t_arg;
      a[tptr][2] = ptr_arg;
      a[tptr][1] = val_arg;
   }
   else
   if (func == POP)
   {
      q[1] = a[head][1];
      q[2] = a[head][2];
      q[3] = a[head][3];
      head++; 
   }
}

long ham(long p[])
{
   long right[4], left[4], q[4], i;
   int fbreak();

   right[1]=0; right[2]=0; right[3]=0;
   left[1]=0; left[2]=0; left[3]=0;

   q[1]=p[1]; q[2]=1; q[3]=1;
   queue(ADD,q);

   while (1)
   {
      queue(POP,q);
      printf("%d ", q[1]);
      if (getchar() == 27) exit(0);

      left[1]=q[3]*p[q[2]+1];
      left[2]=q[2]+1;
      left[3]=q[3];

      right[1]=q[3]*p[q[2]]*p[q[2]];
      right[2]=q[2];
      right[3]=q[3]*p[q[2]];

      queue(ADD ,right);
      if (left[1]>0) queue(ADD ,left);
   }
}

main(int argc, char **argv)
{
   long p[11], i;

   printf("\nprime list:");
   p[argc] = 0;
   for ( i = 1 ; i < argc ; i++ )
   {
      p[i] = atoi(argv[i]);
      printf(" %d", p[i]);
   }
   printf("\n\n");

   ham(p);
}