Collatz予想(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 -