How many numbers are there such that its number of decimal digits equals to the number of its distinct prime factors?

Question

Problem

A positive integer is said to be balanced if the number of its decimal digits equals the number of its distinct prime factors. For instance, $15$ is balanced, while $49$ is not. How many balanced numbers are there?

My thoughts

One digit balanced numbers are the prime ones. So, we have $4$ one digit balanced numbers.
Number of 2 digit balanced numbers = number of 2 digit numbers - number of 2 digit prime numbers - number of 2 digit prime powers = $90-21-10=59$.
We can continue doing this until we find no balanced number. But this gets messier in each step.
Edit: As in the comments, I missed many of the numbers.

---

Is there some easier way to solve the problem?

Answer 1

The total number of these numbers is $7812$.

The number of such $n$ digit numbers $a(n)$ is:

n     a(n)
1     7
2     54
3     267
4     871
5     1783
6     2260
7     1708
8     718
9     138
10    6

where $a(n)=0,n\gt 10$, as mentioned by Calvin Lin.

It is sufficient to examine products of $n$-subsets of primes. That is, examine square-free numbers. Then, all solutions are numbers that are multiples of these products (possibly increment exponents of individual primes to iterate these multiples without adding excess factors) and also have correct number of digits.

I used python. I'm not sure if there is a pure mathematical approach (no computers).

from sympy.ntheory import factorint, sieve

def main():
    B = 10 # number base
    r = 0  # total count
    for n in range(1,12):
        R = set()
        G = set()
        a = 0
        n-= 1
    
        # find products of n-subsets of primes in range.
        h([0 for _ in range(n+1)],n,n,B,G)
    
        # find multiples of products that satisfy property.
        for g in G:
            m = 0
            a = g*m
            while a<B**(n+1):
                m += 1
                a = g*m
                if a>=B**n and a<B**(n+1):
                    if len(factorint(a))==n+1:
                       R.add(a)
        print(n+1, len(R))
        r += len(R)
    print(f"Total: {r}.")

# h = try all combinations of distinct primes that won't overshoot
def h(S,d,n,B,G):
    if d==0:
        while f(S,n,B,G)<B**(n+1):
            S[0] += 1
        S[0]=0
        if len(S)>1:
            S[1]+=1
        return S
    else:
        while f(S,n,B,G)<B**(n+1):
            S = h(S,d-1,n,B,G)
        S[d]=0
        if len(S)>d+1:
            S[d+1]+=1
        return S

# f = evaluate the vector S containing indices of corresponding primes
def f(S,n,B,G):
    e,N=0,1
    for s in S:
        N *= sieve[s+e+1]
        e += s+1
        if N>=B**(n+1):
            break
    if N<B**(n+1):
        G.add(N)
    return N

if __name__ == "__main__":
    main()

This python code is not the fastest or prettiest approach, but simply was quick and easy to think of on the spot. Nonetheless, it gets the job done in less than few seconds.

I've also verified these results with a much slower brute force in WA Mathematica.

Answer 2

Hint:

$$2*3*5*7*11*13*17*19*23*29*31 > 10^{11}.$$

Use this to conclude that the balanced number has at most 10 distinct prime factors.

---

However, from here, it's seems to be tedious (and easy to miss, per the comments) but finite casework to calculate the number of $n\leq 10$ digit numbers with $n$ distinct primes.

Answer 3

The place to start is to list the primes in order:
$p_1 = 2, p_2 = 3, p_3 = 5, \cdots.$

Then, identify the smallest value $k \in \Bbb{Z^+},~$ such that $\prod_{i = 1}^k p_i \geq (10)^k$. Note that with a computer program, this can easily be done via logarithms, base $(10)$.

Then, you know that you need consider no more than $(k-1)$ distinct primes, whose product is $< (10)^k$.

One point of clarification is whether $(3^2) = 9$ is considered balanced.

Anyway, I see no analytical way to approach this problem, so I would simply write a computer program to count $f(i)$, where $i \in \{1,2,\cdots, (k-1)\}$, and $f(i)$ represents the number of balanced numbers that are $\geq (10)^{(i-1)}$ and $< (10)^i.$ Again, my computer program would use logarithms, base $(10)$.

One potential trap, is that when $k$ is identified, although you know that the product must be $< (10)^k$, that does not necessarily exclude primes $\geq p_k$ from consideration.