クエリで Project Euler Problem 4

【お題】

Problem 4。

Problem 4 「最大の回文積」 †
左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.

では, 3桁の数の積で表される回文数の最大値を求めよ.

【環境】

SQLServer	SQLCMD
2017	14.0.1000.169
設定はデフォルト。その他の環境は以下。

OS	CPU	ストレージ
Windows10 64bit	Corei7	SSD 250G

【クエリ 1】

馬鹿正直に実装すると以下。

;WITH [CTE_Val]([Val]) AS (                         -- 100 ～ 999 列挙CTE
    SELECT 100
    UNION ALL
    SELECT [Val] + 1 FROM [CTE_Val] WHERE [Val] < 999
)
, [CTE_Join]([Val], [ValStr]) AS (                  -- 100 ～ 999 × 100 ～ 999 列挙CTE
    SELECT
          [Val]
        , CONVERT(VARCHAR(6), [Val])                -- 文字列に変換
    FROM (
        SELECT
              [Src].[Val] * [Dst].[Val]
        FROM [CTE_Val] [Src], [CTE_Val][Dst]
    )t(Val)
)
SELECT MAX([Val]) FROM [CTE_Join]
WHERE   [ValStr] = REVERSE([ValStr])                -- 回文数判定
OPTION (MAXRECURSION 0)
;
GO

-----------
     906609

(1 行処理されました)

二つの3桁の数の全ての組み合わせの積を列挙。
数値を文字列に変換、REVERSE した結果と一致すれば回文数。
処理時間を計測したら約0.6秒だった。

結果はかなり大きな数値であることが予想されるので、最初の CTE を SELECT 900 として 900始まりとしたら約0.001秒だったけど、それは反則か。

【クエリ 2】

二つの3桁の数の積の最大値は 999 × 999 = 998001。この最大値から降順に調べた方が速いか？ ということで実装例は以下。

;WITH [CTE_Mul]([Mul]) AS (                         -- 100 ～ 999 列挙CTE(除数用)
    SELECT 100
    UNION ALL
    SELECT [Mul] + 1 FROM [CTE_Mul] WHERE [Mul] < 999
)
, [CTE_Val]([Val]) AS (                             -- 999 × 999 以下列挙CTE
    SELECT 999 * 999
    UNION ALL
    SELECT [Val] - 1 FROM [CTE_Val]
    WHERE   NOT EXISTS (
                SELECT 1 FROM [CTE_Mul]
                WHERE   [Val] % [Mul] = 0
                    AND [Val] / [Mul] < 1000
            )
        OR  CONVERT(VARCHAR(6), [Val]) <> REVERSE(CONVERT(VARCHAR(6), [Val]))
)
SELECT MIN([Val]) FROM [CTE_Val]
OPTION (MAXRECURSION 0)
;
GO

-----------
     906609

(1 行処理されました)

実行時間は約1秒。うーん、逆に遅いがな。
998001、998000、997999、……と調べる場合、問題はそれが回文数であるかの判定だけではなく、二つの3桁の数の積であるかの判定も必要なこと。
これって中々な難しいよね。（実はそれがこの問題のポイント？）

普通に考えたら、まず素因数分解。分解した素数群を二つのグループに分け、両グループの積が 1000未満だったらビンゴだけど、それをクエリで書くのはしんどい。
もっと単純でクエリに適したアルゴリズムは……とぐるぐる考えた末に出てきたのが上記の単純な試し割法。
100～999の除数テーブルを用意し、そのいずれかで割り切れ且つ割った結果が 1000未満であるか、という判定方法。しかし遅い。

結果論になってしまうけど、998001 から降順で調べる場合、約9万回ループすることになるので、それなりに高速に判定できないと遅い。
二つの3桁の数の積の降順で調べる単純な方法があれば、ループ数はずっと少なくなるんだろうけど。
二つの3桁の数の積の全てを列挙して……では最初のクエリで良いし。
イマイチ釈然としない結果。