nth ugly number

Question

Numbers whose only prime factors are 2, 3 or 5 are called ugly numbers.

Example:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

1 can be considered as 2^0.

I am working on finding nth ugly number. Note that these numbers are extremely sparsely distributed as n gets large.

I wrote a trivial program that computes if a given number is ugly or not. For n > 500 - it became super slow. I tried using memoization - observation: ugly_number * 2, ugly_number * 3, ugly_number * 5 are all ugly. Even with that it is slow. I tried using some properties of log - since that will reduce this problem from multiplication to addition - but, not much luck yet. Thought of sharing this with you all. Any interesting ideas?

Using a concept similar to "Sieve of Eratosthenes" (thanks Anon)

    for (int i(2), uglyCount(0); ; i++) {
            if (i % 2 == 0)
                    continue;
            if (i % 3 == 0)
                    continue;
            if (i % 5 == 0)
                    continue;
            uglyCount++;
            if (uglyCount == n - 1)
                    break;
    }

i is the nth ugly number.

Even this is pretty slow. I am trying to find 1500th ugly number.

Answer 1

My answer refers to the correct answer given by Nikita Rybak. So that one could see a transition from the idea of the first approach to that of the second.

from collections import deque
def hamming():
    h=1;next2,next3,next5=deque([]),deque([]),deque([])
    while True:
        yield h
        next2.append(2*h)
        next3.append(3*h)
        next5.append(5*h)
        h=min(next2[0],next3[0],next5[0])
        if h == next2[0]: next2.popleft()
        if h == next3[0]: next3.popleft()
        if h == next5[0]: next5.popleft()

What's changed from Nikita Rybak's 1st approach is that, instead of adding next candidates into single data structure, i.e. Tree set, one can add each of them separately into 3 FIFO lists. This way, each list will be kept sorted all the time, and the next least candidate must always be at the head of one ore more of these lists.

If we eliminate the use of the three lists above, we arrive at the second implementation in Nikita Rybak' answer. This is done by evaluating those candidates (to be contained in three lists) only when needed, so that there is no need to store them.

Simply put:

In the first approach, we put every new candidate into single data structure, and that's bad because too many things get mixed up unwisely. This poor strategy inevitably entails O(log(tree size)) time complexity every time we make a query to the structure. By putting them into separate queues, however, you will see that each query takes only O(1) and that's why the overall performance reduces to O(n)!!! This is because each of the three lists is already sorted, by itself.

Answer 2

I believe you can solve this problem in sub-linear time, probably O(n^{2/3}).

To give you the idea, if you simplify the problem to allow factors of just 2 and 3, you can achieve O(n^{1/2}) time starting by searching for the smallest power of two that is at least as large as the nth ugly number, and then generating a list of O(n^{1/2}) candidates. This code should give you an idea how to do it. It relies on the fact that the nth number containing only powers of 2 and 3 has a prime factorization whose sum of exponents is O(n^{1/2}).

def foo(n):
  p2 = 1  # current power of 2
  p3 = 1  # current power of 3
  e3 = 0  # exponent of current power of 3
  t = 1   # number less than or equal to the current power of 2
  while t < n:
    p2 *= 2
    if p3 * 3 < p2:
      p3 *= 3
      e3 += 1
    t += 1 + e3
  candidates = [p2]
  c = p2
  for i in range(e3):
    c /= 2
    c *= 3
    if c > p2: c /= 2
    candidates.append(c)
  return sorted(candidates)[n - (t - len(candidates))]

The same idea should work for three allowed factors, but the code gets more complex. The sum of the powers of the factorization drops to O(n^{1/3}), but you need to consider more candidates, O(n^{2/3}) to be more precise.

Answer 3

Here is a correct solution in ML. The function ugly() will return a stream (lazy list) of hamming numbers. The function nth can be used on this stream.

This uses the Sieve method, the next elements are only calculated when needed.

datatype stream = Item of int * (unit->stream);
fun cons (x,xs) = Item(x, xs);
fun head (Item(i,xf)) = i;
fun tail (Item(i,xf)) = xf();
fun maps f xs = cons(f (head xs), fn()=> maps f (tail xs));

fun nth(s,1)=head(s)
  | nth(s,n)=nth(tail(s),n-1);

fun merge(xs,ys)=if (head xs=head ys) then
                   cons(head xs,fn()=>merge(tail xs,tail ys))
                 else if (head xs<head ys) then
                   cons(head xs,fn()=>merge(tail xs,ys))
                 else
                   cons(head ys,fn()=>merge(xs,tail ys));

fun double n=n*2;
fun triple n=n*3;

fun ij()=
    cons(1,fn()=>
      merge(maps double (ij()),maps triple (ij())));

fun quint n=n*5;

fun ugly()=
    cons(1,fn()=>
      merge((tail (ij())),maps quint (ugly())));

This was first year CS work :-)

Answer 4

Basicly the search could be made O(n):

Consider that you keep a partial history of ugly numbers. Now, at each step you have to find the next one. It should be equal to a number from the history multiplied by 2, 3 or 5. Chose the smallest of them, add it to history, and drop some numbers from it so that the smallest from the list multiplied by 5 would be larger than the largest.

It will be fast, because the search of the next number will be simple:
min(largest * 2, smallest * 5, one from the middle * 3),
that is larger than the largest number in the list. If they are scarse, the list will always contain few numbers, so the search of the number that have to be multiplied by 3 will be fast.

Answer 5

Here is another O(n) approach (Python solution) based on the idea of merging three sorted lists. The challenge is to find the next ugly number in increasing order. For example, we know the first seven ugly numbers are [1,2,3,4,5,6,8]. The ugly numbers are actually from the following three lists:

• list 1: 1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2 ...     ( multiply each ugly number by 2 )
• list 2: 1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3 ...     ( multiply each ugly number by 3 )
• list 3: 1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5 ...     ( multiply each ugly number by 5 )

So the nth ugly number is the nth number of the list merged from the three lists above:

1, 1*2, 1*3, 2*2, 1*5, 2*3 ...

def nthuglynumber(n):
    p2, p3, p5 = 0,0,0
    uglynumber = [1]
    while len(uglynumber) < n:
        ugly2, ugly3, ugly5 = uglynumber[p2]*2, uglynumber[p3]*3, uglynumber[p5]*5
        next = min(ugly2, ugly3, ugly5)
        if next == ugly2: p2 += 1        # multiply each number
        if next == ugly3: p3 += 1        # only once by each
        if next == ugly5: p5 += 1        # of the three factors
        uglynumber += [next]
    return uglynumber[-1]

1. STEP I: computing three next possible ugly numbers from the three lists
   • ugly2, ugly3, ugly5 = uglynumber[p2]*2, uglynumber[p3]*3, uglynumber[p5]*5
2. STEP II, find the one next ugly number as the smallest of the three above:
   • next = min(ugly2, ugly3, ugly5)
3. STEP III: moving the pointer forward if its ugly number was the next ugly number
   • if next == ugly2: p2+=1
   • if next == ugly3: p3+=1
   • if next == ugly5: p5+=1
   • note: not using if with elif nor else
4. STEP IV: adding the next ugly number into the merged list uglynumber
   • uglynumber += [next]

Answer 6

I am working on finding nth ugly number. Note that these numbers are extremely sparsely distributed as n gets large.

I wrote a trivial program that computes if a given number is ugly or not.

This looks like the wrong approach for the problem you're trying to solve - it's a bit of a shlemiel algorithm.

Are you familiar with the Sieve of Eratosthenes algorithm for finding primes? Something similar (exploiting the knowledge that every ugly number is 2, 3 or 5 times another ugly number) would probably work better for solving this.

With the comparison to the Sieve I don't mean "keep an array of bools and eliminate possibilities as you go up". I am more referring to the general method of generating solutions based on previous results. Where the Sieve gets a number and then removes all multiples of it from the candidate set, a good algorithm for this problem would start with an empty set and then add the correct multiples of each ugly number to that.