Count numbers with prime digit

Question

Given a number $N$, I need to find the count of the numbers that have atleast one prime digit $2,3,5$ or $7$ in it.

Now $N$ can be upto $10^{18}$. What is the best approach to solve this problem.

Example : Let $ N = 100$ the answer is $64$.

Answer 1

If $N$ is a power of $10$ (such as $100$ or $10^{18}$) you could count the complement: no prime digits in $N$ slots (leading $0$s allowed since they don't affect the answer). This could be done in $6^N$ ways. So your answer would be $10^N-6^N$.

For non-powers of $10$ you could build the answer using the powers-of-ten idea. For instance let's say $N=4283$:

$0$ to $1000$: $10^3-6^3$ numbers of interest.

$1000$ to $2000$: $10^3-6^3$ numbers of interest.

$2000$ to $4000$: $2000$ numbers of interest.

$4000$ to $4100$: $10^2-6^2$ numbers of interest.

etc.

---

I have added the following based on the asker's comments.

If you wanted to program this, I would suggest working recursively, using the following ideas:

Let $f(n) = $ the number of integers less than $n$ that have at least one prime digit.

If $n$ is of the form $d\cdot 10^k$ where $d$ is a digit in the range 1 to 9, then $f(d\cdot 10^k)=d\cdot 10^k-w\cdot 6^k$ where $w$ is the number of nonprime digits, including $0$ less than $d$.

For other values of $n$, let $d\cdot 10^k$ be the largest multiple of a power of $10$ less than or equal to $n$. Then we have $$ f(n)=f(d\cdot 10^k)+\left\{\begin{array}{ll} x-d\cdot 10^k & \text{if } d\in\{2,3,5,7\}\\ f(x-d\cdot 10^k) &\text{if } d\notin \{2,3,5,7\}\end{array}\right.$$

For example, if we wanted to do $f(6385)$ we'd have: $$f(6385)=f(6000)+f(385)=f(6000)+f(300)+85=(6000-3\cdot 6^3)+(300-2\cdot 6^2)+85=5665$$