ホーム ＞ リレーショナル・データベースの世界 ＞
SQLで数学パズルを解く（数論編-問題）
このコーナーは、SQL を使って色々な数学上の問題を解いていくことで、楽しく SQL の勉強をしよう、という趣旨のサイトです。SQL はその本来の用途として、計算向きの言語ではありません。SQL の本領は検索、すなわち与えられた集合から、条件を満たす部分集合を見つけ出すことにあるからです。それゆえ、数学パズルをプログラミング言語を使って解くアルゴリズムは世に多く知られていますが、SQL による解き方は独特なものになります。皆さんも、頭をひねって色々な解法を考えてみてください。
このサイトでは、主に数論、つまり数の性質にまつわるパズルを主に取り上げます。姉妹編として、「組み合わせ編」も参照。
ではまず、下準備として自然数列を持つテーブルを用意しましょう。次のコードを実行してください。これで Numbers テーブルに 1〜1000の自然数が 1000 行作成されます（この SQL の意味を知りたい人は、「SQLで数列を扱う」を参照）。
--数字テーブル
CREATE TABLE Digits
(digit INTEGER PRIMARY KEY);
INSERT INTO Digits VALUES (0);
INSERT INTO Digits VALUES (1);
INSERT INTO Digits VALUES (2);
INSERT INTO Digits VALUES (3);
INSERT INTO Digits VALUES (4);
INSERT INTO Digits VALUES (5);
INSERT INTO Digits VALUES (6);
INSERT INTO Digits VALUES (7);
INSERT INTO Digits VALUES (8);
INSERT INTO Digits VALUES (9);
--自然数列のテーブル
CREATE TABLE Numbers
(num INTEGER PRIMARY KEY);
--1〜1000の自然数を生成
INSERT INTO Numbers
SELECT D1.digit + (D2.digit * 10) + (D3.digit * 100) + 1 AS seq
FROM Digits D1, Digits D2, Digits D3;
--自然数テーブルをクリアするときは以下を実ﾀ行
DELETE FROM Numbers;
準備ができたら、早速始めましょう。解法を考えるときの条件は、以下のように緩くしておきましょう。
- 実装依存の機能を使っても OK。しかしできれば標準 SQL に則っていると望ましい。
- 剰余の関数 MOD を使ってよい。
- 上で作った自然数テーブルは使わなくてもよい。別の補助テーブルを使うのもアリ。
また、問題および解法も随時募集しております。「この問題が解けるか！」という挑戦でも、「こんなエレガントな（or 奇抜な）解法を思いついた」という自慢でも大歓迎です。タレコミ先は、メール、ゲストブック、ブログのいずれからでもどうぞ。
無限にある自然数の中には、ある種の性質を持つがゆえに名前を与えられた数が存在します。こうした特別な数は、その不思議さと美しさによって、はるか昔から多くの人々を惹きつけてきました。ここでは、そうした数を SQL を使って求めてみましょう。まずは、約数についての性質で分類したときの特殊な数がテーマです。
素数とは、1とその数自身以外に正の約数を持たない（つまり1とその数以外のどんな自然数によっても割り切れない）、1 より大きな自然数のこと。
まず小手調べは、皆さんご存知のこの数からです。1 と自分自身以外に約数を持たない数。「寂しい数」などとも言われます。数論分野では最も基本的な構成要素となる重要な数で、小さい順に並べると
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 ･･･
となります。これを SQL で求めてください。
解答はこちら
単偶数または半偶数とは、2で割り切れるが4では割り切れない整数のこと。
MOD関数の練習問題ですが、いくつか求め方があります。
解答はこちら
平方数とは、別の自然数の二乗（平方）になっているような自然数のこと。
これが解けたら立方数も求めてみてください。
解答はこちら
完全数とは、その数自身を除く約数の和が、その数自身と等しい自然数のこと。
完全数は、小川洋子『博士の愛した数式』にその名が登場したことから広く知られました。例えば、6 = 1 + 2 + 3、28 = 1 + 2 + 4 + 7 + 14 などがそうです。完全数にはいくつかのヴァリエーションがあるので、まずはこのオーソドクスな完全数の求め方を理解しておくことが肝心です。
解答はこちら
不足数は自然数で、その正の約数の総和が元の数の2倍より小さい数のこと。言い換えると、その数自身を除く正の約数の総和が元の数より小さくなるような数のことである。
過剰数は自然数で、その正の約数の総和が元の数の2倍より大きい数のこと。言い換えると、その数自身を除く正の約数の総和が元の数より大きくなるような数のこと。
上述の完全数は、自分と約数の和がピタリ一致する数でした。今度はその条件が、「足りない」と「余る」に変わったわけです。不足数は、小さい方から並べると、
1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19 ･･･
過剰数は、
12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72 ･･･
となります。
解答はこちら
擬似完全数は自然数で、自身を除くいくつかの約数の和が元の数に等しい数のこと。
例えば、20 の自身を除く約数は、1, 2, 4, 5, 10 の 5 つ。このうち 2 を除いた 4 つの和は、1 + 4 + 5 + 10 = 20 となるので、20 は擬似完全数です。定義から、全ての完全数は擬似完全数ですが、擬似完全数の中には過剰数も含まれています。
擬似完全数を6から小さい順に列記すると
6, 12, 18, 20, 24, 28, 30, 36, 40 ･･･
となります。
この問題は、部分和問題という計算量理論の分野の問題の一種です。手続き型言語ならば、総当り的に組み合わせをテストして、一つでも条件を満たす組を見つければそこでテストを打ち切ればいいのですが、SQL の場合、約数の全ての組み合わせを作らざるをえません。「安定結婚問題」もそうですが、この手の組み合わせ問題は、SQL の苦手な分野です。
解答はこちら
友愛数とは、異なる2つの自然数の自分自身を除いた約数の和が、互いに他方と等しくなるような数のこと。
自分の約数を足すと相手になる。相手の約数を足すと自分になる、という仲良し関係にあるペアです。これもやはり『博士の愛した数式』に登場してその名を知られました。友愛数は比較的あらわれる頻度の低い数で、1,000以下では (220, 284) のペア一つだけです。そのため1,000までのテーブルを使うと結果が寂しいので、今回は、Numbers テーブルを増やして10,000まで用意しましょう。以下のクエリを実行してください。
DELETE FROM Numbers;
INSERT INTO Numbers
SELECT D1.digit + (D2.digit * 10) + (D3.digit * 100) + (D4.digit * 1000) + 1 AS seq
FROM Digits D1, Digits D2, Digits D3, Digits D4;
解答はこちら
作成者：ミック
作成日：2007/07/21
最終更新日：2007/07/24
この作品は、クリエイティブ・コモンズ・ライセンスの下でライセンスされています。