こんにちは。iQeda [@iQeeeda] です。
今回は剰余を使ったグループ分けについて解説します。
なんらかの数字の法則性を発見できると、剰余でなんでもグループ分けが可能です！
グループ分けができると、複雑な数式でもパターンで答えを導けます。
この記事を読めば、プログラミングの余り算の使い時が分かるようになりますよ。
剰余とは
割り算すると必ず「余り」が出ます。 (余り 0 を含む)
これでグループ分けを行うことができます。
余りのことは、専門用語で「剰余」と呼びます。
また、余りだけに注目した割り算を「余り算」と言ったりもします。
奇数と偶数
余り算の代表的なグループ分けに「偶数・奇数」があります。
- 奇数とは
- 2 で割ると余りが 1 になる整数のこと
- 偶数とは
- 2 で割ると余りが 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 の個数を徐々に増やしたときの曜日を検証してみます。
| 0 の個数 | n 日後 | n / 7 | 曜日 |
|---|---|---|---|
| 0個 | 1 (10^0) | 1/7 = 0 余り 1 | 月 |
| 1個 | 10 (10^1) | 10/7 = 1 余り 3 | 水 |
| 2個 | 100 (10^2) | 100/7 = 14 余り 2 | 火 |
| 3個 | 1000 (10^3) | 1000/7 = 142 余り 6 | 土 |
| 4個 | 10000 (10^4) | 10000/7 = 1428 余り 4 | 木 |
| 5個 | 100000 (10^5) | 100000/7 = 14285 余り 5 | 金 |
| 6個 | 1000000 (10^6) | 1000000/7 = 142857 余り 1 | 月 |
| 7個 | 10000000 (10^7) | 10000000/7 = 1428571 余り 3 | 水 |
| 8個 | 100000000 (10^8) | 100000000/7 = 14285714 余り 2 | 火 |
| 9個 | 1000000000 (10^9) | 1000000000/7 = 142857142 余り 6 | 土 |
| 10個 | 10000000000 (10^10) | 10000000000/7 = 1428571428 余り 4 | 木 |
| 11個 | 100000000000 (10^11) | 100000000000/7 = 14285714285 余り 5 | 金 |
| 12個 | 1000000000000 (10^12) | 1000000000000/7 = 142857142857 余り 1 | 月 |
7 の周期性だと n / 7 で「1, 3, 4, 6, 2, 5」という剰余を繰り返すため、
曜日も「月, 水, 火, 土, 木, 金」を繰り返していることが分かります。
つまり 0 の数が 6 増えると、同じ曜日になっています。
このことから 6 の周期性が存在していることが分かります。
6 の周期性で考える (0 の個数の周期性)
ある値を「周期」で割れば、その剰余でグループ分けできることを思い出してください。
0 の個数 / 6 の剰余は「0, 1, 2, 3, 4, 5」のいずれかになります。
剰余に対応する曜日さえ把握していれば、0 が 100 個のときの曜日も分かります。
| 0 の個数 | 0 の個数 / 6 | 曜日 |
|---|---|---|
| 0個 | 0 / 6 = 0 余り 0 | 月 |
| 1個 | 1 / 6 = 0 余り 1 | 水 |
| 2個 | 2 / 6 = 0 余り 2 | 火 |
| 3個 | 3 / 6 = 0 余り 3 | 土 |
| 4個 | 4 / 6 = 0 余り 4 | 木 |
| 5個 | 5 / 6 = 0 余り 5 | 金 |
| 6個 | 6 / 6 = 1 余り 0 | 月 |
| 7個 | 7 / 6 = 1 余り 1 | 水 |
| 8個 | 8 / 6 = 1 余り 2 | 火 |
| 9個 | 9 / 6 = 1 余り 3 | 土 |
| 10個 | 10 / 6 = 1 余り 4 | 木 |
| 11個 | 11 / 6 = 1 余り 5 | 金 |
| 12個 | 12 / 6 = 1 余り 0 | 月 |
| … | … | … |
| 100個 | 100 / 6 = 16 余り 4 | 木 |
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 の累乗だけを追いかけて、その計算結果の一の位に注目しましょう。
| 7^n | 7^n の一の位 | 0 の個数 / 4 | 備考 |
|---|---|---|---|
|
| 1 | 0 / 4 = 0 余り 0 | ※ |
|
| 7 | 1 / 4 = 0 余り 1 | ※ |
|
| 9 | 2 / 4 = 0 余り 2 | ※ |
|
| 3 | 3 / 4 = 0 余り 3 | ※ |
|
| 1 | 4 / 4 = 1 余り 0 | ※ |
|
| 7 | 5 / 4 = 1 余り 1 | ※ |
|
| 9 | 6 / 4 = 1 余り 2 | ※ |
|
| 3 | 7 / 4 = 1 余り 3 | ※ |
|
| 1 | 8 / 4 = 2 余り 0 | ※ |
|
| 7 | 9 / 4 = 2 余り 1 | ※ |
一の位は 1, 7, 9, 3 の値を繰り返しているので「周期性」は 4 といえます。
つまり指数 987654321 を 4 で割ったときの剰余を確認すればよいことになります。
987654321 / 4 = 246913580 余り 1 で剰余が 1 なので、
それに対応する一の位は 7 となります。
1234567^987654321 の一の位は 7 になる、が答えです。
「剰余を使って、大きな数の問題を小さな数の問題に落としこむ」基本的な考え方を解説しました。
No comments yet