10
\$\begingroup\$

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?

\$\endgroup\$
  • 2
    \$\begingroup\$ (Side note: This is similar to the so-called "Hamming numbers" which have prime factors 2,3,5 only. Some sophisticated methods so save both time and storage space can for example be found at rosettacode.org/wiki/Hamming_numbers#Python.) \$\endgroup\$ – Martin R Nov 13 '15 at 10:00
14
\$\begingroup\$

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: 2*humble numbers, 3*humble numbers, 5*humble numbers, and 7*humble 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.091s |
| 4000 |      1730.465s |          0.123s | #ok, I only ran this one once
+------+----------------+-----------------+
\$\endgroup\$
  • \$\begingroup\$ Thank you! That was so helpful, both for how to structure my code and why it wasn't O(N). 10/10 answer, great introduction to the site :) \$\endgroup\$ – txizzle Nov 14 '15 at 11:03
  • \$\begingroup\$ (previous erroneous comment deleted). Indeed, if we calculate the log(H(N)) values from your first table and calculate the empirical orders of growth for the resulting sequence, we get the list [0.32, 0.29, 0.27, 0.26], going closer and closer to the theoretical 0.25. \$\endgroup\$ – Will Ness Dec 23 '18 at 16:26
6
\$\begingroup\$

This Code Review, so let us review your code, before proceeding to questions and optimisations.

Code and style review

  • Choose better names – According to python style guide, PEP8, you should use snake_case for variables and functions. In addition what does dp, acc stand for? And in general one should avoid single letter variables except in tight loops
  • Uncomfortable while loop – I'm a little confused by the loop in humbleNumber, you have loop using i < n, but mostly you focus and increment on curr. This doesn't read good, and is somewhat confusing.
  • Anti-pattern of if True: variable = True – Setting a variable to True or False after you just checked it in an if statement, is kind of an anti-pattern. Normally you should rather do dp[curr] = ishumble[curr, dp). In your code this does require some other changes as well. See code refactor below
  • Add spaces after commas – Don't clamp up list like in [2,3,5,7], add spaces around operations and after commas. It is better with [2, 3, 5, 7] and ishumble(x, dp) and so on
  • Comment your code – Add docstrings to your functions, and comment before non-intuitive code segments
  • BUG: ishumble(x/i) is missing the dp parameter – When testing a slightly modification of your code, I actually got to call the line which you comment that you don't get called, and it fails as it hasn't gotten enough parameters! (So yes, it doesn't get called in your version, and no, it doesn't work!)

Code refactored

After correcting these issue you could end up with:

def humble_number(n):
    """Return n'th number divisble only by 2, 3, 5 and 7."""

    humble_numbers = {}
    i, candidate = 0, 0

    while i < n:

        # Find next humble number
        while True:
            candidate += 1
            humble_numbers[candidate] = ishumble(candidate, humble_numbers)

            if humble_numbers[candidate]:
                break

        i += 1

    return candidate

You could do similar refactoring to the ishumble, but you should really replace that function with something more effective.

Time and space complexity

Your code is not plain \$O(n)\$. At least not \$n\$ as the n'th humble number. This comes from the simple fact that you loop all numbers, curr, until you find your n'th humble numbers, and the 1689th humble number is 330674. Clearly you've checked 330674 numbers to get the 1689th humble numbers, and that is not \$O(n)\$. In addition your method uses a dict to store previously calculated humble numbers, so it has a memory complexity of \$\theta (n)\$.

A better approach would be to use generators to calculate the next humble number, using the information that the next number has to be next multiple of 2, 3, 5, or 7 compared to a previous humble number. Various approaches exists to do this, amongst them the one in Barrys answer (which got written while I write this answer), or the one suggested by Martin R from Rosetta code related to Hamming numbers.

If you incorporate the Rosetta Code's "Cyclic generator method #2" from link above, and replace the hamming() function with the the following you'll get a quite fast version:

def humble_number(a, b = None):
    if not b:
        b = a + 1
    seq = (chain([1], pp(7, pp(5, pp(3, p(2))))))
    return list(islice(seq, a - 1, b - 1)) 

Do however note that I don't recommed the variable naming, and the lack of comments on this code. According to Rosetta code this should be faster than a version based on heapq.merge, but I currently don't have time to run time verification on that.

\$\endgroup\$
  • 2
    \$\begingroup\$ Why lead your review off with the importance of choosing good variable names, and then post a solution that is (a) incomplete (what are pp, p?) and (b) uses the worst possible variable names (again, wtf are pp and p)? \$\endgroup\$ – Barry Nov 13 '15 at 15:46
  • 1
    \$\begingroup\$ @Barry, I do agree that the names are terrible, but they are a part of the Rosetta Code solution I refer to. And the main point is still to use generators to generate the humble number sequentially, and not loop every number as the original code of the OP did. \$\endgroup\$ – holroy Nov 13 '15 at 15:52
3
\$\begingroup\$
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

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

If you believe that some condition is always fulfilled, but you don't want to or are not able to prove it, you could let Python verify it for you by using an assertion:

if x % i == 0:
    assert x/i in dp, "x/i is not in dp: {}/{}".format(x, i)
    return dp[x/i]

This way, you don't have dead code, but will still be notified when your assumptions should turn out wrong.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.