Hamming sequence

Hamming's Problem

Hamming wants an efficient algorithm that generates the list, in ascending order, of all numbers of the form 2ⁱ3^j5^k for i,j,k at least 0. This list is called the Hamming sequence. The list begins like this:
1 2 3 4 5 6 8 9 10 12 15 16 18 ...

Brute force technique:

Take the first number you haven't checked yet, divide it by 2's, 3's and 5's until you can't do that any more, and if you're left with 1, then the number should go on the list; otherwise throw it away and try the next number. So:

• Is 19 on the list? No, because it's not divisible by 2, 3, or 5.
• Is 20 on the list? Yes, because after we divide it by 2, 2, and 5, we're left with 1.
• Is 21 on the list? No, because after we divide it by 3, we're left with 7, which isn't divisible by 2, 3, or 5.

This obvious technique has one problem: it's unbelievably slow. The problem is that most numbers aren't on the list, and you waste an immense amount of time discovering that. Although the numbers at the beginning of the list are pretty close together, the 2,999th number in the list is 278,628,139,008. Even if you had enough time to wait for the brute-force algorithm to check all the numbers up to 278,628,139,008, think how much longer you'd have to wait for it to finally find the 3,000 number in the sequence, which is 278,942,752,080.

Linear Solution:

The idea is that to calculate a[i], we can use a[j]*2 for some j < i. But we also need to make sure that:
1) a[j]*2 > a[i - 1] and
2) j is smallest possible.

Then, a[i] = min(a[j]*2, a[k]*3, a[t]*5)

 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(void) {
  // get n from user
  unsigned n;
  cout <<"n: ";
  cin >>n;

  // list of ugly numbers
  vector <uint64_t> ugly;
  uint64_t x = 1;
  ugly.push_back(x);

  // index of next multiple
  unsigned i2 = 0, i3 = 0, i5 = 0;

  // value of next multiple
  uint64_t x2 = 2, x3 = 3, x5 = 5;

  // loop through ugly numbers
  for(unsigned a = 1; a < n; a++) {

    x = std::min(x2, std::min(x3,x5));

    ugly.push_back(x);
    if (x == x2) { i2++; x2 = ugly[i2] * 2; }
    if (x == x3) { i3++; x3 = ugly[i3] * 3; }
    if (x == x5) { i5++; x5 = ugly[i5] * 5; }
  }

  // return last ugly number found
  cout << x << endl;
  return 0;

}