メインコンテンツへスキップ
見出し画像

最初だけ素数っぽい数列の一般項

    ※完全に記録用です。
     漸化式から一般項を求めるいい練習になりましたが。

    今回は以下のような数列を考えます。

    {an}=1,2,3,5,7,11,15,23,31,47,63,95,127,…\{a_n\}=1,2,3,5,7,11,15,23,31,47,63,95,127,…

    見ての通り、最初のほうは1と15を除き素数が並びます。47くらいまで数列を出して15を「?」にしておけばおそらく半数以上の人が13,17で迷うはずです。

    1. 数列の特徴

    まずは数列の特徴を軽く押さえておきます。
    どう見ても等間隔ではないので等差数列ではありませんし、素数も多数含まれているので等比数列もありえません。そこで各項の差を取ってみます。

    an=1,2,3,5,7,11,15,23,31,47,63,95,…より、a2−a1=1a3−a2=1a4−a3=2a5−a4=2a6−a5=4a7−a6=4a8−a7=8a9−a8=8a10−a9=16a11−a10=16a12−a11=32…\displaystyle {a_n}=1,2,3,5,7,11,15,23,31,47,63,95,…より、\\a_2-a_1=1\\a_3-a_2=1\\a_4-a_3=2\\a_5-a_4=2\\a_6-a_5=4\\a_7-a_6=4\\a_8-a_7=8\\a_9-a_8=8\\a_{10}-a_9=16\\a_{11}-a_{10}=16\\a_{12}-a_{11}=32\\…

    このようにすると、数列の特徴がよくわかります。言葉で説明すると、「1から始めて2回繰り返したら倍になるという法則で増える数列」です。

    2. 階差数列の一般項を求める(1)

    数列の差に関しての法則があれば階差数列を求めることができます。階差数列が求まれば、そこから元の数列の一般項を求められます(下記の補足参照)。

    ※以下、{an}\{a_n\}の階差数列を{bn}\{b_n\}とします。

    まずは{bn}\{b_n\}を書き出して、少し変形しておきます。

    {bn}=1,1,2,2,4,4,8,8,16,16,32,32,64,64,…=20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,…\displaystyle\{b_n\}=1,1,2,2,4,4,8,8,16,16,32,32,64,64,…\\=2^0,2^0,2^1,2^1,2^2,2^2,2^3,2^3,2^4,2^4,2^5,2^5,2^6,2^6,2^7,2^7,…

    指数が1回おきに1増えるので、floor関数(切り捨て)を使えば一般項は下のように書けます。

    bn=2⌊n−12⌋b_n=2^{\lfloor\frac{n-1}{2}\rfloor}

    n=1n=1のときは20=12^0=1、n=2n=2のときは⌊12⌋=⌊0.5⌋=0∴2⌊12⌋=1\lfloor\dfrac{1}{2}\rfloor=\lfloor0.5\rfloor=0\therefore2^{\lfloor\frac{1}{2}\rfloor}=1のように代入するとしっかりbnb_nが現れます。

    【補足】階差数列から元の数列の一般項を求める方法

    階差数列の定義より、bn=an+1−anよって、b1=a2−a1,b2=a3−a2,…より、a1+b1=a2,a2+b2=a3,…,an−1+bn−1=anここで、a2,a3,…,an−1にbnの式を代入すると、an=a1+b1+b2+b3+b4+…+bn−1b1+b2+…+bn−1をまとめると、an=a1+∑k=1n−1bkしたがって、∑k=1n−1bkを求めればanも求まる。\displaystyle 階差数列の定義より、b_n=a_{n+1}-a_n\\よって、b_1=a_2-a_1,b_2=a_3-a_2,…より、\\a_1+b_1=a_2,a_2+b_2=a_3,…,a_{n-1}+b_{n-1}=a_n\\ここで、a_2,a_3,…,a_{n-1}にb_nの式を代入すると、\\a_n=a_1+b_1+b_2+b_3+b_4+…+b_{n-1}\\b_1+b_2+…+b_{n-1}をまとめると、\\a_n=a_1+\sum_{k=1}^{n-1}{b_k}\\したがって、\sum_{k=1}^{n-1}{b_k}を求めればa_nも求まる。

    3. 階差数列の一般項を求める(2)

    bn=2⌊n−12⌋\displaystyle b_n=2^{\lfloor\frac{n-1}{2}\rfloor} がわかったのは良いですが、最終的にana_nを求めるためにはbnb_nの部分和を計算する必要があります。しかし、∑\sumの計算においてn乗の公式はありますが「n(小数を切り捨て)乗」という公式はありません(何なら切り捨てのfloor関数は初等関数ですらありません)。これを何とかするべく、式を変形します。

    まずは条件分岐の場合分けで考えます。
    n−1n-1が偶数、つまりnnが奇数の場合はn−12\dfrac{n-1}{2}をそのまま入れればよいですが、n−1n-1が奇数、つまりnnが偶数の場合は切り捨てになるのでn−12−0.5=n2−1\dfrac{n-1}{2}-0.5=\dfrac{n}{2}-1となります。この考え方を使うと、以下の式が導けます。

    bn={2n−12 (nは奇数)2n2−1 (nは偶数)\large b_n=\begin{cases}2^\frac{n-1}{2}  (nは奇数)\\[8pt]2^\frac{n}{2}-1  (nは偶数)\end{cases}

    これらを比較すると、nnが偶数の場合にのみ12\dfrac{1}{2}を引けばよいことになります(n−12−12=n−22=n2−1\dfrac{n-1}{2}-\dfrac{1}{2}=\dfrac{n-2}{2}=\dfrac{n}{2}-1)。

    ここで、次のような式を考えます。
    (1) : 1−(−1)n2 (2) : 1+(−1)n2\displaystyle (1)  :  \frac{1-(-1)^n}{2} (2)  :  \frac{1+(-1)^n}{2}
    (1)の式はnnに奇数を代入すると11、偶数を代入すると00を出力します。(2)の式はこの逆で、偶数を代入すると11、奇数を代入すると00と出力します。これは(−1)n(-1)^nがnnが奇数なら−1-1、nnが偶数なら11を出力するというように数式で数の偶奇を判別できることを利用しています。

    今回はnnが偶数の場合のみ12\dfrac{1}{2}を引きたいので、指数部分は、
    n−12−12⋅1+(−1)n2=2n−2−(1+(−1)n)4=2n−3−(−1)n4\displaystyle\frac{n-1}{2}-\frac{1}{2}\cdot\frac{1+(-1)^n}{2}=\frac{2n-2-(1+(-1)^n)}{4}=\frac{2n-3-(-1)^n}{4}
    12\frac{1}{2}を引くところに偶奇の判断を入れて掛けておけばどちらか一方のみ演算ができるという考え方です。

    したがって、初等関数で表した{bn}\{b_n\}の一般項は以下のようになります。

    bn=22n−3−(−1)n4\large b_n=2^{\frac{2n-3-(-1)^n}{4}}

    4. Σを計算する

    bnb_nが分かったので、いよいよana_nの一般項を求めていきます。まずは∑k=1n−1bk\displaystyle\sum_{k=1}^{n-1}{b_k}を求めます。
    ※指数部分が非常に見づらかったので数式部分は拡大で書いています
    ※mmは自然数、MMは2M+1,2M>02M+1,2M>0を満たす整数とします

    bk=22n−3−(−1)n4において、k=2m−1のときは22(2m−1)−3−(−1)2m−14=24m−2−3+14=2m−1k=2mのときは22⋅2m−3−(−1)2m4=24m−3−14=2m−1\displaystyle\large b_k=2^{\frac{2n-3-(-1)^n}{4}}において、\\k=2m-1のときは\\2^{\frac{2(2m-1)-3-(-1)^{2m-1}}{4}}=2^{\frac{4m-2-3+1}{4}}=2^{m-1}\\k=2mのときは\\2^{\frac{2\cdot2m-3-(-1)^{2m}}{4}}=2^{\frac{4m-3-1}{4}}=2^{m-1}
    このことから、このことから、
    ∑k=1n−1bkにおいてn−1の偶奇で分けると、n−1=2Mのとき∑k=1n−1bk=∑m=1M(b2m−1+b2m)=2∑m=1M2m−1=2(2M−1)=2M+1−2=2n+12−2n−1=2M+1のとき∑k=1n−1bk=∑m=1M(b2m−1+b2m)+b2M+1=2∑m=1M2m−1+2M=2M+1−2+2M=2⋅2M+2M−2=3⋅2M−2\displaystyle\large\sum_{k=1}^{n-1}{b_k}においてn-1の偶奇で分けると、\\n-1=2Mのとき\\\sum_{k=1}^{n-1}{b_k}=\sum_{m=1}^{M}{(b_{2m-1}+b_{2m})}=2\sum_{m=1}^{M}{2^{m-1}}\\=2(2^M-1)=2^{M+1}-2=2^{\frac{n+1}{2}}-2\\n-1=2M+1のとき\\\sum_{k=1}^{n-1}{b_k}=\sum_{m=1}^{M}{(b_{2m-1}+b_{2m})+b_{2M+1}}=2\sum_{m=1}^{M}{2^{m-1}}+2^M\\=2^{M+1}-2+2^M=2\cdot2^M+2^M-2=3\cdot2^M-2
    これをまとめると、これをまとめると、
    ∑k=1n−1bk={2n+12−1  (nは奇数)3⋅2n2−1−1  (nは偶数)\displaystyle\large \sum_{k=1}^{n-1}{b_k}=\begin{cases} 2^{\frac{n+1}{2}}-1   (nは奇数)\\ 3\cdot2^{\frac{n}{2}-1}-1   (nは偶数)\end{cases}

    5. 計算結果を1つにまとめる

    ∑k=1n−1bk={2n+12−1  (nは奇数)3⋅2n2−1−1  (nは偶数)\displaystyle\sum_{k=1}^{n-1}{b_k}=\begin{cases} 2^{\frac{n+1}{2}}-1   (nは奇数)\\ 3\cdot2^{\frac{n}{2}-1}-1   (nは偶数)\end{cases}が分かったので、次はこれを(−1)n(-1)^nを利用して一つの式にまとめます。今回は偶数、奇数どちらの式も利用します。ここで1つのテクニックとして、−2-2は共通しているので移項してから計算します(面倒な展開をしなくて済みます)。

    2+∑k=1n−1bk=2n+12⋅1−(−1)n2+3⋅2n2−1⋅1+(−1)n2=2n−12−2n−12⋅(−1)n+3⋅2n2−2+3⋅2n2−2⋅(−1)n=3⋅2n2−2+2n−12+(−1)n⋅(3⋅2n2−2−2n−12)∴ ∑k=1n−1bk=3⋅2n2−2+2n−12+(−1)n⋅(3⋅2n2−2−2n−12)−2\displaystyle 2+\sum_{k=1}^{n-1}{b_k}=2^{\frac{n+1}{2}}\cdot\frac{1-(-1)^n}{2}+3\cdot2^{\frac{n}{2}-1}\cdot\frac{1+(-1)^n}{2}\\[5pt]=2^{\frac{n-1}{2}}-2^{\frac{n-1}{2}}\cdot(-1)^n+3\cdot2^{\frac{n}{2}-2}+3\cdot2^{\frac{n}{2}-2}\cdot(-1)^n\\[5pt]=3\cdot2^{\frac{n}{2}-2}+2^{\frac{n-1}{2}}+(-1)^n\cdot(3\cdot2^{\frac{n}{2}-2}-2^{\frac{n-1}{2}})\\[5pt]\therefore  \sum_{k=1}^{n-1}{b_k}=3\cdot2^{\frac{n}{2}-2}+2^{\frac{n-1}{2}}+(-1)^n\cdot(3\cdot2^{\frac{n}{2}-2}-2^{\frac{n-1}{2}})-2

    6. 数列の一般項

    ∑k=1n−1bk\displaystyle\sum_{k=1}^{n-1}{b_k}が求まったので、2.の補足のやりかたでana_nを求めることができます。
    ※初項は最初に提示した数列からa1=1a_1=1とわかります

    an=a1+∑k=1n−1bk=1+∑k=1n−1bk=3⋅2n2−2+2n−12+(−1)n⋅(3⋅2n2−2−2n−12)−1\displaystyle a_n=a_1+\sum_{k=1}^{n-1}{b_k}=1+\sum_{k=1}^{n-1}{b_k}\\[5pt]=3\cdot2^{\frac{n}{2}-2}+2^{\frac{n-1}{2}}+(-1)^n\cdot(3\cdot2^{\frac{n}{2}-2}-2^{\frac{n-1}{2}})-1

    最終的な一般項は下のようになります。

    an=3⋅2n2−2+2n−12+(−1)n⋅(3⋅2n2−2−2n−12)−1\large a_n=3\cdot2^{\frac{n}{2}-2}+2^{\frac{n-1}{2}}+(-1)^n\cdot(3\cdot2^{\frac{n}{2}-2}-2^{\frac{n-1}{2}})-1

    最初の規則的な並びからは想像もできない複雑な式ですが、特殊な方法で漸化式を解くと大体こうなることが多い気がします。(−1)n(-1)^nは「2回に1回(階差数列が)増える」などということをいうときによく使われる条件分岐の項です。


    7. テクニック集

    (1) -1のn乗を利用した条件分岐

    1−(−1)n2:nが奇数なら1,偶数なら01+(−1)n2:nが奇数なら0,偶数なら1\displaystyle\frac{1-(-1)^n}{2}:nが奇数なら1,偶数なら0\\[8pt]\frac{1+(-1)^n}{2}:nが奇数なら0,偶数なら1

    一般に、A={f(n) (nが奇数)g(n) (nが偶数)\displaystyle A=\begin{cases}f(n)  (nが奇数)\\g(n)  (nが偶数)\\\end{cases} のとき、
    A=f(n)⋅1−(−1)n2+g(n)⋅1+(−1)n2\displaystyle A=f(n)\cdot\frac{1-(-1)^n}{2}+g(n)\cdot\frac{1+(-1)^n}{2}

    (2) Σの計算の偶奇分け

    ∑k=1nck\displaystyle \sum_{k=1}^{n}{c_k}において、ck=c2m−1+c2mc_k=c_{2m-1}+c_{2m}を利用することで計算できる場合がある。


    8. 数列の第50項までの数

    参考までに、数列の数を50項まで書いておきます。

    1, 2, 3, 5, 7,
    11, 15, 23, 31, 47,
    63, 95, 127, 191, 255,
    383, 511, 767, 1023, 1535,
    2047, 3071, 4095, 6143, 8191,
    12287, 16383, 24575, 32767, 49151,
    65535, 98303, 131071, 196607, 262143,
    393215, 524287, 786431, 1048575, 1572863,
    2097151, 3145727, 4194303, 6291455, 8388607,
    12582911, 16777215, 25165823, 33554431, 50331647

    5個ずつ区切っています。
    素数が多いのは奇数項は必ず2^m-1の形になるからかな?というのが私の見解です。

    【一般項を利用して数列の各項を出すpythonプログラム】

    def seq(n,list_flag=True):
        res = []
        for i in range(1,n+1):
            a = 3 * (2 ** (i/2 - 2)) + 2 ** ((i-1)/2)
            b = 3 * (2 ** (i/2 - 2)) - 2 ** ((i-1)/2)
            if list_flag == True:
                res.append(int(a + ((-1)**i)*b) - 1)
            else:
                print(int(a + ((-1)**i)*b) - 1)
        if list_flag == True:
            return res
    
    
    # seq(表示個数) で実行、そこまでの数列をリストで返す
    # ただし、第二引数はFalseを指定するとリストを返さずにprintで表示
    # (第二引数は初期値True,指定しなくても可)



    この記事が参加している募集

     
     
    数学とPythonが好きな人です。 主に数学と自作のPythonプログラムの解説記事を書いています。 最近はBVE関連にハマってます… X垢(主にBVE):https://x.com/__init__92435

    あなたへのおすすめ