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