PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 202 / レーザービーム

正三角形ABCの内側に鏡がはられている。各頂点にはレーザーが通れるような微小の穴がある。

Cから入ったレーザーが内側の辺で11回反射し頂点Cから出て行く経路は2つ存在する。1つを下に示す。もう1つはこの逆である。

f:id:variee:20170529185415g:plain

1000001回反射し出て行く経路は80840通り存在する。

Cから入ったレーザーが内側の辺で12017639147回反射し, 元の頂点Cから出て行く経路はいくつ存在するか。

Problem 202 - Project Euler

折れ線はのばす

入試でたまにある「折れ線はのばす」系の問題ですね。平面を三角形で覆いつくして,
C=O(0, 0), B(2, 0), A(1, √3)
となる座標をとって考えます。目標である点Cの座標は一般に
(3p, √3q) (p, q は偶奇の一致した整数)
とあらわされます。

また,光線がはじめにたどり着く頂点 P は m, n を互いに素な自然数として
↑OP =n↑OA + m↑OB =(2m+n, √3n)
とあらわされます。P=C から
2m+n=3p, √3n=√3q
∴ q=n, p=(2m+n)/3

これを p-q ≡0 (mod 2)に代入すると

 \dfrac{2}{3}(m-n)\equiv 0 \pmod{2}\quad \therefore m\equiv n \pmod{3}

反射の回数は k=2(m+n)-3 とあらわされるので,条件をまとめるとこうなります。

  • m+n=(k+3)/2
  • m, n は互いに素
  • m, n を3で割った余りは等しい

k=12017639147 のとき (k+3)/2 を3で割った余りは1なので,「m, n を3で割った余りは等しい」の余りは2です。

  • m, n を3で割った余りは2

m=3M+2 とおきます。

この式と n=(k+3)/2-m を
(m, n)=1(最大公約数)
に代入すると

 \left(3M+2, \dfrac{k+3}{2}\right)=1\quad \cdots\text{★}

M の範囲は m+n=(k+3)/2 と m, n ≧2 から

0\leqq M \leqq \dfrac{k-5}{6}\quad \cdots\text{☆}

★☆をみたす整数 M の個数が答えです。

★をまともに調べるのは大変そうなので (k+3)/2(=kk とおく)を素因数分解しました。

 kk=\dfrac{k+3}{2}=5^2\cdot 11\cdot 17\cdot 23\cdot 29\cdot 41\cdot 47

ダブリを除外するために5で割って計算します。時間は25分。

包除原理

時間短縮のため,包除原理を使います。

たとえば1以上N以下で3で割って余り2の数は

 \left[\dfrac{N-2}{3}\right]\text{個}

では,3で割って余り2かつ,5で割り切れる数は?
この条件をみたす数の最小値は5で,余りの周期は3*5=15なので

 \left[\dfrac{N-5}{15}\right]\text{個}

これを一般化します。包除原理の係数の ±1 は組み込み関数の
LiouvilleLambda で求めました。これは重複を数えた素因数の数を k として(-1)^k を返す関数です。結果は0.008秒。