関数型プログラミングの初級問題-32問目- 「オイラー関数」

　プログラミング初級者が挑戦する関数型プログラミングによる算数の練習問題の第32問です。問題は、OCaml公式ページのものを使いました。
　内容は、問題と答案です。答案の作成時間は、約0分でした。

問題32.

　オイラー関数phiを書け（オイラー関数とは、正の整数nと、そのn以下の正の整数であってnと互いに素な整数を要素とする集合の基数とからなる順序対の集合です）。

※ 例えば、phi 6は、2になります（6と互いに素な正の整数は、1と5の二つです）。

答案

本問の解き方

　前回の答案で作成した関数coprimeを使い回します。
　coprimeは、所与の二つの正の整数が互いに素であるか否かについて判定する関数です。　　
　そこで、coprimeに渡す二つの正の整数のうちの一方をphiの引数で固定し、他方を引数未満の正の整数として走らせます。
　これにより、phiの引数と互いに素な正の整数からなるリストが得られるので、その長さを返します。

コード

let phi n =
let rec len = function [] -> 0 | head::tail -> 1+len tail in

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

let rec gcd r1 r2 = if r2 = 0 then r1 else gcd r2 (r1 mod r2) in

let coprime n m = gcd n m = 1 in

let rec euler = function [] -> []
| head::tail -> if coprime n head then head::(euler tail) else euler tail in

len (euler (seq 1 n))

　関数lenは、リストの長さを求める関数です。
　関数seqは、aからbまでの整数のリストを求める関数です。
　関数gcdは、r1とr2の最小公倍数を求める関数です。
　関数coprimeは、nとmとが互いに素であるか否か判定する関数です。
　関数eulerは、所与の正の整数に対し素な整数のリストを求める関数です。

感想

　今回の問題も簡単だったので、簡単にすませました。そのため、ご覧の通り効率と頭が悪そうなコードになっています。

　一応、問題29の答案で実装したエラストテネスのふるいを使って、もっと効率のよい解き方はないか検討してみました。
　しかし、エラストテネスのふるいの実装自体が、あまり効率のよいものとは言えないので途中で諦めました。
　そもそも再帰的アルゴリズムは計算量を計算し難いと思います。

　次回は、第33問です。
　noteが勧めるように毎日記事を粗く書き濫りに投稿したおかげでビュー数が確実に減少しています。
　まさに「骨折り損のくたびれ儲け」です。
　この言い回しを知ったのは小学生のときでした。授業で「オツベルと象」を習った頃だったので、ずっと「骨折り象」だと思ってました、パオーン。