3
$\begingroup$

Multiply all the digits of a number $n$ by each other, repeating with the product until a single digit is obtained. The number of steps required is known as the multiplicative persistence of $n$.

According to http://mathworld.wolfram.com/MultiplicativePersistence.html, it was shown by Erdos that:

Ignoring all zeros, at most $c\ln(\ln n)$ steps are needed to reduce $n$ to a single digit, where $c$ depends on the base.

Where can I find a proof of this result?

$\endgroup$
2
$\begingroup$

Let the base be $B$. Suppose that you start with a number $n$ which has $d$ digits, so $n \geq B^d$. After you apply your operation, you get at most $(B-1)^d \leq n^\alpha$ for some $\alpha < 1$ (in fact, $\alpha = \log_B (B-1)$).

Form now a sequence $n_0 = n, n_1, \dots$, where $n_{i+1}$ is obtained from $n_i$ through the operation. We have seen that $\log_B n_{i+1} \leq \alpha \log_B n_i$, and so $\log_B n_t \leq \alpha^t \log_B n$. The process stops when $\log_B n_t < 1$, which happens when $\alpha^t < 1/(\log_B n)$. Taking another logarithm, we get the bound $t < \log_{1/\alpha} \log_B n$.

$\endgroup$
  • $\begingroup$ oops didn't realize it was that simple. math at 2 in the morning is a bad idea. $\endgroup$ – Joshua Benabou Apr 20 '15 at 6:15

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.