読者です 読者をやめる 読者になる 読者になる

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 323 / ランダムな整数のビット論理和演算

y0, y1, y2,... をランダムな32ビット符号なし整数からなる数列とする。0≦yi<2^32 で,すべての値が同様に確からしい。数列 xi に対し次の反復が与えられる。

x0 = 0
xi = x(i-1) | y(i-1) (i>0)(| はビット単位のOR演算)

すべての i≧N に対し xi = 2^32-1(すべてのビットが1)となる添え字 N が存在する。

N の期待値を求めよ。答えを小数点以下10桁に四捨五入して求めよ。

Problem 323 - Project Euler


ORは結合法則
(x OR y) OR z = x OR y OR z
をみたすので,一回でも1が来ればその桁は1になります。

(ある桁が k 回以下の操作で1になる確率)
=(k 回中少なくとも1回は1が来る確率)
=1 - (1/2)^k

各桁は独立しているので,すべての桁が1になる確率は各桁ごとの確率の積です。

 P(N≦k)=\left\{1-(1/2)^k\right\}^{32}

ちょうど k 回で全桁揃う確率はこれの階差。

 P(N=k) = P(N≦k)-P(N≦k-1)

あとは k 倍して和を取ればおしまい。