2
$\begingroup$

A positive integer, n, where the number of its decimal digits (base 10) equals the number of its distinct prime factors has an upper-bound (there is a maximum n).

Anyone knows the proof for this?

Thinking of establishing a relationship between number of digits and number of decimal places (and $10^x < n$) and proving n has an upper bound. I have tried linking the fact that the number of primes $\leq n$ is $\frac n{\ln n}$, but can't seem to find a good link.

$\endgroup$
  • 1
    $\begingroup$ Welcome to MSE. What have you tried? $\endgroup$ – Ennar Sep 17 '17 at 8:27
  • 1
    $\begingroup$ Thinking of establishing a relationship between number of digits and number of decimal places (and 10^x < n) and proving n has an upper bound. I have tried linking the fact that the number of primes <= n is n/(lnn), but can't seem to find a good link. $\endgroup$ – Jacob Sep 17 '17 at 8:57
  • $\begingroup$ You should add this in the body of the question. Often will the questions similar to yours be closed for lack of context. Writing your attempt solves the problem and you will more likely get an answer. $\endgroup$ – Ennar Sep 17 '17 at 9:00
  • $\begingroup$ Great, thank you for the edit. Also, when you have some time to spare, you can learn how to format mathematics on MSE using MathJax. $\endgroup$ – Ennar Sep 17 '17 at 9:11
2
$\begingroup$

For any $n$-digit number $x$ we have $x<10^n$. Let $p_i$ be the $i$-th prime. If $x$ has $n$ digits and $n$ distinct prime factors, we have that $$p_1p_2\ldots p_n\leq x< 10^n.$$

Thus, all it takes to finish the proof is to show that $$p_1p_2\ldots p_n \geq 10^n$$ for all but finitely many positive integers $n$. Can you do that?

$\endgroup$
  • $\begingroup$ So, I lg both sides and show n < the sum of logs, therefore it has an upper bound? $\endgroup$ – Jacob Sep 17 '17 at 11:46
  • $\begingroup$ @Jacob, yes. If $n$ is large enough, $$\sum_{i=1}^n\log p_i > 0+0+0+0+1+\ldots+1+2+2+2+2+1+\ldots+1 = n.$$ $\endgroup$ – Ennar Sep 17 '17 at 11:53
  • $\begingroup$ i don't quite understand the "0+0+0+0+1+…+1+2+2+2+2+1+…+1" though.. $\endgroup$ – Jacob Sep 17 '17 at 14:05
  • $\begingroup$ @Jacob, let $p_k = 101$. Then $0<\log p_i<1$, for $ i = 1,2,3,4$, $1<\log p_i < 2$ for $i = 5,\ldots, k-1$, and $2<\log p_i$ for $i\geq k$. Thus, we have $\log p_i>1$ for all but $i = 1, 2, 3, 4$, and we make up for it with $\log p_k + \log p_{k+1} + \log p_{k+2} + \log p_{k+3} > 2 + 2 + 2 + 2$. So, "$n$ large enough" means $n\geq k + 3$. $\endgroup$ – Ennar Sep 17 '17 at 14:12
1
$\begingroup$

How about a different approach?

To make it easier, I'm going to define a number as wonderful iff the number of its decimal digits (base 10) equals the number of its distinct prime factors.

Then,

  1. Let x be some wonderful number with n digits.
  2. We know that x is wonderful, so it has n distinct prime factors.
  3. To maximize the number of distinct prime factors in x, we should have x be the multiplication of the smallest prime factors, in order of increasing numbers (i.e. x = 2*3*5*7*11 ... n primes)
  4. However, primes after 7 have at least 2 digits, so multiplying them into x will cause x to increase by at least 1 digit in length.
  5. This can keep going until after 100, where primes after 100 will cause x to increase by at least 2 digits in length, but only add 1 to the amount of distinct prime factorization of x.
  6. Clearly, this is unsustainable, and eventually the wonderful number x cannot add another unique prime factorization as it would cause x to gain more digits in length than the single distinct prime factorization would add to the number of distinct prime factors of x.
  7. If x is multiplied by a non-distinct prime factor, then eventually it will also increase in length, due to the nature of multiplication, but will not gain an extra distinct prime factorization, so x will also no longer be wonderful.
  8. At some point, x cannot be increased any further and still stay wonderful.
  9. Thus, wonderful numbers are upper bounded.
$\endgroup$

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.