PythonでConnell（コネル）数列のn番目の項を求める方法

数 n が与えられたとき、Connell（コネル）数列の n 番目の項を求める問題を考えてみましょう。まずは、この数列がどのような規則で構成されているのかを確認します。

Connell数列とは？

Connell数列は、「奇数・偶数を交互に、取り出す個数を1つずつ増やしながら」並べていく数列です。生成ルールは次のとおりです。

• 最初に、奇数を1つ取ります：1
• 次に、偶数を2つ取ります：2, 4
• 続いて、奇数を3つ取ります：5, 7, 9
• その次は、偶数を4つ取ります：10, 12, 14, 16
• 以降も同じパターンを繰り返します

つまり、Connell数列は「1, 2, 4, 5, 7, 9, 10, 12, 14, 16, …」という形になります。例として、入力が12の場合、出力は21です。

解法の考え方

各グループにはその番号と同じ個数の要素が含まれるため、m グループ目までの累積要素数は三角数 m×(m+1)/2 になります。この性質を利用すると、n 番目の要素がどのグループに属するかを特定できます。さらに、各グループ内の値は公差2の等差数列になっているため、グループ末尾の値から逆算することで目的の項を求められます。

具体的な手順は以下のとおりです。

• i を 1 で初期化する
• (i × (i + 1) / 2) の商が n + 1 未満である間、i を 1 ずつ増やす
• idx := i × (i + 1) / 2（商のみ＝整数除算）とする
• num := i² とする
• num − 2 × (idx − n − 1) を結果として返す

Pythonでの実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, n):
        i = 1
        while (i * (i + 1) // 2) < n + 1:
            i += 1
        idx = i * (i + 1) // 2
        num = i**2
        return num - 2 * (idx - n - 1)

ob = Solution()
print(ob.solve(12))

入力

12

出力

21