「オイラー関数改」：関数型プログラミングの初級問題-35問目-（1分）

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

問題35.

　以下の式を参考にオイラー関数phi_improvedを書け。
　$${\phi_{improved}(m) = (p_1-1)\times p_1^{m_1-1}\times (p_2-1)\times p_2^{m_2-1}\times (p_3-1)\times p_3^{m_3-1}\times \cdots}$$
　$${p_i:}$$素因数、$${m_i:}$$:指数

※ 例えば、phi_improved 5は、4になります。

答案

本問の解き方

　前回の答案で作成した素因数と指数のタプルからなるリストを生成する関数factorsを使い回します。
　後は、問題文の通りに実装すれば完成です。

コード

let factors n =
 let rec is_mul m p = if m < n then is_mul (m+p) p else n = m in

 let rec exp m p =
  if m < n then if is_mul m m then 1
  else 0+exp (m*p) p else 0 in

 let rec sweep m p = function
  | [] -> ((if n != m then None else Some (p, exp p p)), [])
 | head::tail ->
  if m = head && n != m then sweep (m+p) p tail
  else let (opt, rest) = sweep (if m < head then m+p else m) p tail in (opt, head::rest) in

 let rec sieve = function [] -> []
  | head::tail -> let (opt, rest) = sweep head head tail in match opt with
   | None -> sieve rest
   | Some e -> e::(sieve rest) in

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

 match sieve (seq 2 (n-1)) with
  | [] -> [(n, 1)]
  | _ as l -> l
----------------------------------------------------------------

 let phi_improved n =
  let rec power a b = if b = 0 then 1
  else if b = 1 then a
  else a*(power a (b-1)) in
 let rec phi = function [] -> 1
  | (p, m)::tail -> (p-1)*(power p (m-1))*phi tail in
 phi (factors n)

　点線より下が今回の答案で新しく書いた箇所です。
　関数powerはべき関数です。

感想

　今回の問題は簡単でした。問題文にて再帰的に定義されている式をただ写すだけでした。

　ところで、今回のオイラー関数は、問題32の関数からの「改良」となっていますが、全然良くなっていません。
　むしろ計算時間が増えており、悪くなっています。

$ time ./phi 113333

real	0m0.055s
user	0m0.049s
sys	    0m0.006s


$ time ./phi_improved 113333

real	0m1.231s
user	0m1.223s
sys	    0m0.006s

　何を根拠に改良などと言っているのか理解しかねます。

　だからと言って、改悪の理由も…あっ…
　もしかして「エラストテネスのふるい」が原因でしょうか？
　そう言えば調子に乗って、

　ご存知のように、所与の整数が素数であるか否かは、所与の整数と、それ未満の整数との剰余を取り、それが0か否かで簡単に判定できます。
　これは単純なループ処理一つで終わります。答案のようなややこしいコードにはなりません。

　なぜそうしなかったのか？

　それは「エラストテネスの篩を知ってる僕すごい！」をしたかったからです。精神的に成長しているのです。

関数型プログラミングの初級問題-29問目- 「素数」

などとバカなことを書いていました。

　今更プログラムを作り直すのも面倒なので、タイトルを「オイラー関数の改良」から「オイラー関数改」に変更しました。

　水平思考と言うやつです。犬やチンパンジーには出来ませんが、豚には出来る思考方法です。もちろん人である私にも！

次回は、第36問です。
　話の流れとしては狗肉か猿肉の料理を見出し写真に使いたかったのですが、さすがに見つかりませんでした。