Friday, September 30, 2011

Hamming Numbers

This exercise is taken from www.programmingpraxis.com
=========================================================
"The sequence of Hamming numbers 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, … (A051037) consists of all numbers of the form 2i·3j·5k where i, j and k are non-negative integers. Edsger Dijkstra introduced this sequence to computer science in his book A Discipline of Programming, and it has been a staple of beginning programming courses ever since. Dijkstra wrote a program based on three axioms:

Axiom 1: The value 1 is in the sequence.

Axiom 2: If x is in the sequence, so are 2 * x, 3 * x, and 5 * x.

Axiom 3: The sequence contains no other values other than those that belong to it on account of Axioms 1 and 2.

Your task is to write a program to compute the first thousand terms of the Hamming sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below."

=========================================================

Here is my C solution

=========================================================

#include 
#include 

int ham_num(int x) {
    int h = x;
    while (h && (h%2 == 0)) 
        h = h/2;

    while (h && (h%3 == 0)) 
        h = h/3;
    
    while (h && (h%5 == 0)) 
        h = h/5;
   /* 
    * h will be 1, when it is ham num, else it will be  
    * something else - example h =10  
    */
   return h;
}

int main(int argc, char *argv[])
{
    int x = 1, cnt = 1000;
    printf("Hamming Numbers : \n");
    if (argc > 1)  
        cnt = atoi(argv[1]); 

    while (cnt) {
        if (ham_num(x) == 1) {
            printf("%d ",x);
            cnt--;
        }   
        x++;
    }   
    printf("\n");
}