Find the Nth number divisible by only 2,3,5, or 7

I recently participated in a small friendly competition and this was one of the questions:


A number whose only prime factors are 2, 3, 5 or 7 is called a humble
number. The first 20 humble numbers are: 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ...


Given n, find the nth humble number.


Example


n = 1: 1; n = 11: 12; n = 22: 30


[input] integer: positive integer n


[output] integer: The nth humble number.


There should be a O(N) solution!

Here's my solution:

def humbleNumber(n):
    curr = 0
    i = 0
    dp = {}
    while i < n:
        curr += 1
        if ishumble(curr, dp):
            dp[curr] = True
            i += 1
        else:
            dp[curr] = False
    return curr

def ishumble(x,dp):
    if x == 1:
        return True
    acc = [2,3,5,7]
    for i in acc:
        if x % i == 0:
            if (x/i) in dp:
                return dp[x/i]
            return ishumble(x / i) #i don't believe this ever get's called
    return False

I believe that this solution is \$O(N)\$. I am iterating up to \$n\$, and at each step, I am calling a constant-time helper function. The helper function ishumble(x, dp) will check if the current number x is a humble number. We are able to do this in constant time because we are guaranteed that if x % i == 0, then (x/i) is in dp! So I believe that the return ishumble(x / i) line is actually never called.

Therefore, this solution is in \$O(N)\$. Is my analysis correct? Is there a better solution?

No, not \$O(n)\$. Not even close. I'll get back to this later though. First, the code:

It's a little difficult to tell what your loop logic is. curr is getting incremented each time, but i isn't... whereas typically we'd use i as a loop index. I'd propose using i as the loop index, and then keeping a humble number count named count (or num_humbles or something):

count = 0
dp = {}
for i in itertools.count(start=1):
    if ishumble(i, dp):
        dp[i] = True
        count += 1
        if count == n:
            return i
    else:
        dp[i] = False

You are also correct in this comment:


#i don't believe this ever get's called

That'll happen in the case where x is divisible by one of our primes, but we somehow haven't seen x/p yet. But we are iterating in order, so you're guaranteed that y in dp for all y<x. So you can simplify that block to:

if x % i == 0:
    return dp[x/i]

Though if you reread that statement again, you'll see that there's no need for dp to be a dictionary. You can just make it a list.

Split things up

Rather than having one function that does both generate the humble numbers and return the nth one, you can split them up. Have one function that generates the humble numbers:

def humble_numbers():
    dp = {}
    for i in itertools.count(start=1):
        if ishumble(i, dp):
            dp[i] = True
            yield i
        else:
            dp[i] = False

And another function that returns the nth one. Actually, that part is a snap using the nth recipe:

def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(islice(iterable, n, None), default)

So the solution becomes:

def humbleNumber(n):
    return nth(humble_numbers(), n)

Note that now that we separated out the original idea into "generate the numbers" and "get the nth one" as separate, we can just play around with the generating functions.

Runtime

Your algorithm is deceptively easy to analyse. For each number we check, we do at most 4 modulo operations, at most 1 dictionary lookup, and 1 dictionary insertion. That's all reasonable and obviously super cheap. But, are we doing one cheap operation per \$n\$? NO, we're not, but it's easy to fall into that trap. Because we're not iterating up to \$n\$... we're iterating up to the \$n\$th humble number. Thus, the runtime is really \$O(H(n))\$.

And humble numbers get really sparse. Here's an unnecessarily prettified table for what the growth rate looks like:

+---------+---------------------------------------+
|       N |                                  H(N) |
+---------+---------------------------------------+
|      10 |                                    12 |
|     100 |                                   480 |
|    1000 |                                387072 |
|   10000 |                           63248102400 |
|  100000 |                 123098144531250000000 |
| 1000000 | 4157518627998641643389868083057746290 |
+---------+---------------------------------------+

Your runtime complexity grows commensurately with the second column. According to Wikipedia, that means your algorithm is something on the order of \$O(e^{\sqrt[4]{n}})\$?

A better approach

Rather than checking every individual number (which leads to terrible runtime complexity), we can build numbers up from the bottom. The numbers we want are basically \$2^a3^b5^c7^d\$, for all \$a,b,c,d\$. Of course, that's difficult to iterate over (how do you know which one to do next?). But a different way of writing that is each humble number is either 2x, 3x, 5x, or 7x some previous humble number. And that's easy to iterate over:

def humble_numbers2():
    primes = (2,3,5,7)
    result = [1]
    yield 1

    def make_multiple(_p):
        return (_p * result[i] for i in itertools.count())

    iters = map(make_multiple, primes)
    merged = heapq.merge(*iters)
    for k,_ in itertools.groupby(merged):
        result.append(k)
        yield k

The key is heapq.merge, which joins sorted iterables (which we know ours are). Basically we're on the fly creating the lists: 2humble numbers, 3humble numbers, 5humble numbers, and 7humble numbers - which are all humble numbers - and then using itertools.groupby to drop the duplicates (because, e.g., 14 is both 2x the 7th humble number and 7x the 2nd humble number)

This approach is \$O(n)\$. We are only performing constant operations to determine the next humble number. Which, when in doubt, we can always very by timing how long it takes to find the Nth humble number 10 times (after making the modifications I proposed to your solution):

```
+------+----------------+-----------------+
| N | humble_numbers | humble_numbers2 |
+------+----------------+-----------------+
| 100 | 0.003s | 0.002s |
| 1000 | 2.890s | 0.028s |
| 2000 | 53.332s | 0.059s |
| 3000 | 384.589s | 0.091

StackExchange Code Review Q#110647, answer score: 14