In looking through the voluminous comments on my previous notes on this problem, one theme emerges that I think it is important to deal with before looking at solutions in more detail: How can we be sure that we have actually solved the problem? In other words, suppose we have a program that purports to solve the problem. How can we be sure that it actually does so? The obvious way to start is to solve the problem in the simplest way we can think of, and verify that the simple solution’s output matches the one we are trying to test. An earlier post suggests such a solution:

    for (int n = 1; n < limit; ++n) {
        int i = n;
        while ((i % 2) == 0) i /= 2;
        while ((i % 3) == 0) i /= 3;
        while ((i % 5) == 0) i /= 5;
        if (i == 1)
            cout << n << “\n”; 
    }

This piece of code prints all the element of the 2-3-5 sequence that are less than the variable "limit."  Testing another program that purports to compute the elements of the sequence in order should surely begin by verifying that the program being tested produces the same output as this test program.

Of course, we should decide whether we are willing to wait for the test program to run.  In the case of this particular program, we should be able to see that checking whether a particular value n is in the sequence requires no more than one iteration for each time 2, 3, or 5 is a factor of n, which in turn is O(log n) operations.  Therefore, producing the values of the sequence up to "limit" should take O(limit x log(n)) operations, which is likely to be acceptable in practice.

After all, if our goal is to produce a huge number of elements of the sequence, we don't have to test them all.  If the program correctly produces every element of the sequence less than a million, one can be reasonably confident that it is working correctly--or at least, if the nature of the algorithm being used is such that one cannot be confident, then we had better prove that the algorithm is correct.

So we have a reasonable way of doing at least a cursory test of a purported algorithm.  The next problem is seeing whether we can do better than O(limit x log(n)).  In particular, it would be nice to come up with an algorithm with a run time that depends on the number of elements produced, rather than depending on the elements' value.