Smith Numbers are Infinite in Number

From ProofWiki
Jump to navigation Jump to search

Theorem

There are infinitely many Smith numbers.


Lemma

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$.


Algorithm

They can be generated from a $9$-repdigit as follows:

$(1): \quad$ Choose any $n \ge 2$ and factor the $9$-repdigit $m = 10^n - 1$.
$(2): \quad$ Compute $\map {S_p} m$ and set $h = 9 n - \map {S_p} m$.
$(3): \quad$ Solve $x = h - 7 b$ for $b, x \in \Z$, $2 \le x \le 8$.
$(4): \quad$ Find $t \in \set {2, 3, 4, 5, 8, 7, 15}$ such that $\map {S_p} t = x$.
$(5): \quad$ Then $M = t m \times 10^b$ is a Smith number.


Proof

First we prove the the algorithm above does generate Smith numbers.

Let $n \ge 2$.

We have:

$m = 10^n - 1 = 3 \times 3 \times R_n$

where $R_n$ is the repunit with $n$ digits.

We apply the Lemma, taking note that $r \ge 3$:

$\map {S_p} m < 9 \map N m - 0.54 \times 3 = 9 n - 1.62$

Since both $\map {S_p} m$ and $9 n$ are integers, the inequality can be rewritten as:

$h = 9 n - \map {S_p} m \ge 2$


By the Division Algorithm:

$\exists! a, b \in \Z: \paren {h - 2} = 7 b + a, 0 \le a < 7$

Since $h - 2 \ge 0$, we must also have $b \ge 0$.

Take $x = a + 2$.

Then $2 \le x \le 8$ and:

$h - 7 b = a + 2 = x$

Hence both $b, x$ exist and are within the desired range.


Note that:

$\map {S_p} {\set {2, 3, 4, 5, 8, 7, 15} } = \set {2, 3, 4, 5, 6, 7, 8}$

so we can the corresponding value of $t \in \set {2, 3, 4, 5, 8, 7, 15}$ for each $2 \le x \le 8$ such that $\map {S_p} t = x$.


Since $b \ge 0$, $M = t m \times 10^b$ is an integer.

To show that $M$ is a Smith number, we need to show:

$\map {S_p} M = \map S M$

We have:

\(\ds \map {S_p} M\) \(=\) \(\ds \map {S_p} t + \map {S_p} m + \map {S_p} {2^b \times 5^b}\)
\(\ds \) \(=\) \(\ds x + \paren {9 n - h} + 7 b\)
\(\ds \) \(=\) \(\ds 9 n\)

Note that:

$t \le 15 < 99 = 10^2 - 1 \le 10^n - 1 = m$

Hence we can apply Generalization of Multiple of Repdigit Base minus $1$:

\(\ds \map S M\) \(=\) \(\ds \map S {t m \times 10^b}\)
\(\ds \) \(=\) \(\ds \map S {\sqbrk {\paren {t - 1} \paren {10^n - t} } \times 10^b}\) Generalization of Multiple of Repdigit Base minus $1$
\(\ds \) \(=\) \(\ds \map S {\sqbrk {\paren {t - 1} \paren {m - \paren {t - 1} } } }\) $10^b$ only adds trailing zeros
\(\ds \) \(=\) \(\ds \map S m\) no carries occur in the subtraction $m - \paren {t - 1}$
\(\ds \) \(=\) \(\ds 9 n\)


This article, or a section of it, needs explaining.
In particular: Explanation of the meaning of the square brackets
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Explain}} from the code.


and thus $\map {S_p} M = \map S M = 9 n$, showing that $M$ is indeed a Smith number.

$\Box$


Note that for each $n$, we can generate a Smith number that is greater than $m = 10^n - 1$.

To generate an infinite sequence of Smith numbers, we choose $n$ equal to the number of digits of $M$ previously generated.

Then the next Smith number will be strictly greater than the previous one, thus forming a strictly increasing infinite sequence of Smith numbers.

$\blacksquare$


Sources

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