- 233 名前:132人目の素数さん mailto:sage [2007/10/29(月) 20:55:45 ]
- >>230
(1) [解] 要素数をA(n)とすれば、A(n+1)=A(n)+A(n)-1よりA(n)=(2^n)+1。 [解] 総和をS(n)とすれば、S(n+1)=S(n)+2(S(n)-2)+2よりS(n)=(3^n)+1。 [予想] 最大数は1,2から始まるフィボナッチ。 (2) [略証] aとbが互いに素のとき、写像 (a,b)├→ if a>b then (a-b,b) else (a,b-a) を考えると、互除法の原理から、これを繰り返し適用すれば必ず有限ステップNで (1,1)に到達し、その経路は一通りである。すなわち、これを(1,1)から逆に 辿ることにより、唯一の(a,b)が問題文の手続きに従って生成されることがわかる。 よってP_Nは順序対(a,b)を含み、それが唯一である。 (3) [予想] P_(n) に k (1≦k≦.n) はφ(k)個含まれる。ただしφ(k)は、 1≦i≦kであって、kと互いに素になるようなiの個数。
|
|