数学プログラミング・チャレンジ（問題）

数学プログラミングの問題を５問出題します。
いずれもCodeIQで出題しようと思っていたネタです。
各問とも正解者用のひとこと掲示板を用意してます。一番乗りを目指して下さい！

ルールなど

答えの数字をそのままフォームに入力して正解チェックする Project Euler 形式の出題です。
難易度は Project Euler の Easy～Medium ぐらいです。
うまくコードを書くと、普通の性能の PC で 1 分以下の実行時間で答えが出せるよう設計しています。出題者は C++ または Python で ideone で 1 秒を切れることを確認しています。
本問については、ブログ記事など自由に書いて下さってＯＫです。ただとりあえずの解禁日ということで 3/18(日) AM 8 時以降に公開して頂けると嬉しいです。
問題文についてのお問い合わせはこの記事のコメント欄か @riverplus までお願いします。

それではどうぞチャレンジを！

第１問：「メダルツアー」問題

自然数 w, h に対し、横と縦の長さがそれぞれ w, h となる格子状の道を考えます。
さらに、自然数 m に対し、左から m 番目の縦の道の、各交差点の中間にメダルが 1 個ずつ置いてあります。

例えば下図は、w, h, m = (4, 3, 2) のときの様子です。

この図の左下の点からスタートして、右上のゴールまで最短距離で向かいます。
途中で通過したメダルはすべて拾います。

取り得る経路を等しい確率で選ぶとき、拾うメダルの個数の期待値を F(w, h, m) と定義します。

例えば F(3, 2, 2) = 0.5 です。
取り得る経路は下図の 10 通りで、そのうちメダルを 2 個拾うものが 1 通り、1 個拾うものが 3 通り、0 個拾うものが 6 通りです。
したがって、期待値は 2×(1/10)＋1×(3/10)＋0×(6/10) ＝ 0.5 と計算できます。

同様に、F(1, 1, 1)＝0.5, F(2, 1, 3)＝1/3, F(4, 3, 2)＝0.6 となることが確かめられます。

小数点以下が 7 桁になるよう四捨五入した F(10, 10, 3) の値を求めて下さい。

正解チェックはこちらから

第２問：「奇数和平方数」問題

自然数 n に対し、連続する n 以下の奇数の和が平方数（自然数の 2 乗で表される数）となるものを探します。

例えば n = 10 の場合、以下の 7 通りです。
項が 1 つだけのものもカウントしている点に注意して下さい。

　　1 ＝ 1²
　　1＋3 ＝ 2²
　　1＋3＋5 ＝ 3²
　　9 ＝ 3²
　　1＋3＋5＋7 ＝ 4²
　　7＋9 ＝ 4²
　　1＋3＋5＋7＋9 ＝ 5²

このような表し方の数を F(n)と定義します。例えば F(10) = 7 です。
同様に、F(20)＝14, F(30)＝23, F(1000)＝1272 となることが確かめられます。

F(10⁷) の値を求めて下さい。

正解チェックはこちらから

第３問：「ヒストリー和」問題

自然数 k に対して、数列 F_k(n) を次のように定義します。
$\begin{eqnarray} F_k(n)=\left\{ \begin{array}{ll} 0 & (n<0) \\ 1 & (n=0) \\ \sum_{i=1}^{k} (k-i+1) F_k(n-i) & (n>0) \\ \end{array} \right. \end{eqnarray}$

例えば k = 3 なら次のようになります。
$\begin{eqnarray} F_3(n)=\left\{ \begin{array}{ll} 0 & (n<0) \\ 1 & (n=0) \\ 3F_3(n-1)+2F_3(n-2)+F_3(n-3) & (n>0) \\ \end{array} \right. \end{eqnarray}$

例えば F₃(1) = 3, F₃(2) = 11, F₃(3) = 40, F₃(4) = 145, F₅(10) = 36709715 です。

F₁₀(10¹⁰) + F_10⁴(10⁶) の値の、下 8 桁を求めて下さい。

正解チェックはこちらから

第４問：「ラディカル和」問題

自然数 n に対し、n の互いに異なる素因数の積を F(n) と定義します。

例えば F(24) = 6 です。24 を素因数分解すると 24 = 2³・3¹ で、互いに異なる素因数は 2 と 3 だからです。
同様に、F(5) = 5、F(60) = 30、F(1024) = 2 となることが確かめられます。

また、自然数 m に対し、1 から m までの自然数 n に対する F(n² + 1) の和を G(m) と定義します。

例えば G(3) = F(1² + 1) + F(2² + 1) + F(3² + 1) = F(2) + F(5) + F(10) = 2 + 5 + 10 = 17 です。
同様に、G(7) = 107、G(20) = 2590、G(100) = 299434、G(1000) = 303647368 となることが確かめられます。

G(2×10⁶) の値を求めて下さい。

正解チェックはこちらから

第５問：「10/16数」問題

10 進数で表された自然数 n に対し、この数字の並びをあたかも 16 進数のように読み、これを 10 進数として表したものを F(n) と定義します。
例えば n = 23 のとき、「23」を 16 進数として読んだものを 10 進数として表すと、2×16＋3 ＝ 35 ですから、F(23) = 35 となります。
同様に、F(9) = 9, F(10) = 16, F(11) = 17, F(100) = 256, F(999) = 2457 です。

さて、F(n) が n の整数倍となるような自然数を、「10/16 数」と呼ぶことにしましょう。

例えば 1038 は 10/16 数です。「1038」を 16 進数として読んだものを 10 進数で表すと、1×16³＋0×16²＋3×16¹＋8 ＝ 4152 により、F(1038) = 4152 です。たしかに 4152 は 1038 の倍数となっています。

1038 以外に 10/16 数はあるでしょうか。
1 桁の自然数（1～9）は全て 10/16 数です。
その次に小さな 10/16 数は 1038 です。
以降小さい順に、1040, 2078, 2080, 2118, … と続きます。
また 20 番目に小さな 10/16 数は 4238 です。

100 番目に小さな 10/16 数を求めて下さい。

正解チェックはこちらから