2020-10-11

Problem 71

Project Euler

分母が1,000,000までの既約分数を小さい順に並べた時に、3/7の1つ前に来る分数（3/7より小さく、3/7に最も近い数）はなにか

　まず思いつくのは、全ての分数を列挙してsortして…というナイーブな手法だが、恐らくその方法では時間が掛かり過ぎる。もう少し論理的にアプローチできないか。そこで以下のように考えた。

求めるべき分数を $\displaystyle \frac{q}{p}$ とすると、問題は

$\displaystyle \delta = \frac{3}{7} - \frac{q}{p}$ を最小にする $p, q$ を求めることと同義である。 $p$ を固定したときの $q$ には以下の制約が課せられる。

$\displaystyle \frac{q}{p} \lt \frac{3}{7} \lt \frac {q + 1}{p}$

ここから

$\displaystyle 0 \lt \left(\frac{3}{7} - \frac{q}{p} \right) = \delta \lt \frac{1}{p}$

このことを利用して、3/7 - 1/1000000, 3/7 - 1/999999, 3/7 - 1/999998, ... と3/7 - 1/p の候補を小さい順番に評価していき、約分の結果一番最初に分母が1,000,000より小さくなる数を探し出した。数学的な正当性はもっと厳密に示す必要があるが、正解に辿り着くのは間違いない。

割と良いアイデアだったのではないか☆

2020-10-04

Problem 70

Project Euler

引き続きオイラーのφ関数；今度は n と φ(n) が順列入れ替えの関係にあるものを探す。
n / φ(n) が最小となる n < 10,000,000 を求める。

懸案が多い。
n / φ(n) が小さいということは、素因数は少ないほうがいいんだろうという予想は立つものの、厳密に証明しようとすると難しい。とりあえず２つの素数の積の中から答えを探索する方針で行く。
探索する素数の上限も怪しい。厳密には素数p,qに対して p☓q < 10,000,000なのだが、これを律儀にやっていては計算が終わらない。適当に範囲を絞るが根拠はない。

その辺に目を瞑りつつ、ゴニョゴニョと計算すると、一応正解には辿り着く。　　

とりあえず答えがあっていたというだけの…★

2020-10-04

Problem 69

Project Euler

オイラーのφ関数。 n / φ(n) が最大となる n < 1,000,000 を求める。
φ(n) = n より小さく n と互いに素な数の個数（下表）

手始めに素直にφ関数を実装してみる。やってみると分かるが、数が大きくなると全く使えない。本質的に素因数分解と同じなので、大きな素数同士の積になると時間が掛かるのは当然といえば当然か。

方針を変更すべく考えるうちに、逆に素数の積を計算するアプローチがあるのではないかと思い始める。しかし邪道だ。いいんだろうか…？と思い悩みながらも、背に腹は変えられないので計算だけはやってみる。すると一瞬で答えに辿り着く。

こんな方法でいいのかな…。と思っていたら、公式の解法(?)もどうやら同じようである。うーん、ちょっとモヤモヤするが、とりあえずよしとしよう。

まあまあ☆

2020-10-04

Problem 17

Project Euler

1から1000までの数を英語でカウントするときの全文字数を求める；

1 なら one なので 3文字。342なら three hundred and forty two なので23 文字
115 なら one hundred and fifteen なので20 文字
イギリス流に正しく and を入れましょう。

嫌だ…。見られたくない…。こんな力任せのコード…。嫌だ…。

はっ！　心の声が漏れ出してしまいました。この問題はずーっと放置していました。なぜならば；

理由①　問題が面白くない。ただの英語のテストやんけ。
理由②　素敵な解法が思いつきそうにない。力で押せ押せに見える。

しかしある時気づいたのです。 Project Euler には "solved fifty consecutive problems" に対する award があることを。

もっとスマートな場合分けはないものか。ガードの使い方も気に入らない。でもじっくり考える気力もない。

このへんで勘弁してください。

ううう…★