# 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 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];

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

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;

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

}
}

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