周の長さが12で、各辺の長さが全て整数の直角三角形は(3,4,5)だけである。 同様に24 -> (6,8,10), 30 -> (5,12,13) 等々、長さを与えれば3辺の長さが決まる。 中には120 -> (30,40,50), (20,48,52), (24,45,51) のように、ある周長に対して複数の直角三角形…

145 → 1! + 4! + 5! = 1 + 24 + 120 = 145 である。 このように各桁の階乗の和を取る作業を繰り返すことで、一連の数列を得ることができる。例えば169なら 169 → 363601 → 1454 → 169 と長さ3のループ（4回目でもとに戻る）を得る。 完全なループにならない…

分母が12,000以下の既約分数は1/3と1/2の間にいくつあるか。 いくつかの方法を試すが計算が終わらない。これは例によって「知らないと解けない」系ではないかと疑い周辺情報を調べた結果、"Farey sequence"という有名な数列に関する問題であることが判明。そ…

分母が1,000,000以下の既約分数は全部でいくつあるか。 問題は を求めることと同義である。ここまで重い計算を避けるために、φ関数を直接計算することは避けてきたが、この問題ではさすがにそうもいかない。連想リストで効率化をはかりつつ、計算は真っ向勝…

分母が1,000,000までの既約分数を小さい順に並べた時に、3/7の1つ前に来る分数（3/7より小さく、3/7に最も近い数）はなにか まず思いつくのは、全ての分数を列挙してsortして…というナイーブな手法だが、恐らくその方法では時間が掛かり過ぎる。もう少し論理…

引き続きオイラーのφ関数； 今度は n と φ(n) が順列入れ替えの関係にあるものを探す。 n / φ(n) が最小となる n < 10,000,000 を求める。 懸案が多い。 n / φ(n) が小さいということは、素因数は少ないほうがいいんだろうという予想は立つものの、厳密に証…

オイラーのφ関数。 n / φ(n) が最大となる n < 1,000,000 を求める。 φ(n) = n より小さく n と互いに素な数の個数（下表） 手始めに素直にφ関数を実装してみる。やってみると分かるが、数が大きくなると全く使えない。本質的に素因数分解と同じなので、大き…

1から1000までの数を英語でカウントするときの全文字数を求める； 1 なら one なので 3文字。342なら three hundred and forty two なので23 文字 115 なら one hundred and fifteen なので20 文字 イギリス流に正しく and を入れましょう。 嫌だ…。見られた…