コラッツ予想(MySQL編)


WHILE EXISTS (SELECT * FROM integers WHERE f!=1) DO
  UPDATE integers SET f=IF(MOD(f,2)=0,f/2,3*f+1),g=g+1 WHERE f!=1;
END WHILE;
SELECT n h FROM integers WHERE g=(SELECT max(g) FROM integers);

主記憶が足りなくなるかもという向きには、データベースがおすすめ(まじめな人はBIGINTにしてね)。{n,f,g}を格納するテーブルを作っておいて、
あとは言われたとおりにf=1になるまで計算、gの値が最大になる行のnを問い合わせればいい

MySQLなら全体は次のようになる(主記憶を気にしないなら、CREATE TABLE文の最後にTYPE=HEAPをつけて速くできる)

DELIMITER //
DROP TABLE IF EXISTS integers//
CREATE TABLE integers (n INT PRIMARY KEY,f INT NOT NULL,g INT DEFAULT 0 NOT NULL,KEY(f))//

DROP PROCEDURE IF EXISTS collatz//
CREATE PROCEDURE collatz(maxNum INT)
BEGIN
  DECLARE i INT DEFAULT 1;
  TRUNCATE TABLE integers;
  SET i=1;
  WHILE i<maxNum+1 DO
    INSERT INTO integers (n,f) VALUES (i,i);
    SET i=i+1;
  END WHILE;
  
  WHILE EXISTS (SELECT * FROM integers WHERE f!=1) DO
    UPDATE integers SET f=IF(MOD(f,2)=0,f/2,3*f+1),g=g+1 WHERE f!=1;
  END WHILE;
  
  SELECT n h FROM integers WHERE g=(SELECT max(g) FROM integers);
END;//

CALL collatz(100)//
+----+
| h  |
+----+
| 97 |
+----+

途中の計算結果を利用したいなら、主要部を次のように変更

UPDATE integers a,integers b SET a.f=1,a.g=a.g+b.g WHERE a.f!=1 AND a.f=b.n AND b.f=1;
UPDATE integers SET f=IF(MOD(f,2)=0,f/2,3*f+1),g=g+1 WHERE f!=1;

これでかなり速くなる。欲を出して、途中の計算をすべて記憶しておこうとすると逆効果。「テーブルにないfの値が出てきたら、それをテーブルのnに追加し、計算はそっちだけにする」という戦略で解くのが下(calは、fを計算するかどうかを指示するフラグ)

DELIMITER //
DROP TABLE IF EXISTS integers//
CREATE TABLE integers (
  n INT PRIMARY KEY,
  f INT NOT NULL,
  g INT DEFAULT 0 NOT NULL,
  cal BOOL DEFAULT 1 NOT NULL,
  KEY(f),
  KEY(cal)
)//

DROP PROCEDURE IF EXISTS collatz//
CREATE PROCEDURE collatz(maxNum INT)
BEGIN
  DECLARE i INT DEFAULT 1;
  TRUNCATE TABLE integers;
  SET i=1;
  WHILE i<maxNum+1 DO
    INSERT INTO integers (n,f) VALUES (i,i);
    SET i=i+1;
  END WHILE;
  
  WHILE EXISTS (SELECT * FROM integers WHERE f!=1) DO
    UPDATE integers a,integers b SET a.f=1,a.g=a.g+b.g WHERE a.f!=1 AND a.f=b.n AND b.f=1;
    INSERT INTO integers (n,f) SELECT f n,f FROM integers a WHERE a.f!=1 AND NOT EXISTS (SELECT * FROM integers b WHERE a.f=b.n);
    UPDATE integers a,integers b SET a.cal=0 WHERE a.f=b.n AND a.g!=0 AND b.g=0;
    UPDATE integers SET f=IF(MOD(f,2)=0,f/2,3*f+1),g=g+1 WHERE f!=1 AND cal!=0;
  END WHILE;
  
  SELECT n h FROM integers WHERE g=(SELECT max(g) FROM integers);
END;//

CALL collatz(100)//
+----+
| h  |
+----+
| 97 |
+----+

SELECT COUNT(n) FROM integers//
+----------+
| COUNT(n) |
+----------+
|      251 |
+----------+

キミならどう書く 2.0 – ROUND 2 –

100までの整数から素数を列挙せよ(SQL編)


SELECT n prime FROM(
  SELECT x.n,COUNT(DISTINCT d.n) c
    FROM integers x,integers d
    WHERE MOD(x.n,d.n)=0 AND d.n<=x.n
    GROUP BY x.n) tmp
  WHERE c=2;

「欲しいものを書くだけでいい」というのがSQLのいいところ。この場合は「約数をちょうど2つ持つ整数」と書けばいい。エラトステネスの篩いを試みたりしてはいけない(そういう意味ではPrologでもいいのだけれど、文法を思い出せない)

でも、あらかじめ整数をテーブルに入れておくという準備が必要で、Oracleならこんな感じか

DROP TABLE integers;
CREATE TABLE integers (n INT NOT NULL);

DECLARE
  maxNum INT:=100;
  i INT:=1;
BEGIN
  EXECUTE IMMEDIATE 'TRUNCATE TABLE integers';
  WHILE i<maxNum LOOP
    INSERT INTO integers (n) VALUES (i);
    i:=i+1;
  END LOOP;
END;
/
SELECT n prime FROM(
  SELECT x.n,COUNT(DISTINCT d.n) c
    FROM integers x,integers d
    WHERE MOD(x.n,d.n)=0 AND d.n<=x.n
    GROUP BY x.n) tmp
  WHERE c=2;

SELECT文を直接書けないからPL/SQLはあまり好きではないんだけど、
無理矢理PROCEDUREにするなら、こんな感じか

CREATE OR REPLACE PROCEDURE primes (maxNum INT) AS
  i INT:=1;
  CURSOR cur IS
    SELECT n prime FROM(
      SELECT x.n,COUNT(DISTINCT d.n) c
        FROM integers x,integers d
        WHERE MOD(x.n,d.n)=0 AND d.n<=x.n
        GROUP BY x.n) tmp
      WHERE c=2;
BEGIN
  EXECUTE IMMEDIATE 'TRUNCATE TABLE integers';
  WHILE i<maxNum LOOP
    INSERT INTO integers (n) VALUES (i);
    i:=i+1;
  END LOOP;
  
  FOR item IN cur
  LOOP
    DBMS_OUTPUT.PUT_LINE(item.prime);
  END LOOP;
END;
/
CALL primes(100);

Version 5になってやっと使えるようになったMySQLのストアド・プロシージャを使うなら

DELIMITER //
DROP TABLE IF EXISTS integers//
CREATE TABLE integers (n INT)//

DROP PROCEDURE IF EXISTS primes//
CREATE PROCEDURE primes(maxNum INT)
BEGIN
  DECLARE i INT DEFAULT 1;
  TRUNCATE table integers;
  WHILE i&lt;maxNum DO
    INSERT INTO integers (n) VALUES (i);
    SET i=i+1;
  END WHILE;
  
  SELECT n prime FROM(
    SELECT x.n,COUNT(DISTINCT d.n) c
      FROM integers x,integers d
      WHERE MOD(x.n,d.n)=0 AND d.n<=x.n
      GROUP BY x.n) tmp
    WHERE c=2;
END;//

CALL primes(100)//
&#91;/sql&#93;

<p><a href="http://ll.jus.or.jp/2006/blog/doukaku1">キミならどう書く 2.0 - ROUND 1 -</a></p>

<p>追記:エラトステネスの篩いね、そりゃあ、このほうが速いよ</p>

[sql]
DELIMITER //
DROP TABLE IF EXISTS integers//
CREATE TABLE integers (
  n INT PRIMARY KEY,
  flag INT DEFAULT 0 NOT NULL,
  KEY(flag)
)//

DROP TABLE IF EXISTS results//
CREATE TABLE results (prime INT PRIMARY KEY)//

DROP PROCEDURE IF EXISTS primes//
CREATE PROCEDURE primes(maxNum INT)
BEGIN
  DECLARE i INT DEFAULT 2;
  TRUNCATE table integers;
  WHILE i&lt;maxNum DO
    INSERT INTO integers (n) VALUES (i);
    SET i=i+1;
  END WHILE;
  
  WHILE EXISTS (SELECT * FROM integers WHERE flag=0) DO
    INSERT INTO results (prime) SELECT n FROM integers WHERE flag=0 LIMIT 1;
    UPDATE integers JOIN (SELECT MAX(prime) p FROM results) tmp SET flag=1 WHERE MOD(n,p)=0;
  END WHILE;
  
  SELECT prime FROM results;
END;//

CALL primes(100)//