*[[Problem 382:http://projecteuler.net/problem=382]] 「ポリゴン生成」 [#q1d56ca5]
''ポリゴン''とは, 閉じた閉路になるよう組み合わされた直線分から成る平面図形のことである. ポリゴンは少なくとも3つの辺から成り, それ自身と交わることはない.
正の整数の集合 S が以下の条件を満たすとき ''ポリゴン P を作る'' と呼ぼう :
-ポリゴン P が同じ長さの2つの辺を持たず,
-ポリゴン P のすべての辺の長さが集合 S に含まれ, かつ
-集合 S がその他の値を含まない.
例えば :~
集合 {3, 4, 5} は 3, 4, 5, の長さの辺を持つポリゴン(三角形)を作る.~
集合 {6, 9, 11, 24} は 6, 9, 11, 24 の長さの辺を持つポリゴン(四角形)を作る.~
集合 {1, 2, 3} そして {2, 3, 4, 9} からはどんなポリゴンも作られない.
以下のように定義される数列 s を考えよう :
-s&sub{1}; = 1, s&sub{2}; = 2, s&sub{3}; = 3
-s&tex{_{n}}; = s&tex{_{n-1}}; + s&tex{_{n-3}}; [&tex{n}; > 3 のとき]
集合 {s&sub{1};, s&sub{2};, ..., s&tex{_{n}};} を U&tex{_{n}}; としよう. 例えば, U&sub{10}; = {1, 2, 3, 4, 6, 9, 13, 19, 28, 41}.~
少なくとも一つのポリゴンを作ることができる U&tex{_{n}}; の部分集合の個数を f(&tex{n};) としよう.~
例えば, f(5) = 7, f(10) = 501, そして f(25) = 18635853 となる.
f(10&sup{18};) の最後の9桁を求めよ.
![[PukiWiki]](recentchanges.png "[PukiWiki]")
