忍者ブログ
20080511~ 13と7と11の倍数の論理積は13と7と11の積の倍数である。 和ァ・・・
[4447] [4446] [4445] [4444] [4443] [4442] [4441] [4440] [4439] [4438] [4437]
ある数10m+nがあります。m,nは整数です。
これが任意の整数Aの倍数かどうかを判定する式を作りたいとき、どうするか。



たとえば7の倍数判定だったらA=7で

-m+2nが7の倍数だったら10m+nも7の倍数


13の倍数判定だったらA=13で
m+4nが13の倍数だったら10m+nも13の倍数なんですが、
この4とか-2とか、Aを一般化したいわけです。



10m+n=A*z1
B2*m+B1*n=A*z2


としてみましょう。
(z1,z2、B1,B2も整数です)


1つ目の式を変形して、
n=A*z1-10m
このnを2つ目の式に代入して

B2*m+B1*(A*z1-10m)=A*z2
展開して
B2*m+A*B1*z1-10m*B1=A*z2

mを含む項と含まない項に分け
B2*m-10m*B1=A*z2-A*B1*z1

(B2-10B1)*m=A*(z2-B1*z1)


こうした上で、A=7だったら
B2=-1、B1=2とすると、左辺のカッコの中が-1-10*2=-21になって、両辺が7で約分できるので、判定式として成立します。

同様にA=13だったら
B2=1、B1=4とすると、左辺のカッコの中が1-10*4=-39になるため、両辺が13で約分できて、これも判定式として成立します。


つまり、以下の形に変形することにより、任意のAに対して

(B2-10B1)*m=A*(z2-B1*z1)

B2とB1を定めやすくなる、というわけです。

ためしにA=4だと
B1=1、B2=6とか
B2=2、B1=-1とかで成立します。

32が4の倍数だと判別するために、後者を採用すると
下1桁2から、それ以外3に2をかけて6にして引き算
-4になってこれは4の倍数なので、元の数32も4の倍数と、ちゃんとできています。



A=3だったら

B1=1、B2=1とすると
たとえば36だったら下1桁6とそれ以外3を足した9が3の倍数だったら、元の数36も3の倍数


A=11だったら
B2=-1、B1=1
121を相手にしてみると
下1桁1からそれ以外12を引いて11なので、元の121も11の倍数


とできます。



任意の数の倍数判定に使うことができます。
が、速度は遅いし、あまり役に立たないです。
2のべき乗と3のべき乗と5のべき乗と11のべき乗などを区別しません。

ですので、2や5のべき乗の倍数判定(十進数)では必ず割り切れるのでほとんど意味がありませんし

3や9の倍数判定、「各桁を足す」に対して、完全下位互換となりますし(おそろしく遅い)
11の倍数判定「偶数桁の合計と奇数桁の合計を引く」に対しても完全下位互換になります。



たとえば1053が3の倍数だということを確かめたい場合、
1+5+3=9なのですぐにわかりますが、今回の方法では

105と3を足した108が3の倍数か知るために8に10を足した18が3の倍数か知るために
1+8=9と、数珠つなぎのような地獄を味わうことになり、大変判定が遅くなります。



なお、ある数Aの倍数判定のための式は1つではなく、無数に作りだすことができます



100m3+10m2+m1とかにしたらどうなるんでしょうね?

拍手[0回]

PR

コメント


コメントフォーム
お名前
タイトル
文字色
メールアドレス
URL
コメント
パスワード
  Vodafone絵文字 i-mode絵文字 Ezweb絵文字


忍者ブログ [PR]
カレンダー
07 2019/08 09
S M T W T F S
1 2 3
4 5 6 7 8 10
11 12 13 14 15 16 17
18 19 20 22 23 24
25 26 27 28 29 30 31
ブログランキング
ブログランキング参戦中
にほんブログ村 アニメブログ 深夜アニメへ
にほんブログ村 漫画ブログ SF・ファンタジー漫画へ
にほんブログ村 科学ブログ 自然科学へ
よかったらポチッとお願いします^^
最新CM
[03/03 くそ]
[02/28 GIC結晶ファン]
[12/01 量子きのこ]
[11/06 NONAME]
[10/12 量子きのこ]
プロフィール
HN:
量子きのこ
年齢:
38
性別:
男性
誕生日:
1981/04/04
職業:
WinDOS.N臣T
趣味:
妄想・計算・測定・アニメ
自己紹介:
日記タイトルの頭についてるアルファベットは日記の番号です
26進数を右から読みます
例:H→7番目、XP→15(P)×26+23(X)=413番目。
A=0とする仕様につき一番右の桁はAにできませんのでご了承くださいズコー
バーコード
ブログ内検索
アクセス解析