普段何気なく使っている自然数ですが、数学で扱うためには厳密に定義する必要があります。今回はその方法をご紹介します。
以下、個人的な好みの問題ですが、自然数は$0$から始まるものとしています。
自然数の作り方
自然数は$0$（または$1$）から始まり、無限に、かつ一列に並ぶ性質を持っています。当然ですが、どこかで途切れたり、分岐したり、合流したりすることはありません。このような自然数が満たすべき性質は「ペアノの公理」というもので定められています。ペアノの公理に関しては、「高校数学の美しい物語 自然数とは（0を含むこともあるよ）」等を参考にしていただけると良いかと思います。また、「数学ガール ゲーテルの不完全性定理」の中で詳しく、かつ分かりやすく議論されています。
ところが、ペアノの公理では自然数であるための条件にしか触れていません。一応これでも問題はないのですが、これらの条件を満たすものを形式的に定義する、つまり自然数に実体を与えるアルゴリズムの一つが「ノイマンの構成法」です。エンジニアの言葉でいうと、ペアノの公理で自然数の要件定義を行い、ノイマンの構成法でコーディングするイメージでしょうか。ノイマンの構成法では、集合（{1, 2, 3}みたいなやつ）を使用して、ペアノの公理を満たすものを生成していきます。
ノイマンの構成法では$0$を最初の自然数として、自然数を次のように定義していきます。
\begin{eqnarray}
0 &:=& \{\} \\
1 &:=& \{0\} = \{\{\}\} \\
2 &:=& \{1,\ 0\} = \{\{\{\}\},\ \{\}\} \\
3 &:=& \{2,\ 1,\ 0\} = \{\{\{\{\}\},\ \{\}\},\ \{\{\}\},\ \{\}\}
\end{eqnarray}
以降は繰り返しです。
アルゴリズムの整理
ノイマンの構成法に従い、自然数を定義するアルゴリズムを作ります。ゴールは$0$以上の整数を入力すると、その定義を文字列で標準出力するプログラムを作ることです。
ノイマンの構成法では、最初に0 = {}を定義した後、既に定義済みの自然数のみを使用して再帰的に定義していきます。最終的に自然数は{、}、,の3種類の文字だけで表現されます。イメージ図を載せておきます。
あとはこれを左から1文字ずつ出力すればOKです。
実装
ソースコードはこちら。python 3.7を使用しています。
import sys
# 自然数ジェネレータ
def neumann_algorithm(target_num: int):
processing = target_num - 1
yield '{'
while processing >= -1:
# (1)
if processing == -1:
yield '}'
return 0
else:
natural_number_generator = neumann_algorithm(processing)
yield from natural_number_generator
# (2)
if processing == 0:
yield '}'
return 0
else:
yield ', '
processing -= 1
return 0
# 入力値を取得
def get_input_num():
args = sys.argv
input_num = int(args[1])
return input_num
if __name__ == "__main__":
target_num = get_input_num()
natural_number_generator = neumann_algorithm(target_num)
for char in natural_number_generator:
print(char, end='')
ソースコード解説
ソースコードのneumann_algorithm関数が自然数を生成するアルゴリズムになります。関数内部では(1)と(2)（ソースコード中のコメントを参照）の2か所で分岐が存在します。簡単に説明した図を載せておきます。
(1)はこれから出力する数値が$0$であるか否か、つまり定義済みであるか否かを判定する部分です。0 = {}は最初に定義されているので直接{}を出力できますが、その他の数は定義されていないので再起的に関数を呼び出すことが必要です。
(2)は再起処理が1個終了するごとに、次は}と,のどちらを出力するかを判定する部分です。
なお、自然数の定義は数が大きくなると爆発的に長くなります（$O(2^n)$くらい）。そのため、全体を文字列やリストに起こしてしまうとメモリが足りなくなる可能性があります。これを防ぐため、出力する文字を逐一判定し、必要なくなったら破棄できるジェネレータを使用して実装しました。実行する場合は$10$くらいで一度様子見することをお勧めします。
出力結果
$0$から$5$を入力して実行した結果がこちら。
>python natural_number_generator.py 0
{}
>python natural_number_generator.py 1
{{}}
>python natural_number_generator.py 2
{{{}}, {}}
>python natural_number_generator.py 3
{{{{}}, {}}, {{}}, {}}
>python natural_number_generator.py 4
{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}
>python natural_number_generator.py 5
{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}
>
いい感じですね。
ちなみに動かしてみて気付いたのですが、}は3回以上連続することはないみたいです。分岐の仕方をみれば明確ではあるのですが、アルゴリズムを考える段階では意識していませんでした。新たな発見がありましたね。
おまけ
$10$の定義です。
>python natural_number_generator.py 10
{{{{{{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}
>
以上です。ありがとうございました。