Big Data. Big Decisions
InformationWeek
Special Coverage Series

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 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.

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.

By The Numbers

Base: 417 respondents at organizations using or planning to deploy data analytics, BI or statistical analysis software
Data: InformationWeek 2013 Analytics, Business Intelligence and Information Management Survey of 541 business technology professionals, October 2012

What Do You Think?

 What's your attitude about SQL analysis on top of Hadoop? We want fast, standard SQL analysis capabilities on Hadoop ASAP Hadoop is for unstructured data; SQL is for relational databases We'll give SQL on Hadoop a try, but relational DBs will remain the mainstay Given strong SQL support on Hadoop, we'd nix the data warehouse We're not interested in Hadoop No opinion

Related Content

Five Big Data Challenges and How to Overcome Them with Visual Analytics

Business leaders often need a visual snapshot of data to quickly grasp and use it. This paper identifies five challenges in presenting data and how visual analytics can resolve them. Solutions are suggested to overcome the challenges of: speed, data clarity, data quality, displaying meaningful results, and dealing with outliers.

Game-Changing Analytics: How IT Executives Can Use Analytics to Create Innovation and Business Success

Today's competitive advantage requires a deeper understanding of your business, your market and your customers. As an IT executive, you can drive that knowledge transformation. In this white paper, learn how to make decisions as a strategic business leader and three steps to begin an analytics initiative within your enterprise.

Data Visualization Techniques: From Basics to Big Data with SAS Visual Analytics

High-performance data visualization turns sophisticated analyses into meaningful graphics, leading to faster and smarter decision making. In this white paper, learn how visual analytics can transform big data, with additional features such as real-time functionality, mobile compatibility, robust applications for technical groups and accessibility for nontechnical users.

Big Data: Lessons from the Leaders

Financial performance, competitive advantage, operational efficiency, strategic decision making - every business goal can extract value from big data, and the time for doubt or inaction has long passed. In this Economist Intelligence Unit report, in-depth interviews with data pioneers reveal the link between the effective use of big data and the bottom line among other results.

Decision-Driven Data Management: A Strategy for Better Decisions with Better Data

Which came first, the data or the decision? This white paper makes the case for having a decision in mind, then tailoring big data's volume, variety and velocity to achieve business results such as overcoming customer dissatisfaction or creating well-informed strategies in real time.

Informationweek Reports

Research: The Big Data Management Challenge

The challenge of big data is real, but most organizations don't differentiate 'big data' from traditional data, and nearly 90% of respondents to our survey use conventional databases as the primary means of handling data. We'll help you understand what constitutes big data (it's not just size) and the numerous management challenges it poses.