The Period of a Function／関数の周期性

数学に登場する多くの関数は周期的と言えます。関数の演算結果を注意深く観察してみると、ある周期で同じ数列が繰り返すことがわかります。周期とは、この数字の繰り返しがどのくらいの間隔であるかを示す言葉です。

数学的に記述すると、「もし取ることが可能な全ての(x)に対し(f(x + r) = f(x))ならば、この関数(f(x))は周期(r)で周期的である」となります。

例として、(f(x) = 3^x bmod 10)について考えてみましょう。(bmod)(モジュロ演算子)は、法（ここでは10）で数値を割ったときの余りを返します。これは、底（同様に10）に書き直された数値の最後の桁の数字を返していると言い換えることもできます。

(f(0) = 3^0 mod 10 = 1 bmod 10 = 1) (f(1) = 3^1 mod 10 = 3 bmod 10 = 3) (f(2) = 3^2 mod 10 = 9 bmod 10 = 9) (f(3) = 3^3 mod 10 = 27 bmod 10 = 7) (f(4) = 3^4 mod 10 = 81 bmod 10 = 1) (f(5) = 3^5 mod 10 = 243 bmod 10 = 3)

上の式を全体的に眺めてみると(1rightarrow 3rightarrow 9rightarrow 7rightarrow 1)と値が循環していることがわかります。すなわち(r = 4): (f(0) = f(4) = f(8) = f(12) = 1)の様に周期 4 で返される値は等しくなっています。この周期は(x)の値をどこからスタートさせても変わることはありません。例えば(x = 1)としてみましょう。(f(1) = f(5) = f(9) = 3)と同様に周期が4であることがわかります。

モジュロ演算と循環については、以下の例(f(x) = 5^x mod 7)を見てみましょう。

(f(0) = 5^0 mod 7 = 1 bmod 7 = 1)
(f(1) = 5^1 mod 7 = 5 bmod 7 = 5)
(f(2) = 5^2 mod 7 = 25 bmod 7 = 4)
(f(3) = 5^3 mod 7 = 125 bmod 7 = 6)
(f(4) = 5^4 mod 7 = 625 bmod 7 = 2)
(f(5) = 5^5 mod 7 = 3125 bmod 7 = 3)
(f(6) = 5^6 mod 7 = 15625 bmod 7 = 1)

ここで(r = 6): (1rightarrow 5rightarrow 4rightarrow 6rightarrow 2rightarrow 3 rightarrow 1)という周期になることがわかります。したがって、(f(4) = f(10) = f(16) = f(22) = 2)なります。 大抵の問題はそうですが、小規模の処理のの場合は問題なく周期を発見することができますが、これが大規模になると周期(r)を決定するのが困難になってきます。