読者です 読者をやめる 読者になる 読者になる

破棄されたブログ

このブログは破棄されました。

2 のべき乗を用いて総和をテストする

caution 数学的な厳密性は不明です

ある集合の部分集合の要素の総和を検証したいときは、 2 のべき乗を使うとよさそう。

2 のべき乗を使うと、総和から部分集合の要素を特定することができる。

たとえば、

    • 条件 (condition)
    • 値 (value)
    • aaa
    • n_1
    • bbb
    • n_2
    • ccc
    • n_3
    • aaa
    • n_4

みたいなデータがあったとして、 aaa の列だけを取り出して和を取りたいとする。 SQL で書くと

SELECT SUM(value) FROM <TABLE> WHERE condition = 'aaa'

というようなケース。

こう言ったケースで、指定した条件(WHERE 句)が正しいことを検証したい場合、値 (value) に 2 のべき乗値を入れておく。

    • 条件 (condition)
    • 値 (value)
    • aaa
    • 2
    • bbb
    • 4
    • ccc
    • 8
    • aaa
    • 16

具体的にはこう。

こうすると、総和として 18 が得られ、選択された行が 18 = 2 + 16216 の行であることがわかる。

しかし、 2 のべき乗でない場合は、選択された行が特定できないことがある。

    • 条件 (condition)
    • 値 (value)
    • aaa
    • 1
    • bbb
    • 3
    • aaa
    • 2

例えば、 {1, 2, 3} を用いてしまったようなケースで、結果が 3 のとき、 3 = 1 + 2 なのか 3 = 3 なのかの区別がつかない。

2 のべき乗の二進数表現

なぜ 2 のべき乗だと、総和から要素を特定できるのかというと、 2 のべき乗を二進数で考えるとわかる。

2 : 00010
4 : 00100
8 : 01000
16: 10000

和をとっても各ビットが繰り上がったりすることはなく、選択された要素のビットのみが和に現れる。 したがって、総和のビット列から選択された要素を特定できる。

Sum-free sequence

Sum-free sequence 、もしくは A-sequence という正の整数列がある。

ある正の整数列があり、その任意の要素がその任意の部分集合の要素の総和と常に異なるような場合、この数列は Sum-free sequence となる。

たとえば、 2 のべき乗は Sum-free sequence なので、 {2, 4, 8} から 16 を作るみたいなことはできない。

一方で、 Sum-free sequence でない数列 {1, 2, 3} なんかは、 {1, 2} から 3 を作ることが出来てしまう。

ただし、定義としては任意の部分集合の要素の総和がユニークであることを保証しているわけではないようだ。

参考

広告を非表示にする