# The 2-3-5 problem -- a first look at some solutions

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 2*n*, 3*n*, and 5*n*.

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.

More Insights

Newest First| Oldest First | Threaded Viewpost a commentregarding this story.