Let \$n\$ be the number of digits of \$N\$, which can be determined in \$O(\ln N)\$ time.
Let \$l_{n-1}\$ be the number of lucky numbers less than \$N\$ with \$n-1\$ digits, and \$l_{n}\$ be the number of lucky numbers less than \$N\$ with \$n\$ digits.
All lucky numbers with \$n-1\$ digits are less than \$N\$; let's count them. If we only consider numbers with \$k\$ digits (i.e. numbers preceded by \$k-1\$ zeroes), then we just choose a lucky digit for each of the \$k\$ positions. Thus, there are \$3^k\$ possibilities. Doing this for each value of \$k\$, we get:
$$ l_{n-1} = \sum_{k=1}^{n-1} 3^k = \frac12 (3^n - 3) $$
which can be computed in \$O(\ln n)\$ time through repeated squaring.
Now, let's count \$l_n\$, the number of lucky numbers with exactly \$n\$ digits that are less than \$N\$. We need to count \$n-1\$ numbers that are both less than \$N\$ and lucky. There is no closed formula for this AFAIK, so instead we do a simple recursive algorithm (making use of the counting we did in the above case):
# digits is the array of digits of N, i.e. str(N).split('')
def numLucky(digits):
digit = digits.pop(0)
if digit == 1: return numLucky(digits)
if digit < 7: return 0.5*(3**n - 3)
if digit == 7: return 0.5*(3**n - 3) + numLucky(digits)
if digit == 8: return (3**n - 3) # simplified from 2*0.5*(3**n - 3)
if digit == 9: return (3**n - 3) + numLucky(digits)
Basically, if the leading digit of \$N\$ (call it \$d\$) is not a lucky number, we just multiply the number of lucky digits less than \$d\$ (which will either be 1 or 2) times the formula computed above for the number of lucky numbers with a certain number of digits. If \$d\$ is a lucky digit, we need to consider lucky numbers starting with \$d\$, which may or may not be less than \$N\$. Thus we recurse.
The runtime is the number of digits of \$N\$, so \$O(\ln N)\$