8
$\begingroup$

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?

$\endgroup$
8
  • 1
    $\begingroup$ What makes you sure that you'd continue on and on and reach a point where you won't find a balanced number? $\endgroup$ – user112196 Jun 20 at 10:46
  • 1
    $\begingroup$ For the 2 digit case also need to subtract for 30 and 70 which have 3 distinct prime factors. $\endgroup$ – coffeemath Jun 20 at 10:48
  • 2
    $\begingroup$ For 1 digit would you include 4 since it has only one distinct prime factor? $\endgroup$ – coffeemath Jun 20 at 10:51
  • 1
    $\begingroup$ It is indeed from a contest (Italy MO 1999 P2) which says to "prove there is a finite number of balanced numbers". But I modified it to "how many balanced numbers are there"? @SathvikAcharya $\endgroup$ – Unknown Jun 20 at 11:23
  • 1
    $\begingroup$ I see, I missed many of the numbers. @coffeemath $\endgroup$ – Unknown Jun 20 at 11:28
4
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ I get at most 10 different primes. If there are 10, the largest is at most 43, and six cases work. That at least gets the task below a billion. $\endgroup$ – Empy2 Jun 20 at 12:45
  • $\begingroup$ @Empy2 Yes, updated the bound. $\endgroup$ – Calvin Lin Jun 20 at 14:41
  • $\begingroup$ 3 mod 4, need an odd number of 3 mod 4 factors, 1 mod 4 need an even number of them, that should narrow the odd number ones down ... $\endgroup$ – Roddy MacPhee Jun 20 at 15:14
  • $\begingroup$ @RoddyMacPhee Why do we need an odd number of 3 mod 4 factors? EG $3^2 = 9 $ and $ 3 \times 7 = 21$ are both balanced. $\endgroup$ – Calvin Lin Jun 21 at 15:38
  • $\begingroup$ I mean in the factorization of any 3 mod 4 number there are an odd number of them. As both 1 and 3 square to 1, you need an odd one out so to speak. Same is true with 1 and -1 mod 6 $\endgroup$ – Roddy MacPhee Jun 21 at 15:39
1
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ Given that 49 is not balanced, I would count 9 as balanced. $\endgroup$ – Calvin Lin Jun 20 at 11:10
  • $\begingroup$ @SathvikAcharya An argument can be made either way. The OP needs to address this question. $\endgroup$ – user2661923 Jun 20 at 11:15
  • $\begingroup$ @user2661923 What is your argument which makes 49 not balanced and 9 not balanced? $\endgroup$ – Calvin Lin Jun 20 at 11:16
  • 1
    $\begingroup$ @user2661923 (Right, I edited my comment almost immediately). But then, according to your logic, 49 is a 2 digit number with 2 prime factors (and these prime factors are not distinct), so it is balanced. So, it's not a consistent argument for both 9 and 49 to be not balanced. $\endgroup$ – Calvin Lin Jun 20 at 11:19
  • 1
    $\begingroup$ 49 has two prime factors (7 & 7). But since they are same, we can count them as one and we can say 49 has only one distinct prime factor. So, it's not balanced. Again for 9, it is a one digit number and has only one distinct prime factor. So, it is indeed balanced. Hope this concludes the debate. @user2661923 $\endgroup$ – Unknown Jun 20 at 11:47

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.