Smith Numbers are Infinite in Number/Lemma

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\map S m$ denote the sum of the digits of a positive integer $m$.

Let $\map {S_p} m$ denote the sum of the digits of the prime decomposition of $m$.

Let $\map N m$ denote the number of digits in $m$.


Suppose $m = p_1 p_2 \dots p_r$, where $p_i$ are prime numbers, not necessarily distinct.

Then $\map {S_p} m < 9 \map N m - 0.54 r$.


Proof

Let $b_i = \map N {p_i} - 1, i = 1, 2, \dots, r$.

Let $b = b_1 + b_2 + \dots + b_r$.

Since a prime cannot be a multiple of $9$, $\map S {p_i}$ cannot be a multiple of $9$ either.

Hence:

$\map S {p_i} \le 9 \map N {p_i} - 1 = 9 b_i + 8$

We partition the $p_i$ into $9$ disjoint classes by means of the following:

Define $c_i = \map S {p_i} - 9 b_i$.

By the above, $c_i \le 8$ and $c_i \ne 0$.

Let $n_0$ be the number of $i$ such that $c_i$ is (strictly) negative, and $n_j$ be the number of $i$ such that $c_i = j$ for $1 \le j \le 8$.

Then:

\(\ds \map {S_p} m\) \(=\) \(\ds \sum_{i \mathop = 1}^r \map S {p_i}\)
\(\ds \) \(=\) \(\ds \sum_{i \mathop = 1}^r \paren {9 b_i + c_i}\)
\(\ds \) \(=\) \(\ds 9 b + \sum_{j \mathop = 1}^8 j n_j + \sum c_i\)

where the last sum is over the integers $i$ where $c_i$ is (strictly) negative.

There are $n_0$ of these integers, so we also have:

\(\ds \sum c_i\) \(\le\) \(\ds -n_0\)
\(\text {(1)}: \quad\) \(\ds \leadsto \ \ \) \(\ds \map {S_p} m\) \(\le\) \(\ds 9 b + \sum_{j \mathop = 1}^8 j n_j - n_0\)


We have $\map S {p_i} = 9 b_i + c_i$.

For $c_i < 0$ we will use the inequality:

$p_i > 10^{\map N {p_i} - 1} = 10^{b_i}$

For $1 \le c_i \le 8$ we would have:

$p_i \ge \paren {c_i + 1} \times 10^{b_i} - 1$

since this number on the right is the smallest integer $N$ with $\map S N = 9 b_i + c_i$.

We also have:

$\paren {c_i + 1} \times 10^{b_i} - 1 = \paren {c_i + 0.9} \times 10^{b_i} + 10^{b_i - 1} - 1 \ge \paren {c_i + 0.9} \times 10^{b_i}$

for $b_i > 0$ (i.e. when $p_i \ne 2, 3, 5, 7$).

Finally for $b_i = 0$, we have:

$p_i = \map S {p_i} = c_i = c_i 10^{b_i}$


It follows that:

\(\ds m\) \(=\) \(\ds p_1 p_2 \dots p_r\)
\(\ds \) \(\ge\) \(\ds \paren {1.9}^{n_1} \paren 2^{n_2} \paren 3^{n_3} \paren {4.9}^{n_4} \paren 5^{n_5} \paren {6.9}^{n_6} \paren 7^{n_7} \paren {8.9}^{n_8} \times 10^b\)

Write $m = a \times 10^{\map N m - 1}$ where $1 \le a < 10$.

By taking logarithm (base $10$) on both sides, we get:

\(\ds \log a + \map N m - 1\) \(\ge\) \(\ds n_1 \log 1.9 + n_2 \log 2 + \dots + n_8 \log 8.9 + b\)
\(\ds \leadsto \ \ \) \(\ds 9 \map N m\) \(\ge\) \(\ds 9 b + n_1 \paren {9 \log 1.9} + n_2 \paren {9 \log 2} + \dots + n_8 \paren {9 \log 8.9}\)
\(\ds \) \(\ge\) \(\ds 9 b + n_1 \paren {1 + 0.54} + n_2 \paren {2 + 0.54} + \dots + n_8 \paren {8 + 0.54}\) by manual checking
\(\ds \) \(=\) \(\ds 9 b + \sum_{j \mathop = 1}^8 j n_j + 0.54 \paren {n_1 + n_2 + \dots + n_8}\)
\(\text {(2)}: \quad\) \(\ds \leadsto \ \ \) \(\ds 9 b + \sum_{j \mathop = 1}^8 j n_j\) \(\le\) \(\ds 9 \map N m - 0.54 \paren {n_1 + n_2 + \dots + n_8}\)

Combining $(1)$ and $(2)$, we have:

\(\ds \map {S_p} m\) \(\le\) \(\ds 9 b + \sum_{j \mathop = 1}^8 j n_j - n_0\) from $(1)$
\(\ds \) \(\le\) \(\ds 9 \map N m - 0.54 \paren {n_0 + n_1 + \dots + n_8} - 0.46 n_0\) from $(2)$
\(\ds \) \(\le\) \(\ds 9 \map N m - 0.54 r\)

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Smith_Numbers_are_Infinite_in_Number/Lemma&oldid=580677"