オイラーの関数の反復プロセス

　自然数ｎ　と素な数のn以下の数の個数をφ(n)と表し、オイラー関数という。数論関数のひとつだ。
定義より、ｐが素数であるなら、φ(p)=p-1 である。

　これを反復的に同じ数に適用してみよう。そのココロはφ(φ(φ(．．．)))という入れ子を収束するまで行うことである。
n=5であれば、{5, 4, 2, 1}となる。3回で１になる。n=97であれば、{97, 96, 32, 16, 8, 4, 2, 1}である。7回だ。
　証明は難しくないであろうが、オイラー関数の反復は必ず「１」になる。

では、何回反復すれば「１」となるのであろうか？
もはや大量数値計算で一挙に自然数に適用してみよう。横軸は自然数で縦軸は「１」になるまでの反復回数である。

横軸の自然数を増やしてみる。

素数だけ選ぶとどうなるだろうか？２０００未満の素数で計算してみよう。

ただの自然数よりは反復回数は増大している。また、なんとなしに階段状で増加しているようだ。

この両方を併記してみる。茶色が自然数、青が素数のみ。当然ながら、上限は一致する。時折、素数なみに
上限値になる数があるのが注目される。これらの非素数は何か特徴があるかもしれない。

　面白い現象をひとつ指摘しておく。９７では{97, 96, 32, 16, 8, 4, 2, 1}となった。つまり、2^k+1のかたちの素数であれば、
ｋ回で収束する。フェルマー素数はｋ回程度で収束するわけである。

オイラー関数は初等数論で絶大な威力を発揮する、かなり性質のよく知られている関数だ。
だからといってすべての事実がくまなく判明しているわけではない。
何が読み取れたわけでもないのだが、これも数の不思議の探求のひとつではないだろうか？

数論入門―証明を理解しながら学べる (ブルーバックス)