三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.
三角数 | P3,n=n(n+1)/2 | 1, 3, 6, 10, 15, ... |
四角数 | P4,n=n2 | 1, 4, 9, 16, 25, ... |
五角数 | P5,n=n(3n-1)/2 | 1, 5, 12, 22, 35, ... |
六角数 | P6,n=n(2n-1) | 1, 6, 15, 28, 45, ... |
七角数 | P7,n=n(5n-3)/2 | 1, 7, 18, 34, 55, ... |
八角数 | P8,n=n(3n-2) | 1, 8, 21, 40, 65, ... |
3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ.
- この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する
- それぞれ多角数である: 三角数 (P3,127=8128), 四角数 (P4,91=8281), 五角数 (P5,44=2882) がそれぞれ別の数字で集合に含まれている
- 4桁の数の組で上の2つの性質をもつはこの組だけである.
三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる6つの巡回する4桁の数からなる唯一の順序集合の和を求めよ.
問題の紹介が面倒なのでココより借用した。
まずは解けた自分を褒めてあげたい。最初の挑戦で律儀に全組み合わせを評価する手法を試みたが、当然のように全く計算が終わらず。これは腰を据えて考えなければならないということで、効率的な検索と評価の方法に悩む。
全体的な方針は以下;
最初に与えられた2桁から始まる多角数のリストを得るための関数を作りたいと考えた。実際はこれを関数ではなく連想リストにすることで効率的な検索を図った。
また、最終的な答えはサイクリックだと分かっているので、探索はどこから始めても良いだろうということで、八角数を与えて、そこから所望の数列が得られるか探すことを基本方針とした。
あとは下2桁から次の数を見つける連鎖が続く限り数をリストで繋いでいきつつ、n角数のnに重複が出たら打ち止めることにすると6連鎖が見つかる。重複を除外しているので7連鎖以降が見つかる可能性はない。そのようにして見つかった6連鎖の中から先頭と末尾がきちんとサイクルしていることを確認すればOK。findを使っているが、これは問題文より答えが1つしかないことが分かっているから使った。別にfilterを使っても計算時間が余計にかかる(リストの最後まで走査するため)だけで、同じ答えに辿り着く。
…などと書いているが、正解に辿り着くまで暇な細切れ時間を使いつつ5日ほど掛かってしまった。苦労したぶん解けた喜びも大きい。
大金星☆