キース数

こんにちは｜こんばんは。カエルのアイコンで活動しております @kyamaz :frog: です。

## はじめに
数学の専門家ばかりではなく、:frog: のような数学好きな人であればすぐに取り組めて、その魅力を堪能できる数学のことを「娯楽数学」といいます。パズルやゲームなどで楽しむもので数独などは最もポピュラーな娯楽数学の１つではないでしょうか。以前のエントリ『[ヴァンパイア数](https://qiita.com/kyamaz/items/3e13559ed016423b23ee)』のなかで紹介した「make10（メイクテン）」[^make10]もその遊びの１つでした。

本稿では、娯楽数学とされる『キース数』について取り上げます。

## キース数

キース数は、1978年にアメリカの数学者[マイケル・キース（Michael Keith）](https://en.wikipedia.org/wiki/Mike_Keith_(mathematician))によって初めて考案された数で、自己再現的な性質を利用して定義される数です。桁ごとに分割した数を使って生成される数列が元の数と一致する次の条件を満たす数です。

:::note info
<dl><dt>キース数の定義</dt>
<dd>ある $n$ 桁の自然数 $N$ から作られる次の数列が成り立つ数 $N$ をキース数とします。

1. $N$ の各桁を初期値として順に並べた数列を作ります
2. この数列の次の項は、直前の $n$ 項の合計とします（この数列の第 $k$ 項は、直前の $n$ 項の数の合計）
$ S_{k} = S_{k-1} + S_{k-2} + \cdots + S_{k-n} $
3. この規則に従って数列を延長していき、数列の中に元の数 $N$ が現れた場合にキース数とします
（数列が $N$ を超えた場合は、以降の項に $N$ が現れることはないので打ち切ります）
</dd></dl>
:::

具体的には、次のような手順で数列が生成されます。

### キース数の例

例えば、$N=197$ がキース数であるかどうかを調べます。
$ 197 $ は $3$ 桁なので、数列の初期値は $[1,9,7]$ です。

初期値：$1, 9, 7$
その次の項：$1 + 9 + 7 = 17$
その次の項：$9 + 7 + 17 = 33$
その次の項：$7 + 17 + 33 = 57$
その次の項：$17 + 33 + 57 = 107$
その次の項：$33 + 57 + 107 = 197$（ここで元の数 $197$ が出現）

このように、数列の中に元の数 $197$ が現れるため、$197$ はキース数です。

キース数は少ないため、数が大きくなると発見が難しくなります。桁数が増えると必要な計算量も増え、より複雑な数列が構成されるため、探索が大変になります。
下記の Wolfram MathWorld には、34桁までのキース数が列挙されております（また、オンライン整数列大辞典の数列 [A007629](https://oeis.org/A007629) も参照のこと）

https://mathworld.wolfram.com/KeithNumber.html

### キース数の未解決問題

* キース数は無限に存在するかどうかは分かっておらず、未解決問題です。今のところ有限の範囲でしか確認されていません。
* キース数は桁数が増えると稀になる傾向はありますが、どのように分布するのかは不明です。


### キース数を求めるプログラム

キース数を求めるプログラムをHaskellで実装してみましょう。

```haskell: キース数の判定 isKeith
digitRev x | x == 0 = [] | otherwise = d : digitRev r where (r,d) = quotRem x 10
isKeith n = keith (length ds) ds where ds = digitRev n; keith l d | n == s = True | s > n = False | otherwise = keith l (take l (s:d)) where s = sum d
```

このキース数を判定する関数を用いて、10 〜 50,000,000 まで調べてみると次のようになります。

```haskell:
ghci> filter isKeith [10..50_000_000]
[14,19,28,47,61,75,197,742,1104,1537,2208,2580,3684,4788,7385,7647,7909,31331,34285,34348,55604,62662,86935,93993,120284,129106,147640,156146,174680,183186,298320,355419,694280,925993,1084051,7913837,11436171,33445755,44121607]
```

## マイケル・キース

マイケル・キース氏はアメリカの数学者であり、ソフトウェアエンジニアです。1980年から1990年までサーノフ社、1990年から1998年までインテル社に勤務し、両社においてマルチメディアソフトウェアに従事しました。キース数のほかに、原始数（Primeval number）を提案しました。

### 原始数（Primeval number）
原始数とは、自然数 $N$ の一部または全部を並べ替えることで得られる素数の個数が、その数より小さい自然数に対して、同じ方法で得られた素数の個数よりも多い数を『原始数』と呼びます。この原始数も、娯楽数学といえます。

例えば、$1379$ はこの中の数字を並べ替えると、次の $31$ 個の素数があります。
$3, 7, 13, 17, 19, 31, 37, 71, 73, 79,$
$97, 137, 139, 173, 179, 193, 197, 317, 379, 397,$
$719, 739, 937, 971, 1973, 3719, 3917, 7193, 9137, 9173,$
$9371$

それより前の自然数では、$1367$ が $26$ 個の素数を作れるため、それまでの数のなかでは最も多く、$1379$ で生成できる素数の個数がそれより多くなるため $1379$ は『原始数』となります。
原始数は、素数であるものだけではなく、合成数もあります。（オンライン整数列大辞典の数列：原始数→[A072857](https://oeis.org/A072857)、原始数に対する素数の個数列→[A076497](https://oeis.org/A076497) 、素数の原始数の数列：[A119535](https://oeis.org/A119535)）
次表は、100,000 未満の原始数のリストです。

| 原始数 | 含まれる素数の個数 |
|-:|-:|
| 2 | 1 |
| 13 | 3 |
| 37 | 4 |
| 107 | 5 |
| 113 | 7 |
| 137 | 11 |
| 1013 | 14 |
| 1037 | 19 |
| 1079 | 21 |
| 1237 | 26	|	
| 1367 | 29 |
| 1379 | 31 |
| 10079 | 33 |
| 10123 | 35 |
| 10136 | 41 |
| 10139 | 53 |
| 10237 | 55 |
| 10279 | 60 |
| 10367 | 64 |
| 10379 | 89 |
| 12379 | 96 |
| 13679 | 106 |

## おわりに
いかがでしたでしょうか。娯楽数学が学問の発展に如何に役立つかはわかりませんが、キース氏のようなソフトウェアエンジニアであり、数学者である存在は数学好きにはありがたい存在です。

最後に、本稿を記載するために検証したHaskell環境を記しておきます。お手元の環境で検証する際に、動作が異なるときには参考になるかもしれません。

<details><summary>本稿の環境</summary>

本稿のために使用した環境は以下となります。

* macOS: Sonoma 14.6.1 (chip: Apple M1)
* GHCup: 0.1.30.0
* GHC: 9.6.6

</details>

ご一読いただきまして有り難うございます。
（●）（●） Happy Hacking!
/""　＿＿""＼



[^make10]: [make10（テンパズル）](https://ja.wikipedia.org/wiki/%E3%83%86%E3%83%B3%E3%83%91%E3%82%BA%E3%83%AB)は「0を含まない、互いに相異なる4つの数の場合は必ず解ける」ということが知られています。また、次のような例（重複も許す）が比較的難しいとされています。 $$\begin{flalign}
1158 &= 8 \div (1 - 1 \div 5) &\\\\
1199 &= (1 + 1 \div 9) \times 9 \\\\
1337 &= (1 + 7 \div 3) \times 3 \\\\
3466 &= (4 \times 6 + 6) \div 3 \\\\
3478 &= (3 - 7 \div 4) \times 8 \\\\
4669 &= (6 + 9) \times 4 \div 6 \\\\
6699 &= (6 + 9) \times 6 \div 9 \\\\
6788 &= (8 \times 8 + 6) \div 7 \\\\
9999 &= (9 \times 9 + 9) \div 9 \\\\
\end{flalign}$$