「ゴールドバッハ予想の組合せ数」：関数型プログラミングの初級問題-39問目-（1分）

　素数についての練習問題と答案です。問題は、OCaml公式ページのものを使いました。答案の作成時間は、約1分でした。

問題39.

　$${\Z}$$の有界閉区間に対し、そこに含まれる全ての偶数と、その組合せ数とを含むリストを生成する関数goldbach_listを書け。なお、組合せ数はタプルで表せ。また、リストの要素は、偶数と組合せ数のタプルとからなるタプルで表せ。

※ 例えば、goldbach_list 23 33は、[(24, (5, 19)); (26, (3, 23)); (28, (5, 23)); (30, (7, 23)); (32, (3, 29))]になります。

答案

本問の解き方

　前回の答案で作成した関数goldbachを使い回します。
　具体的には、まず引数から閉区間を生成します。
　次に、その閉区間から偶数を順番に選び出すとともに、その偶数に対し関数goldbachにより組合せ数を求めて組合せ数のタプルを生成します。
　次に、各偶数と組合せ数のタプルとからなるタプルを生成し、その生成したタプルを集めてリストを生成します。

　日本語にすると反って分かり辛いので、コードを読める人はコードを見てください。

コード

let rec seq a b = if a < b then a::(seq (a+1) b) else [b]

let all_primes a b =
let rec sweep m p = function [] -> []
  | head::tail ->
   if m = head then sweep (m+p) p tail
   else head::(sweep (if m < head then m+p else m) p tail) in

 let rec sieve = function [] -> []
  | head::tail -> head::(sieve (sweep head head tail)) in

 sieve (seq a b)

let goldbach n =
 let rec loop2 =
 let rec loop1 m = function [] -> []
  | head::tail -> if n = m+head then [m, head] else loop1 m tail in

 function
  | [] -> raise (Failure "goldbach")
  | head::tail as lst -> match loop1 head lst with
   | [] -> loop2 tail
   | head::_ -> head in

 loop2 (all_primes 2 n)
--------------------------------------------------------------------------------
let goldbach_list a b =
 let rec is_even x =
  if x < 0 then true else if x = 1 then false
  else is_even (x-2) in

 let rec loop = function [] -> []
  | head::tail ->
   if is_even head then (head, goldbach head)::(loop tail)
   else loop tail in

 loop (seq a b)

　点線から下が今回の答案で書いたコードです。

感想

　今回の問題も簡単でした。算数における最後の問題なので身構えていたのですが拍子抜けしました。

　ところで、本問には続きがあります。それは、
「多くの場合で組合せ数は一方が小さな値になる、両方が50を越えることは珍しい、その珍しい組合せ数を[2, 3000]の範囲で探せ」
　というものです。
　しかし、プログラムとして高度な技術が必要とされ、また話題への興味があり余り文字数を大幅に超過しそうなので無視しました。

　ゴールドバッハ予想は有名な問題です。この美しい真実に感銘を受けないプラトン主義者はいないでしょう。この世は数学により構成され、そこに君臨するのが女王たる整数論なのです。

　次回は、第40問です。
　今回の結語は、いつもの否定的・悲観的な記述をやめて、肯定的・楽観的に書き換えてみました。水面に浮いてきたサヨリの如くキラキラしているはずです。ビュー数増間違いなしです。