数学サイト
http://blog.livedoor.jp/mazra627/
から
 
第154回「ファレイ数列」
問題(さらに「オイラー関数」)
 
ある線分の2等分点、3等分点、4等分点と順に
新しい等分点にだけ印をつけていきます。
15等分点も印をつけたとき、
新たに増える印の数を答えてください。
 
(ここでは答えとなるオイラー関数についても考えてみたい)
 
 
解答例:

 
イメージ 2
 
15等分の等分点は14個。
素因数分解15=3×5だから
3等分点=2と、5等分点=4は重複するので、
単純に、14-2-4=8 ―――――――――――(答え)
 
ということは、n等分では
(n-1)-シグマ(nの素因数-1)?・・・違う。
反例:n=12のとき答えの4にならない、など・・・。
 
n等分で新たに増える印の数
=(n-1)
 -((1~(n-1)で、1以外のnの素因数と、その倍数)の個数)
               ―――――――――――――――――――(1)
(これは、また)
=n-((1~nで、1以外のnの素因数と、その倍数)の個数)
=(1~nで、nと互いに素となる整数の個数) とも表せる。 →(7)参照。
これは、
分母n、分子1~(n-1)の分数のうち、
約分できない分数の個数と同義となる。――――――――――――――――(2)
これも、・・・分子1~nの分数のうち、
約分できない分数の個数・・・と書いても変わりはないと言ってよいだろう。
 
問題では、(1)より
14-((1~14で、1以外の素因数と、その倍数)の個数)
=14-((3,5,6,9,10,12)の個数6)=8 ―――(答え)
(=15-((3,5,6,9,10,12,15)の個数7)=8
 としても結果は同じである)
つまり、1,2,4,7,8,11,13,14、の8個
または、(2)より
分母15、分子1~14の分数のうち、
約分できない分数の個数ということで
3/15=1/5,5/15=1/3,6/15=2/5,
9/15=3/5,10/15=2/3,12/15=4/5
以上のように約分できる分数6個を除いた次の
1/15,2/15,4/15,7/15,8/15,
11/15,13/15,14/15、の、8個 ――――――――(答え)
(これもまた、分子1~15の分数のうち、と変えて、
 約分できる分数に15/15=1を加えても結果は同じである)
(1)と(2)は同義になる。
 
また、nについては、
n=p^?×q^?×r^?×・・・と素因数分解できた場合、――――――――(3)
(p、q、r、・・・は、互いに異なる1以外の素数である。
 また、指数「^?」は、1以上の何乗でもよい。
 nが素数の場合、素因数分解は、n=n^1 だけということになる。) ――(3)
答えは、
オイラー関数(n)
=n×(1-1/p)×(1-1/q)×(1-1/r)×・・・
で求められるという。 ―――――――――――――――――――――(4)
例えば
n=15のとき素因数3,5
15(1-1/3)(1-1/5)=8 ――――――――――――(答え)
n=12のとき素因数2,3
(上の(3)(4)の式のように、素因数2^2は2だけでよい)
12(1-1/2)(1-1/3)=4
(1,5,7,11、の4個である)
 
1~nの
オイラー関数(n)の意味は、
1~nの整数のうち、nを含まず、1を含むが、
nと互いに素である(約数を共有しない)整数の個数を意味する。
これは、(1)や(2)の意味と同じになるが、――――――――――(5)
 
オイラー関数の証明を検索したら、
合同式で求める方法があったが、分かりにくかった(苦笑)ので、
ここでは
オイラー関数について確率で?考えてみる。
(ちょっと怪しいかもしれない・・・?)
 
問題では、
分けた線分+その右側の点を1単位と考えると、
全部で15の場合の数、つまり選択肢の数、になる。
それを左から1~15の番号を並べるとする。

 
イメージ 1

(特定の場合の確率)
=(特定の場合の数)/(全部の場合の数)
 
 ∴ (特定の場合の数)
=(全部の場合の数)×(特定の場合の確率)――――――――(6)
 
分けた線分と線分の右にある点を1つの単位と見なす。
そうすると、問題の場合の数は全部で15になる。
3の倍数を取り出す確率=1/3
3の倍数を取り出さない確率=1-1/3
(取り出さない場合に15も含まれる)
5の倍数を取り出す確率=1/5
5の倍数を取り出さない確率=1-1/5
(取り出さない場合に15も含まれる)
(6)において
(3の倍数にも5の倍数にもならない場合の数)
=(全部の場合の数15)
×(3の倍数にも5の倍数にもならない確率)
=15×((1-1/3)×(1-1/5))
・・・上のオイラー関数になる・・・?
 
一般的に(3)の素因数分解
n=p^?×q^?×r^?×・・・ 
(p、q、r、・・・は互いに異なる素数、など(3)と同様)
においては、
nは、pでもqでもrでも・・・割り切れるので、
例えば、pについては、
1から、n=p×mまでに、pの倍数はm個あるので、
pを選ぶ確率は、m/pm=1/pである。(当たり前か・・)
p、q、r、同様に考えて、
pの倍数を選ぶ確率=1/p
 ∴ pの倍数を選ばない確率=(1-1/p)
qの倍数を選ぶ確率=1/q
 ∴ qの倍数を選ばない確率=(1-1/q)
rの倍数を選ぶ確率=1/r
 ∴ rの倍数を選ばない確率=(1-1/r)
  ・・・・・・
 (6)に当てはめて
(1~nのうち、素因数p、q、r、・・・のいずれの倍数でもない整数の個数)
=(1~(n-1)の整数のうち、nと互いに素となる整数の個数)
=(1~nの整数のうち、nと互いに素になる整数の個数) ――――――――(7)
(上(7)のように「1~nの整数のうち・・・」と書いたほうが
 全体の個数つまり場合の数を n とするのに分かりやすいかもしれない。
 「互いに素」とは「最大公約数が1」と同義であるから
 nとnは互いに素とは言えず、 「1~(n-1)の整数のうち・・・」と
 「1~nの整数のうち・・・」とは、ここでは変わりないと言ってよいだろう)―――(7)
=(全体の場合の数、即ち全体の個数、n )
  ×(1~nのどれか1個を選んだとき、それが、
    nの素因数であるp、q、r、・・・のいずれの倍数でもない確率)
=n×((1-1/p)×(1-1/q)×(1-1/r)×・・・)
=(4)のオイラー関数(n) となる。
 
※ ファレイ数列は、長さ1の線分の、2からn等分点までの
すべての等分点を、0~1の分数で表したもので面白い特性があるのだが、
今回の問題としてはオイラー関数のほうに、より興味が向いたので、
触れる余裕がありませんでした。失礼。
 
(2011年11月13日、同日一部修正)
(2011年11月14日、図など一部修正)
------------------------------------------------
考えてるうちに、混乱しているかもしれません。
コメントいただければ幸いです。