Euler φの反復適用の実験数学 - 完全無欠で荒唐無稽な夢

　初等整数論で出てくるオイラーのφ関数は、１からn-1までで自然数ｎと共通約数がない数の個数を示す。φは重要な役割を整数論で担うことがより進んだ理論（有限体など）で判明する。暗号論では必須の整数論的関数だったりもする。

　ここでは実験数学での気ままなお遊びであると理解していただきたい。

　まず、φの動作確認から。

素数pなら、φ(p)=p-1となるわけであります。

φ(6)=2　なぜなら、1,5だけが6と共通約数がない。

　これを繰り返し適用したら、どうなるであろうか？

φ(φ(6))＝1 φ(φ(φ(φ(φ(72)))))＝1

というように、いくつか計算してみると最後には１になるようだ。

　巨大なメルセンヌ素数　２^17-1=131071もこうだ。

131071, 131070, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1

　この反復回数を n=1-200 までで、カウントしてみた。

　{ｎ、反復回数} のペアを示す。

　{1, 0}, {2, 1}, {3, 2}, {4, 2}, {5, 3}, {6, 2}, {7, 3}, {8, 3}, {9, 3}, {10, 3}, {11, 4}, {12, 3}, {13, 4}, {14, 3}, {15, 4}, {16, 4}, {17, 5}, {18, 3}, {19, 4}, {20, 4}, {21, 4}, {22, 4}, {23, 5}, {24, 4}, {25, 5}, {26, 4}, {27, 4}, {28, 4}, {29, 5}, {30, 4}, {31, 5}, {32, 5}, {33, 5}, {34, 5}, {35, 5}, {36, 4}, {37, 5}, {38, 4}, {39, 5}, {40, 5}, {41, 6}, {42, 4}, {43, 5}, {44, 5}, {45, 5}, {46, 5}, {47, 6}, {48, 5}, {49, 5}, {50, 5}, {51, 6}, {52, 5}, {53, 6}, {54, 4}, {55, 6}, {56, 5}, {57, 5}, {58, 5}, {59, 6}, {60, 5}, {61, 6}, {62, 5}, {63, 5}, {64, 6}, {65, 6}, {66, 5}, {67, 6}, {68, 6}, {69,6}, {70, 5}, {71, 6}, {72, 5}, {73, 6}, {74, 5}, {75, 6}, {76, 5}, {77, 6}, {78, 5}, {79, 6}, {80, 6}, {81, 5}, {82, 6}, {83, 7}, {84, 5}, {85, 7}, {86, 5}, {87, 6}, {88, 6}, {89, 7}, {90, 5}, {91, 6}, {92, 6}, {93, 6}, {94, 6}, {95, 6}, {96, 6}, {97, 7}, {98, 5}, {99, 6}, {100, 6}, {101, 7}, {102, 6}, {103, 7}, {104, 6}, {105, 6}, {106, 6}, {107, 7}, {108, 5}, {109, 6}, {110, 6}, {111, 6}, {112, 6}, {113, 7}, {114, 5}, {115, 7}, {116, 6}, {117, 6}, {118, 6}, {119, 7}, {120, 6}, {121, 7}, {122, 6}, {123, 7}, {124, 6}, {125, 7}, {126, 5}, {127, 6}, {128, 7}, {129, 6}, {130, 6}, {131, 7}, {132, 6}, {133, 6}, {134, 6}, {135, 6}, {136, 7}, {137, 8}, {138, 6}, {139, 7}, {140, 6}, {141, 7}, {142, 6}, {143, 7}, {144, 6}, {145, 7}, {146, 6}, {147, 6}, {148, 6}, {149, 7}, {150, 6}, {151, 7}, {152, 6}, {153, 7}, {154, 6}, {155, 7}, {156, 6}, {157, 7}, {158, 6}, {159, 7}, {160, 7}, {161, 7}, {162, 5}, {163, 6}, {164, 7}, {165, 7}, {166, 7}, {167, 8}, {168, 6}, {169, 7}, {170, 7}, {171, 6}, {172, 6}, {173, 7}, {174, 6}, {175, 7}, {176, 7}, {177, 7}, {178, 7}, {179, 8}, {180, 6}, {181, 7}, {182, 6}, {183, 7}, {184, 7}, {185, 7}, {186, 6}, {187, 8}, {188, 7}, {189, 6}, {190, 6}, {191, 7}, {192, 7}, {193, 8}, {194, 7}, {195, 7}, {196, 6}, {197, 7}, {198, 6}, {199, 7}, {200, 7}

　反復回数はギクシャクしながら、どれもこれも１になっている。類似の問題としてあのコラッツの問題がある。どのような自然数もある操作の反復で１になるという点で類似だ。

　こちらはコラッツの問題より素早く１になるようだ。また、コラッツの問題と異なり、１になることの証明は簡単であろう（自分にはその能力ないけど）

　オマケ特典としてn=1～1000で反復回数の推移をグラフ化しておこう。