# How do we test a solution to the 2-3-5 problem?

January 03, 2009

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.

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

# First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

# HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

# Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

# Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

# How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>