トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

プロジェクト・オイラー(066-070)

[プロジェクト・オイラー]

プロジェクト・オイラー(066-070)

  Problem 66

Probem 「ディオファントス方程式」

 次の形式の, 2次のディオファントス方程式を考えよう:

x%5E2+%2D+Dy%5E2+%3D+1+

 
 たとえば D=13 のとき, x を最小にする解は

649%5E2+%2D+13+%5Ccdot+180%5E2+%3D+1

である.D が平方数(square)のとき, 正整数のなかに解は存在しないと考えられる.
 D = {2, 3, 5, 6, 7} に対して x を最小にする解は次のようになる:
  • 3%5E2+%2D+2+%5Ccdot+2%5E2+%3D+1
  • 2%5E2+%2D+3+%5Ccdot+1%5E2+%3D+1
  • 9%5E2+%2D+5+%5Ccdot+4%5E2+%3D+1
  • 5%5E2+%2D+6+%5Ccdot+2%5E2+%3D+1
  • 8%5E2+%2D+7+%5Ccdot+3%5E2+%3D+1
 したがって, D ≤ 7 に対して x を最小にする解を考えると, D=5 のとき x は最大である.
 D ≤ 1000 に対する x を最小にする解で, x が最大になるような D の値を見つけよ.

Answer

+ 解答

  Problem 67

Probem 「最大経路の和 その2」

 以下の三角形の頂点から下まで移動するとき, その数値の合計の最大値は23になる.この例では 3 + 7 + 4 + 9 = 23100列の三角形を含んでいる15Kのテキストファイル triangle.txt (右クリックして, 『名前をつけてリンク先を保存』)の上から下まで最大合計を見つけよ.注:これは, Problem 18のずっと難しいバージョンです. 
 全部で299 通りの組み合わせがあるので, この問題を解決するためにすべてのルートをためすことは可能でありません!
 あなたが毎秒1兆本の(1012)ルートをチェックすることができたとしても, 全てをチェックするために200億年以上かかるでしょう. 
 解決するための効率的なアルゴリズムがあります. ;o)

Answer

+ 解答

  Problem 68

Probem 「Magic 5-gon ring」

 下に示す図のようなものを"magic" 3-gon ringという.
 これは1~6の数字を当てはめて, 各列の数字の和が9となっている.
 これを例として説明する.外側のノードのうち一番小さいものの付いた列(例では4,3,2)から時計回りに回ってそれぞれ列の数字を3つ連ねて説明する. 例えば例のものは4,3,2; 6,2,1; 5,1,3という組で説明することができる.1~6の数字を当てはめて, 各列の数字の和が等しくなるものは次の8通りある.この組の各数字を連結して, 9桁の数字で表すことができる.
 例えば, 上の図のものは4,3,2; 6,2,1; 5,1,3であるので432621513である.さて, 下の図に1~10の数字を当てはめ, 各列の数字の和が等しくなる"magic" 5-gon ringを作って, それを表す16桁または17桁の数字のうち, 16桁のものの最大の数字を答えよ.(注, 3つの場合の例を見ても分かる通り, 列の始まりの数字を比べた時一番小さい数字で始まる列から時計回りに繋げるという条件のもとで文字列を生成する必要があります.
 この条件下で最大となる数字を答えてください. )

Answer

+ 解答

  Problem 69

Probem 「トーティエント関数の最大値」

 オイラーのトーティエント関数, φ(n) [時々ファイ関数とも呼ばれる]は, n と互いに素な n 未満の数の数を定める. たとえば, 1, 2, 4, 5, 7, そして8はみな9未満で9と互いに素であり, φ(9)=6.n ≤ 10 では n/φ(n) の最大値は n=6 であることがわかる.n ≤ 1,000,000で n/φ(n) が最大となる値を見つけよ.

Answer

+ 解答

  Problem 70

Probem 「トーティエント関数の置換」

 オイラーのトーティエント関数 φ(n) (ファイ関数とも呼ばれる) とは, n 未満の正の整数で n と互いに素なものの個数を表す. 例えば, 1, 2, 4, 5, 7, 8 は9未満で9と互いに素であるので, φ(9) = 6 となる. 
 1 は全ての正の整数と互いに素であるとみなされる. よって φ(1) = 1 である.面白いことに, φ(87109)=79180 であり, 87109は79180を置換したものとなっている.1 < n < 107 で φ(n) が n を置換したものになっているもののうち, n/φ(n) が最小となる n を求めよ.

Answer

+ 解答

お名前: コメント: