*[[Problem 463:http://projecteuler.net/problem=463]] 「奇妙な漸化式」 [#fc50fc86] すべての正整数に対し関数 '''f''' が以下のように定義されている: - '''f'''(1) = 1 - '''f'''(3) = 3 - '''f'''(2'''n''') = '''f'''('''n''') - '''f'''(4'''n'''+1) = 2'''f'''(2'''n'''+1) - '''f'''('''n''') - '''f'''(4'''n'''+3) = 3'''f'''(2'''n'''+1) - 2'''f'''('''n''') &ref(p463_sum.png); '''f'''('''n''') を関数 '''S'''('''n''') と定義する. '''S'''(8) = 22, そして '''S'''(100) = 3604. '''S'''(3&sup{37};) を求めよ. 回答は末尾9桁を答えよ.