When I described the 2-3-5 problem in my last post, I did not expect as many comments as I got. The first wave of comments was about the precise meaning of the words in the problem description, so I eventually re-described the problem using Dijkstra's original terms: Write a program that produces the elements of a sequence such that

• 1 is an element of the sequence.
• If n is an element of the sequence, then so are 2n, 3n, and 5n.
• All elements of the sequence are determined in this way.

An alternative way to state the problem is that it is to find positive integers such that if n is a prime factor of one of these integers, then n is 2, 3, or 5. So, for example, 12 is an element of the sequence, because its only prime factors are 2 and 3 (even though 2 appears twice), but 14 is not an element because its prime factors include 7. Moreover, 1 is an element of the sequence under both definitions, because the fact that it has no prime factors at all means that it satisfies the condition "if n is a prime factor" vacuously for all values of n.

So far, the comments about my last post include three solutions; I would like to take a look at each of them.

One solution was claimed to be "obvious:"

for (int i = 1; true; i++) {
if (((i%2)%3)%5) == 0) print(i);
}

I'm usually suspicious when someone describes a solution to a problem as obvious, and this case is no exception. I'm not troubled by the fact that this program fragment never terminates, because it's intended as a sketch of a solution, not a complete solution. However, I am troubled by what I see when I try to figure out what values of i will be printed.

Here's the problem. The program divides i by 2 and takes the remainder. That remainder is either 0 (if i is even) or 1 (if i is odd). Once we have that remainder, we can repeat the process with any other divisors, and we will still get 0 if i is even and 1 if i is odd. So this program fragment prints all the positive even integers. In particular, it should never print 3 or 5, because they are not even. So this program cannot possibly be right.

The next solution uses a large boolean array. Each element of the array is initially false. The program then does the following:

array[1] = true;

for (int i = 2; i < arraysize; i += 2) array[i] = true;
for (int i = 3; i < arraysize; i += 3) array[i] = true;
for (int i = 5; i < arraysize; i += 5) array[i] = true;

after which the program's author claims that the true elements of the array correspond to the elements of the result sequence. So, for example, 5 is one of the results, a fact that is reflected by array[5] being true.

Unfortunately, this solution doesn't work either. The problem that it solves is to find every number that has 2, 3, or 5 among its prime factors, and the problem that we were trying to solve was to find numbers that have 2, 3, and 5 as their prime factors and have no other prime factors. So, for example, this program will include 14 as part of its output, but it should not do so because 14 has both 2 and 7 as prime factors.

Which brings us to the third solution:

int i = n;
while ((i % 2) == 0) i /= 2;
while ((i % 3) == 0) i /= 3;
while ((i % 5) == 0) i /= 5;
if (i == 1) print(n);

This solution looks right to me. It removes 2, 3, and 5 as prime factors (by dividing n by each of these numbers as many times as it can--which might be zero times), and then checks whether what is left is 1. If the final value of i is 1, it means that n had no other prime factors, so n is part of the result sequence.

Of course, this solution takes progressively longer to run as the values of n increase. Therefore, the solution raises a new question: Is there a way to make the program run more quickly? If so, is it worthwhile to do so?

I will address these questions in a future post.