7の倍数の判定式を考えるプロセス
「7の倍数」でググると、いくつかの判定法が出てきます:
昔自分が考え付いたときの方法は、単純に、二桁目と三桁目以上と一桁目をわけて、数列をだしてそこから法則をみつけたものでした。以下の表は、7で割り切れる数の一桁目をa、二桁目をb、三桁目以上をcとしたときのaの最小の値の表です:
| c＼b | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 4 | 1 | 5 | 2 | 6 | 3 | 0 | 4 | 1 |
| 1 | 5 | 2 | 6 | 3 | 0 | 4 | 1 | 5 | 2 | 6 |
| 2 | 3 | 0 | 4 | .. | .. | .. | .. | .. | .. | .. |
| 3 | 1 | 5 | 2 | .. | ||||||
| 4 | 6 | 3 | 0 | .. | ||||||
| 5 | 4 | 1 | 5 | .. | ||||||
| 6 | 2 | 6 | 3 | .. | ||||||
| 7 | 0 | 4 | 1 | .. | ||||||
| 8 | 5 | 2 | 6 | .. | ||||||
| 9 | 3 | 0 | 4 | .. | ||||||
| 10 | 1 | 5 | 2 | .. | ||||||
| .. | .. | .. | .. | .. |
こうしてみるとすぐ気がつきます。aは、bが1増えると3づつへっていき、cが1増えると2づつ減っていくのがわかります(0..6で循環するとして)。つまり、aと3b+2cの関係が一定になるわけです。
こここからごにょごにょ考えると、7の倍数は「a + 3b + 2cが7で割り切れる」、という関係が見つかりました。この式自体も7で割り切れることを判定するためのものなので、再帰的に適用すれば最終的に1桁に収まるわけだったりします。
この判定式をrubyでかくと
def seven?(n) return n % 7 == 0 if n < 10 a = n % 10 b = (n / 10) % 10 c = n / 100 seven?(a + 3 * b + 2 * c) end
チェック例のコード:
(0...100000).map{|i| seven?(i*7)}.all?
(0...100000).map{|i| if seven?(i) and i % 7 != 0 then false else true end}.all?
上は、7の倍数が判定式を満たすか、下は、7の倍数以外で判定式を満たすものがないか、をチェックしてます。
ただ、人間がふつうに考えるなら九九の7の段と70, 77, 84, 91, 98はすぐ区別がつくはずなので、「3桁目以降を二倍して、下二桁と足し合わせたもの、が7で割り切れるか」を繰り返す、つまり
def seven?(n) return n % 7 == 0 if n < 100 seven?(2 * (n / 100) + (n % 100)) end
で十分だったりするんですけれど。
おまけ: 証明
命題:
- 1) a + 10*b + 100*cが7の倍数なら、a + 3*b + 2*cは7の倍数である、かつ、
- 2) a + 10*b + 100*cが7の倍数でないなら、a + 3*b + 2*cは7の倍数でない
1) a + 10*b + 100*cが7の倍数
- → a + 10*b + 100*c = 7*x (xは整数)
- → a = 7*x - 10*b - 100*c
- → (これをa + 3*b + 2*cのaに代入)
- → (7*x - 10*b - 100*c) + 3*b + 2*c
- → = 7*x - 7*b - 98*c
- → = 7* (x - b - 14*c)
- → x, b, cが整数であるので、(x - b - 14*c)も整数である
- → よってa + 3*b + 2*c は7の倍数
(2の証明は対偶でも背理法でも可能。)
2a) 対偶: a + 3*b + 2*cは7の倍数なら、a + 10*b + 100*cが7の倍数である
- ほぼ1と同じやり方で証明成立
2b) 背理法: a + 10*b + 100*cは7の倍数でないとき、a + 3*b + 2*cが7の倍数である、が矛盾する
- → a + 10*b + 100*c = 7*x + r (x,rは整数、rは7の倍数ではない)
- → a + 3*b + 2*c = 7*y (yは整数)
- → (上の等式 - 下の等式)
- → 7*b + 98*c = 7*x - 7*y + r
- → 7*b + 98*c - 7*x + 7*y = r
- → 7 * (b + 14*c - x + y) = r
- → b,c,x,yは整数なので、(b + 14*c - x + y)は整数
- → よってrは7の倍数
- → 仮定(rは7の倍数ではない)と矛盾するので 2が成立
引いたとき、割るための数でくくれる式になるような式を作ればいいので、7以外の数にも応用できますね(有用性はないだろうけど):
- 2 => a % 2 == 0
- 3 => (a + b + c) % 3 == 0
- 4 => (a + 2b) % 4 == 0
- 5 => a % 5 == 0
- 6 => (a + 4b + 4c) % 6 == 0
- 7 => (a + 3b + 2c) % 7 == 0
- 8 => (a + 2b + 4c) % 8 == 0
- 9 => (a + b + c) % 9 == 0
追記: (b - 2*a) % 7 == 0なら(a+10*b) は7の倍数
検索で一番上に出てくるページ
では、一桁目を二倍して、それ以上から引いたものが7で割り切れると7の倍数という判定方法を使ってます。引き算が得意ならこちらもよいかもしれません。
これは
- - 2*a + b
でありa + 10*b = 7*x とおくと、この式は21*b-14*xとなって7で割り切れ(1)、-2*a+b=7yとおくと、a + 10*bは、21*a+70yとなって7で割り切れるため(2a)正しい判定式と証明できます。
ちなみに、命題の(1)は満たすけど、(2)が満たさない例として、4の倍数の判定式としての、一桁目の二倍が4の倍数（2*a % 4 == 0）かどうか、があります。
a + 10*b = 4*xとすると、2*aは、4x - 20*bとなり、4で割り切れ(1)を満たしますが、2*a = 4*yとおいたとき、a + 10*bは2*y + 10*bとなってしまい、yしだいで4で割り切れない状況がでてきます。よって(2)を満たさないため、2*aが4の倍数の判定式としてふさわしくない、と証明できます。
いいかえれば、4の倍数なら一桁目を二倍にしたものは必ず4の倍数になるけれど、一桁目を二倍にしたからといって4の倍数とは限らないよ、ということに過ぎません。
