A lot of mathematical functions are periodic. That is, if you start in some place and move forward, eventually the sequence of values repeats itself. The time it takes for that repetition to occur is called the period.

Written in mathematical terms, we can say that a function (f(x)) is periodic with period (r) if

[f(x + r) = f(x)]

for all of the possible values of (x).

For example, consider (f(x) = 3^x bmod 10), where (bmod) is the modulo operator. The modulo operator gives you the remainder when you divide the two numbers, or equivalently, the last digit of the number rewritten in that base (here, ten):

(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)

We can see the cycle (1rightarrow 3rightarrow 9rightarrow 7rightarrow 1), so the period (r = 4): (f(0) = f(4) = f(8) = f(12) = 1). This period does not change depending on where you start; we can see that the period is still four if we look at (f(1) = f(5) = f(9) = 3).

To be clear about the modulo arithmetic as well as the cycle, let us look at a second example, (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)

We can see a period of (r = 6): (1rightarrow 5rightarrow 4rightarrow 6rightarrow 2rightarrow 3 rightarrow 1). Thus, (f(4) = f(10) = f(16) = f(22) = 2).

As with many problems we are discussing, these examples are not hard when the problem size is small, but as the problem size grows, the difficulty of determining that period (r) increases quickly.

関数の周期性

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

数学的に記述すると、「もし取ることが可能な全ての(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)を決定するのが困難になってきます。