SNNN数の倍数になるSNNN数の存在証明
================================

**Edit (2024/03/29)**: 界隈でスタンダードな記法からずれていることなどがあり, 本記事の内容は参考程度のものになっています 今後は https://scrapbox.io/SNNN/ に集約したい所存

前提: $0\in\mathbb{N}$.

> **Def**.
> 1. $f(x) := 10x + 7$.
> 2. $S_0 := 3$, $S_{n + 1} := f(S_n)$. $S_n$をn番目のSNNN数と呼ぶ.
> 3. $R(n) := \sum_{i = 1}^n 10^{n - 1}$. 即ち$R(n)$はn桁のrepunitを表す. なお, $n = 0$の場合は空和と見做し$R(n) := 0$とする.

記法として自然数nに対し$f^n(x) := (f\circ f\circ ...\text{(n回の合成)}...\circ f)(x)$とする. $n = 0$の場合は恒等写像と定義する. 基本的な事実を以下にまとめて示す.

> **Prop. 1**. $n, m \in \mathbb{N}$について$n \lt m$であるとき, 次が成立.
>
> 1. $S_m = f^m(3)$.
> 2. $S_m = f^{m - n}(S_n)$.
> 3. $10R(m) + 1 = R(m + 1)$.
> 4. $f^m(x) = 10^mx + 7R(m)$.
> 5. $R(m) = (10^m - 1) / 9$.

**Proof**.

1. 定義より明白.
2. 定義より$S_n = f^n(3)$であるから$S_m = f^m(3) = (f^{m-n}\circ f^n))(3) = f^{m - n}(f^n(3)) = f^{m - n}(S_n)$.
3. $$
\begin{aligned}
R(m + 1) &= \sum_{i = 1}^{m + 1} 10^{m - 1}\cr
&= \sum_{i = 2}^{m + 1} 10^{m - 1} + 1\cr
&= 10 \left(\sum_{i = 1}^m 10^{m - 1}\right) + 1\cr
&= 10 R(m) + 1.
\end{aligned}
$$
1.
* $m = 0$のとき: $f^0$は恒等写像だから$10^0x + 7 R(0) = 1x + 0 = x = f^0(x)$.
* $m = k - 1$で成立と仮定, $m = k$のとき:
$$
\begin{aligned}
f^k(x) &= f(10^{k - 1}x + 7 R(k - 1))\cr
&= 10^kx + 7 (R(k - 1) 10 + 1)\cr
&= 10^kx + 7 R(k). &(\because\text{Prop. 1 (3.)})
\end{aligned}
$$
* 数学的帰納法により任意の自然数$m$に対し成立.
5.
* $m = 0$のとき: $(10^0 - 1) / 9 = 0 = R(0)$.
* $m = k - 1$で成立と仮定, $m = k$のとき:
$$
\begin{aligned}
R(k) &= 10 R(k - 1) + 1 & (\because \text{Prop. 1 (3.)})\cr
&= 10 (10^{k - 1} - 1) / 9 + 1\cr
&= (10^k - 10) / 9 + 1\cr
&= (10^k - 1) / 9 - 9 / 9 + 1\cr
&= (10^k - 1) / 9.
\end{aligned}
$$
* 数学的帰納法により任意の自然数$m$に対し成立. $\Box$

> **Cor. 2**. $\forall m\in \mathbb{N}. S_m = 3\cdot 10^m + 7R(m)$.

**Proof**. Prop. 1 (4.)より成立. $\Box$

> **Lem. 3**. $\forall n, m \in\mathbb{N}$. $n \lt m$. このとき$S_n \mid S_m$であるための必要十分条件は$7 R(m − n) / S_n \in \mathbb{N}$である.

**Proof**.

* (**必要性**): ある$k \in \mathbb{N}$が存在して$S_m = kS_n$. すると

$$
\begin{aligned}
S_m = kS_n &\iff f^{m - n}(S_n) = kS_n & (\because\text{Prop. 1 (2.)})\cr
&\iff 10^{m - n}S_n + 7 R(m - n) = kS_n &(\because\text{Prop. 1 (4.)})\cr
&\iff 10^{m - n} + 7R(m - n) / S_n = k\cr
&\iff 7R(m - n) / S_n = k - 10^{m - n}
\end{aligned}
$$

である. $k, 10^{m - n}$はそれぞれ自然数だからその差は整数であり, したがって左辺$7R(m - n) / S_n$も整数である. とくに, 左辺は0より真に大きいため, 自然数である.
* (**十分性**): $k := 10^{m - n} + 7R(m - n) / S_n$とおく. このとき
$$
\begin{aligned}
kS_n &= S_n(10^{m - n} + 7R(m - n) / S_n)\cr
&= 10^{m - n}S_n + 7R(m - n)\cr
&= f^{m - n}(S_n)\cr
&= S_m\cr
\end{aligned}
$$
であるから成立. $\Box$

> **Lem. 4**. $\forall x \in \mathbb{N}$. $\exists m \in \mathbb{N}$. $x \mid R(m)$.

**Proof**. $k := \varphi(9x)$とおく. ただし$\varphi$はEuler totient. すると$10^k \equiv 1 \pmod{9x}$である. このとき$\exists t \in \mathbb{N}$. $10^k - 1 = 9tx$なのでProp. 1 (5.)より$tx = (10^k - 1) / 9 = R(k)$. したがって$x \mid R(k)$. $\Box$

> **Thm. 5**. $\forall n \in \mathbb{N}$. $\exists k, m \in \mathbb{N}$. $k \ne 1 \land S_m = k S_n$.

**Proof**

* (**$k, m$の存在**): Lem. 4よりある$t \in \mathbb{N}$が存在して$S_n\mid R(t)$をみたす. $m := n + t$とおくと, $7 R(m - n) = 7 R(n + t - n) = 7 R(t)$は$S_n$を約数にもつ. Lem. 3より$S_n \mid S_m$であり, これゆえある$k$が存在して$S_m = k S_n$.
* ($k\ne 1$): Cor. 2より$S_m = 3\cdot 10^m + 7R(m)$かつ$R(m)\gt R(m - n) = R(t)$である. $S_n\mid R(t)$より$S_n\leq R(t)\lt R(m)$. ゆえに$S_n\lt 3\cdot 10^m + S_n\lt 3\cdot 10^m + 7R(m) = S_m$であり, $1 \ne k$が帰結する. $\Box$

---

おまけ: Pari/GPスクリプト ( http://pari.math.u-bordeaux.fr/gpwasm.html で試せる)

repunit(n) = (10^n - 1) / 9
Sn(n) = 3 * 10^n + 7 * repunit(n)
multiple_m(n) = {
  \\ Thm. 5
  x = Sn(n);
  t = eulerphi(9 * x);
  return(n + t);
}

nn = 40
m = multiple_m(nn)
print([nn, m]) \\ [S_n, S_m]

\\ しばしばmは巨大になるので, 計算段階からModを取って判定する
\\ gcd(9, S_n) = 1を仮定しなくてもいいように9倍したものだけ計算する簡易検証コード
sn = Sn(nn)

\\ 9 * S_m ≡ 0 (mod S_n)を展開しただけ
print(27 * Mod(10, sn)^m + 7 * (Mod(10, sn)^m - 1) == 0) \\ 1

\\ gcd(9, S_n) = 1の場合は厳密に計算できる
\\ gcd(9, S_n) ≠ 1の場合は個別検証することになるが, まあ位数9の元に関する議論だしO(1)で検証できます
\\ S_m ≡ 0 (mod S_n)を展開しただけ
\\ print(3 * Mod(10, sn)^m + 7/9 * (Mod(10, sn)^m - 1) == 0) \\ 1