2019年3月11日月曜日

Lyonsの7テスト

Martin Gardnerは面白い話を沢山書いた. 最近, Lyonsの7テストというものを読んだ. ニューヨークの精神神経科医 L. Vosburgh Lyonsが考案したという.

7で割ったときの剰余を計算するのは面倒だが, Gardnerによるとこれが一番効率がいいそうだ.

まず例から. 14桁くらいの整数を考える. n=12340123456789とでもするか. 右から2桁ずつ区切り, 12 34 01 23 45 67 89とし, それぞれの区画の2桁の数の7での剰余をとる. つまり上の例では

5 6 1 2 3 4 5

が得られる. これを3個ずつ揃え

   3 4 5
   6 1 2
         5
ーーーーー


それぞれをmod 7で足す. 2 5 5になるわけだ. 右の2個を55のように読み, 左の2個を25のように読み, 右の7の剰余6から左の7の剰余4を引くと元の数の7の剰余2が求まる.

なぜうまくいくか. とりあえずn=123456のような6桁だけで考えてみる.

2桁ずつをa, b, cとすると n=10000a+100b+c. n mod 7が欲しいから

10000 mod 7 = 4, 100 mod 7 = 2を入れて

n mod 7 = 4a+2b+c. こうして右の2桁 10b+c から 左の2桁 10a+b を引いたから,

10b+c - (10a+b)=-10a+9b+c. -10=4 mod 7, 9=2 mod 7だから

4a+2b+cになり目出度し目出度し.

6桁より大きいときは n=106a+bだが 10000=4 mod 7, 100=2 mod 7 だったから1000000=8 mod 7=1 mod 7で, n=a+bと同じになり, 6桁ずつ束にして扱えばよいことがわかる.

なるほど.

この方法が優れている理由を冷静に考えてみると, 2桁の数を7で割った剰余は簡単に得られることを利用しているからだ. 我々は7の段 7,2 14; 7,3 21; 7,4 28を諳じているから, それに70を足した84, 91, 98が7の倍数であることも承知している.

3桁を7で割るのはもっと面倒だが, それが出来るなら, Gardnerがいうように7の剰余は次のように得る.

n=12340123456789 を右から3桁ずつに分ける.

12 340 123 456 789 それぞれの7の剰余をとる.

5 4 4 1 5

右から交互に 5 - 1 + 4 - 4 + 5 = 9 = 2 mod 7

この方法は11での剰余なら

1 10 2 5 8

8 - 5 + 2 - 10 + 1 = -4 = 7 mod 11. n mod 11 = 7.

13の剰余なら

12 2 6 1 9

9 - 1 + 6 - 2 + 12 = 24 = 11 mod 13. n mod 13 = 11.

というふうに使えるが, 11や13の除数を得るのに計算機を使うなら最初から計算機を使えばよいから, そんなにメリットはない.

ところで今の手品の秘密は 7×11×13=1001 にある.