Pythonで特定の漸化式のn番目の項を検索します

bnと呼ばれる数列があるとすると、これはb1=1やbn+1 / bn=2nのような漸化式を使用して表されます。与えられたnのlog2（bn）の値を見つける必要があります。

したがって、入力が6の場合、出力はlog2（bn）=（n *（n-1））/ 2 =（6 *（6-1））/ 2 =15

この関係を次のように解くことで、この問題を解くことができます-

b _{n + 1} / b _n =2 ⁿ

b _n / b _n-1 =2 ^n-1

…

b ₂ / b ₁ =2 ¹ 、上記のすべてを掛けると、次のようになります

（b _{n + 1} / b _n ）。（b _n / b _n-1 ）……（b ₂ / b ₁ ）=2 ^{n +（n-1）+………。+ 1}

したがって、b _{n + 1} / b ₁ =2 ^{n（n + 1）/ 2}

1 + 2 +3+として………。 +（n-1）+ n =n（n + 1）/ 2

したがって、b _{n + 1} =2 ^{n（n + 1）/ 2} * b ₁ ;初期値b₁を想定しています。 =1

したがって、b _{n + 1} =2 ^{n（n + 1）/ 2}

nを（n + 1）に置き換えると、次のようになります。

b _n =2 ^{n（n-1）/ 2}

両側のログを取ることで、私たちは得ます、

log ₂ （b _n ）=n（n-1）/ 2

例

理解を深めるために、次の実装を見てみましょう-

def add_upto_n(n):
   res = (n * (n - 1)) / 2
   return res
n = 6
print(int(add_upto_n(n)))

入力

6

出力

15