ホーム ＞ リレーショナル・データベースの世界 ＞
SQLで数学パズルを解く（数論編-解答）
無限にある自然数の中には、ある種の性質を持つがゆえに名前を与えられた数が存在します。こうした特別な数は、その不思議さと美しさによって、はるか昔から多くの人々を惹きつけてきました。ここでは、そうした数を SQL を使って求めてみましょう。まずは、約数についての性質で分類したときの特殊な数がテーマです。
問題はこちら
素数の定義が全称量化文であることに気付いたでしょうか？ 「1とその数以外のどんな自然数によっても割り切れない」 ―― これは言い換えれば、
1とその数以外に割り切れる自然数が存在しない
という文と同義です。そうと分かれば、あとは NOT EXISTS を使えばダイレクトに SQL へ翻訳できます。
/* 答え＃１： NOT EXISTS で全称量化を表現 */
SELECT num AS prime
FROM Numbers Dividend
WHERE num > 1
AND NOT EXISTS
(SELECT *
FROM Numbers Divisor
WHERE Divisor.num <= Dividend.num / 2 --自分以外の約数は自分の半分以下にしか存在しない
AND Divisor.num <> 1 --1 は約数に含まない
AND MOD(Dividend.num, Divisor.num) = 0) --「割り切れない」の否定条件なので「割り切れる」
ORDER BY prime;
結果：
prime
-------
2
3
5
・
・
991
997
まず、被除数（Dividend）と除数（Divisor）の集合を用意します。自分を約数に含まないことから、約数は絶対に被除数の半分以下であることが確実なので（例えば、100の約数を探すときは、51以上は見る必要はない）、「Divisor.num <= Dividend.num / 2」という条件で、検索範囲をかなり制限できます。
このクエリは、パフォーマンス面で見てもかなりいいセンを行きます。NOT EXISTS は高速なうえ、結合条件で num 列のインデックスも利用できるでしょう。
全称量化は ALL 述語を使っても表現できます。それが次の答え＃２です。
/* 答え＃２： ALL 述語で全称量化を表現 */
SELECT num AS prime
FROM Numbers Dividend
WHERE num > 1
AND 0 <> ALL
(SELECT MOD(Dividend.num, Divisor.num)
FROM Numbers DIVISOR
WHERE Divisor.num <= Dividend.num / 2
AND Divisor.num <> 1)
ORDER BY prime;
やっていることは同じですが、こちらのが素直な肯定文なので、読みやすいかもしれません。しかし、パフォーマンスでは NOT EXISTS に一歩譲るでしょう。
もう一つ別解を。全称量化は HAVING 句で特性関数を使っても表せます。
/* 答え＃３： HAVING句で全称量化を表現 */
SELECT Dividend.num AS prime
FROM Numbers Dividend INNER JOIN Numbers Divisor
ON Divisor.num <= Dividend.num
AND Dividend.num > 1
GROUP BY Dividend.num
HAVING COUNT(*) = SUM(CASE WHEN MOD(Dividend.num, Divisor.num) <> 0
THEN 1
ELSE 0 END) + 2
ORDER BY prime;
前二者の解に比べてちょっとトリッキーなのが、結合条件で「約数は被除数の半分以下、かつ、約数に 1 は含まない」と書いてしまうと、2 と 3 が除外されて結果に出てこないので、やむをえずこれらを含める形で集約して、最後の「+ 2」で、1 と自分自身を「割り切れない数」にカウントしてやる、という点。
うーん、少し分かりにくいですね。もう少しスマートにできそうな気もする。誰か改良版考えてください。
･･････と書いたところ、泉さんという方から優れた別解が届けられました。何事も書いておくものですね。以下に示すのは、オリジナルに少し私が手を加えたもの（08/03/23）。
/* 答え＃４： HAVING句で全称量化を表現（改良版） */
SELECT Dividend.num as prime
FROM Numbers Dividend, Numbers Divisor
WHERE 1 < Dividend.num
AND Divisor.num <= SQRT(Dividend.num) --約数は被除数の平方根以下
GROUP BY Dividend.num
HAVING SUM(CASE WHEN MOD(Dividend.num, Divisor.num) = 0
THEN 1
ELSE 0 END) = 1 --1でしか割り切れない
ORDER BY prime;
SQRT関数が使えない場合は、「Divisor.num <= SQRT(Dividend.num)」は、「Divisor.num <= Dividend.num / Divisor.num」と書いても同じです。「Divisor.num * Divisor.num <= Dividend.num」と書いたほうが素直ですが、この書き方をする場合は、主キーのインデックスを利用するために左辺を裸にするのがいいでしょう。いま num 列に0は含まれないと仮定して構わないので、ゼロ割を考慮する必要はありません。
HAVING 句の CASE 式は、Divisor.num で割り切れれば1、割り切れなければ0を返す特性関数です。この合計が1になるということは、つまり割り切れる数が一つしかなかったということ。そして Divisor.num には必ず1が含まれるので、結局「1でしか割り切れなかった」ということを意味します。
私の考えたHAVING句の解法よりずっと意味を明確に伝える優れた答えです。しかも、約数の検索範囲も SQRT(num) 以下に制限できるのでパフォーマンスも向上します。べりぎゅー。
参考：
問題はこちら
「2で割り切れる」という条件も、「4で割り切れない」という条件もともに MOD 関数で記述できます。
/* 答え＃１：定義を直接記述 */
SELECT num AS single_even
FROM Numbers
WHERE MOD(num, 2) = 0
AND MOD(num, 4) <> 0;
結果：
single_even
-----------
2
6
10
14
・
・
・
また単偶数は 「（奇数）× 2」の形でも表せます。なぜなら 「（偶数）× 2」とは「 （適当な数） × 4」と同じだからです。従って次のクエリも正解です。
/* 答え＃２：「奇数 × 2」という条件を利用 */
SELECT num AS single_even
FROM Numbers
WHERE num IN (SELECT num * 2
FROM Numbers
WHERE MOD(num, 2) = 1);
もう一つ、泉さんからメールで届けられた別解を。「単偶数とは、要するに 4n + 2 型の数列を作ること」という発想から、次のような簡潔な答えが導かれます。
/* 答え＃３：4n + 2 の数列を作る */
SELECT num AS single_even
FROM Numbers
WHERE MOD(num, 4) = 2;
ザ・エレガント。気付かなかった。
問題はこちら
素数の場合と違い、集合 Square と Roots は一対一のペアとなるので、EXISTSを使う必要はありません（使っても書けますが、長いうえに、パフォーマンスも落ちます）。
SELECT Square.num AS square
FROM Numbers Square INNER JOIN Numbers Roots
ON Roots.num <= SQRT(Square.num)
AND Square.num = Roots.num * Roots.num;
「Roots.num <= SQRT(Square.num)」の条件はなくても結果は変わりませんが、パフォーマンス上は、ある方が良いかもしれません。
問題はこちら
約数に関わる問題なので、被除数と除数の集合を用意するのは、素数の場合と同じです。約数の和は、SUM 関数で求めましょう。後は HAVING句で、自分と約数の和が等しいという条件を記述すれば完成です。
/* 答え： */
SELECT Dividend.num AS perfect
FROM Numbers Dividend INNER JOIN Numbers Divisor
ON Divisor.num <= Dividend.num / 2
AND MOD(Dividend.num, Divisor.num) = 0
GROUP BY Dividend.num
HAVING Dividend.num = SUM(Divisor.num)
ORDER BY perfect;
結果：
perfect
---------
6
28
496
なお、ここで使った、ある数とその約数のペアの組み合わせは、ビューにしておくと色々な用途に使えて便利です。今後もこの約数ビューは多用します（このビューの約数には「自分自身」は含んでいない点に注意してください）。
約数ビュー：
CREATE VIEW Factors(num, factor) AS
SELECT Dividend.num, Divisor.num
FROM Numbers Dividend INNER JOIN Numbers Divisor
ON Divisor.num <= Dividend.num / 2
AND MOD(Dividend.num, Divisor.num) = 0;
参考：
問題はこちら
どちらも前問のクエリの簡単な変奏です。前問で作った約数ビュー（Factors）を使いましょう。
不足数
SELECT num AS def
FROM Factors
GROUP BY num
HAVING num > SUM(factor)
ORDER BY def;
過剰数
SELECT num AS adnd
FROM Factors
GROUP BY num
HAVING num < SUM(factor)
ORDER BY adnd;
問題はこちら
未解決。約数の集合の部分的な組み合わせの和が自身と一致することを、どうテストするかが問題。
問題はこちら
まずは、ある数についての約数の総和を求めます。それが、Ami_1、Ami_2です。これは名前が違うだけでどちらも同じ集合なので、ビューにするのも良いでしょう。
あとは、二つの数の組み合わせについて、互いの約数の総和と等しい、という条件を書けば完成です。
SELECT Ami_1.num AS ami_1, Ami_2.num AS ami_2
FROM ( SELECT num, SUM(factor) AS sum_fct
FROM Factors
GROUP BY num) Ami_1
INNER JOIN
( SELECT num, SUM(factor) AS sum_fct
FROM Factors
GROUP BY num) Ami_2
ON Ami_1.num < Ami_2.num
AND Ami_1.sum_fct = Ami_2.num -- ami_1の約数の和が、ami_2と等しくなる
AND Ami_2.sum_fct = Ami_1.num; -- ami_2の約数の和が、ami_1と等しくなる
結果：
ami_1 | ami_2
-------+-------
220 | 284
1184 | 1210
2620 | 2924
5020 | 5564
6232 | 6368
作成者：ミック
作成日：2007/07/21
最終更新日：2008/03/23
この作品は、クリエイティブ・コモンズ・ライセンスの下でライセンスされています。