LoginSignup
2
0

More than 5 years have passed since last update.

合成数列の和Advent Calendar 2018Day 21
@sasanquaneufin株式会社ユニエイム

合成数列の和を求める - SQL + ？？？

Last updated at Posted at 2018-12-21

お題

【ルール】

入力として正の整数 N を与えたら 4 から始まる 合成数 の数列の 1 番目から N 番目までの合計を出力してください

N は最大で 100 とします

これに、SQLで挑みます。

sql
SELECT SUM(X) FROM (
SELECT
    A.0+B.0+C.0+D.0+E.0+F.0+G.0+H.0 AS X
FROM (SELECT 0 UNION SELECT 1) A JOIN (SELECT 0 UNION SELECT 1+1) B JOIN (SELECT 0 UNION SELECT 1+1+1+1) C
    JOIN (SELECT 0 UNION SELECT 1+1+1+1+1+1+1+1) D JOIN (SELECT 0 UNION SELECT 10+1+1+1+1+1+1) E
    JOIN (SELECT 0 UNION SELECT 10+10+10+1+1) F
    JOIN (SELECT 0 UNION SELECT 10+10+10+10+10+10+1+1+1+1) G
    JOIN (SELECT 0 UNION SELECT 100+10+10+1+1+1+1+1+1+1+1) H
WHERE EXISTS(
    SELECT 1
    FROM (SELECT 0 UNION SELECT 1) P JOIN (SELECT 0 UNION SELECT 1+1) Q
        JOIN (SELECT 0 UNION SELECT 1+1+1+1) R JOIN (SELECT 0 UNION SELECT 1+1+1+1+1+1+1+1) S
    WHERE
        (A.0+B.0+C.0+D.0+E.0+F.0+G.0+H.0) % (P.0+Q.0+R.0+S.0) = 0
    AND (A.0+B.0+C.0+D.0+E.0+F.0+G.0+H.0) > (P.0+Q.0+R.0+S.0)
    AND (P.0+Q.0+R.0+S.0) > 1
) LIMIT 100) X

少しまじめに解説

　（多くの）SQLが対象としているRDB:Relational Data Baseは数学的には「関係」というものが理論的背景になっています。関係というのは、簡単に言うと適当な集合と適当な集合の直積の部分集合の事で、RDBは実は集合論や直積と密接に関わっています。
　実際、JOINというのはテーブルAとテーブルBを集合と見た時に、それらの直積を取り、直積のうちON句に指定された条件に合致するものだけを抽出するという処理になっています。ON句に何も指定しなければ、実は直積そのものになるのです。
　直積という集合演算は、自然数における数と素朴に対応しているもので、$A,B$を集合とするとき$A \times B$というのは$A$と$B$の要素を一つずつ取った時にできる全ての組み合わせからなる集合、なのでした。
　そこで、これを利用して、はじめのA〜HをJOINしているところでは、要素2つの"テーブル"を8個掛け合わせ、つまり$2^8=256$個のレコードを生成しています。ここで"テーブル"と書いたのは、実際にはテーブルではなく、SELECT 0とSELECT 1などをUNIONして得られる、テーブルとして扱える何かです。
　この直積について、全てのカラムを合計すると、よく知られているように0〜255の全ての数と一対一の対応が得られます。これを自然数列と見て、合成数かどうかを判定します。
　合成数かどうかの判定には、$1<x \leq \sqrt{255}$を満たす約数が存在するかどうかを用いることにします。これが、EXISTS以下の内容であり、WHERE句の条件を満たすような行が存在する場合＝そのような約数が存在する場合には、0〜255のテーブルから要素を取得する、というような事になっています。これによって、合成数の取得ができます。

最後に、こうして取得された行の合計を取ることにすれば、それはまさしく求めるべき合成数列の和なのでした。

多くの場合、JOINでレコードが想定以上に増えるのはバグなのですが、このように全ての組み合わせを試すという考え方もあります。

しかし、題意を満たしていないのではないか

LIMIT 100の100を手書きで書き換える。そのような事が許されるのでしょうか？
プログラムというのは完成してユーザーに届くものであって、ユーザーが書き換えるような事は決してあってはなりません。
これは不正解です。

しかし、SQLでは適当な方言を利用しない限りは入力を受け付けることはできないので、SQLでの達成は無理です。
他にやり方は無いでしょうか？

熟慮した結果

私は必死に考えました。夜も寝ずに必死に考えました。
この苦境を脱する方法を…

そして思いつきました。
SQLで無理なら、SQLでプログラムを書いて、その結果を他の言語に食わせることによって処理をすればよいのです。

では、これに従ってSQLを書くようにしましょう。ここでは、他の言語としてbrainfuckを用いることにします。
なぜなら、命令数が少なく文法も簡単で、SQLで出力するにはもってこいだからです。

brainfuckのソースを出力するSQL（不完全）

brainfuck.sql
set session group_concat_max_len=100000;
SELECT CONCAT('+>+>>,------------------------------------------------[-<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>],------------------------------------------------[-<++++++++++>],------------------------------------------------[-<+>]<', GROUP_CONCAT(X separator ''), GROUP_CONCAT(Y separator ''), '>[[[->>>+<<<[->>>+<<<[->>>+<<<[->>>+<<<[->>>+<<<[->>>+<<<[->>>+<<<[->>>+<<<[->>>+<<<[->>+>---------<<<<]]]]]]]]]]>]<<[>]>>>>[-<<<<+>>>>]<>>>>>>>>>>+<<<<<<<<<<]>>>>>>>>>>[<<<<<<<<<<<<<++++++++++++++++++++++++++++++++++++++++++++++++.>>>>>>>>>>>]') FROM (
SELECT
    CONCAT('[>',A.Z,B.Z,C.Z,D.Z,E.Z,F.Z,G.Z,H.Z,'<-') AS X, ']' AS Y
FROM (SELECT 0, '' AS Z UNION ALL SELECT 1, '+') A JOIN (SELECT 0, '' AS Z UNION ALL SELECT 1+1, '++') B JOIN (SELECT 0, '' AS Z UNION ALL SELECT 1+1+1+1, '++++') C
    JOIN (SELECT 0, '' AS Z UNION ALL SELECT 1+1+1+1+1+1+1+1, '++++++++') D JOIN (SELECT 0, '' AS Z UNION ALL SELECT 10+1+1+1+1+1+1, '++++++++++++++++') E
    JOIN (SELECT 0, '' AS Z UNION ALL SELECT 10+10+10+1+1, '++++++++++++++++++++++++++++++++') F
    JOIN (SELECT 0, '' AS Z UNION ALL SELECT 10+10+10+10+10+10+1+1+1+1, '++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++') G
    JOIN (SELECT 0, '' AS Z UNION ALL SELECT 100+10+10+1+1+1+1+1+1+1+1, '++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++') H
WHERE EXISTS(
    SELECT 1
    FROM (SELECT 0 UNION ALL SELECT 1) P JOIN (SELECT 0 UNION ALL SELECT 1+1) Q
        JOIN (SELECT 0 UNION ALL SELECT 1+1+1+1) R JOIN (SELECT 0 UNION ALL SELECT 1+1+1+1+1+1+1+1) S
    WHERE
        (A.0+B.0+C.0+D.0+E.0+F.0+G.0+H.0) % (P.0+Q.0+R.0+S.0) = 0
    AND (A.0+B.0+C.0+D.0+E.0+F.0+G.0+H.0) > (P.0+Q.0+R.0+S.0)
    AND (P.0+Q.0+R.0+S.0) > 1
) LIMIT 100) X

実行結果

+>+>>,------------------------------------------------[-<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>],------------------------------------------------[-<++++++++++>],------------------------------------------------[-<+>]<[>++++<-[>++++++<-[>++++++++<-[>+++++++++<-[>++++++++++<-[>++++++++++++<-[>++++++++++++++<-[>+++++++++++++++<-[>++++++++++++++++<-[>++++++++++++++++++<-[>++++++++++++++++++++<-[>+++++++++++++++++++++<-[>++++++++++++++++++++++<-[>++++++++++++++++++++++++<-[>+++++++++++++++++++++++++<-[>++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]>[[[->>>+<<<[->>>+<<<[->>>+<<<[->>>+<<<[->>>+<<<[->>>+<<<[->>>+<<<[->>>+<<<[->>>+<<<[->>+>---------<<<<]]]]]]]]]]>]<<[>]>>>>[-<<<<+>>>>]<>>>>>>>>>>+<<<<<<<<<<]>>>>>>>>>>[<<<<<<<<<<<<<++++++++++++++++++++++++++++++++++++++++++++++++.>>>>>>>>>>>]

これを0から16までの数で実行してみましょう。
brainfuckでは、仕様上文字列を1文字ずつしか受け取れないので、例えば10と入力するときは010と入力してください。

懺悔

なぜ0から16までなのか？
それは、私がbrainfuckという言語の仕様を忘れていて、1つのセルが0〜255でループするのを忘れていたからです、、、
いやーつらい

ということで、正しいソースは後で追加します。
応援されたらがんばります！あと更新した通知も入るので、応援する人は積極的にいいねしよう。
説明も書くかもしれません。

一旦おしまい。

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0