【余り算の使い方】数字の周期性と剰余を使って複座な数式を解く方法

こんにちは。iQeda [@iQeeeda] です。

グループ分けができると、複雑な数式でもパターンで答えを導けます。
この記事を読めば、プログラミングの余り算の使い時が分かるようになりますよ。

剰余とは

割り算すると必ず「余り」が出ます。 (余り 0 を含む)
これでグループ分けを行うことができます。

余りのことは、専門用語で「剰余」と呼びます。
また、余りだけに注目した割り算を「余り算」と言ったりもします。

奇数と偶数

余り算の代表的なグループ分けに「偶数・奇数」があります。

これは知っている方も多いかと思います。

周期性と剰余

奇数・偶数以外にも「剰余によるグループ分け」は可能です。

曜日クイズ

100 日後は何曜日？

今日が日曜日の場合、100 日後は何曜日になるでしょうか？

一週間は 7 日で、7 日ごとに同じ曜日がやってきます。
つまり 7 の倍数は「日曜日」になることがわかります。

100 / 7 = 14 余り 2 と計算すると 14 回目の日曜日の 2 日後が 100 日目であり、
「日曜日」の 2 日後は「火曜日」ということが導けます。

1 億日後は何曜日？

今日が日曜日の場合、100000000 日後は何曜日になるでしょうか？

100000000 / 7 = 14285714 余り 2 なので、
これも「火曜日」ということが導けます。注目すべきは剰余の 2 です。

n 日後は何曜日？

つまり n 日後の曜日は n / 7 の剰余から「パターン」で求めることができます。
曜日は 7 を周期として繰り返しているので、こういった計算が可能なのです。

10^100 日後は何曜日？

今日が日曜日の場合、10 の 100 乗日後は何曜日になるでしょうか？

7 の周期性で考える (数の周期性)

10^100 / 7 の計算は少し大変そうです。
まず 7 の周期性を使ってみて、別の周期性もないか探してみましょう。

1 日後… 10 日後… 100 日後… 1000 日後… と、
0 の個数を徐々に増やしたときの曜日を検証してみます。

7 の周期性だと n / 7 で「1, 3, 4, 6, 2, 5」という剰余を繰り返すため、
曜日も「月, 水, 火, 土, 木, 金」を繰り返していることが分かります。

つまり 0 の数が 6 増えると、同じ曜日になっています。
このことから 6 の周期性が存在していることが分かります。

6 の周期性で考える (0 の個数の周期性)

ある値を「周期」で割れば、その剰余でグループ分けできることを思い出してください。

0 の個数 / 6 の剰余は「0, 1, 2, 3, 4, 5」のいずれかになります。
剰余に対応する曜日さえ把握していれば、0 が 100 個のときの曜日も分かります。

100 / 6 の剰余は 4 なので、剰余が 4 のときに対応する曜日を見ればよいですね。
10^100 日後の曜日は「木曜日」であることがわかります。

10^100000000 日後は何曜日？

100000000 / 6 = 16666666 余り 4 なので、
10^100000000 日後の曜日も「木曜日」であることがわかります。

0 の個数に注目すると、大きい数の取り扱いがラクになることも分かったと思います。

累乗クイズ

1234567^987654321 の一の位は？

1234567^987654321 は電卓でも計算できません。
1234567^1 とか 1234567^2 ですら大きな数字になってしまいます。

ですが、今回は一の位だけ分かればいいことにします。
なので「規則性」さえ見つかれば、もっと単純な話になります。

一の位に影響を与えるのは一の位だけ

1234567^n の計算結果で「一の位に影響を与えるのは、一の位どうしの掛け算 (累乗) 」です。
つまり一の位 7 の累乗だけを追いかけて、その計算結果の一の位に注目しましょう。

一の位は 1, 7, 9, 3 の値を繰り返しているので「周期性」は 4 といえます。
つまり指数 987654321 を 4 で割ったときの剰余を確認すればよいことになります。

987654321 / 4 = 246913580 余り 1 で剰余が 1 なので、
それに対応する一の位は 7 となります。

1234567^987654321 の一の位は 7 になる、が答えです。

「剰余を使って、大きな数の問題を小さな数の問題に落としこむ」基本的な考え方を解説しました。

CS シリーズ

次回

前回