人生、Python、三角数

【イントロ】
　日々の生活に疲れてくると、どうでもいいこと考えてしまいますよね。
たとえば、
「もっと別の生き方があったのではないか？」、
とか
「この自然数は何個の三角数で表せるんだろうか？」
とか。
　そこで本記事では、Pythonを使用して「任意の自然数が何個の三角数で表せるか」判定するプログラムを作成したので、公開します。

【方法】
　プログラムはPythonで書きました。本当はRustを使って書きたかったんですがそもそも書き方で悩むとかいう別問題があったので、アルゴリズムを考えて書きやすいPythonを採用しました。
　そもそも、問題意識のきっかけは”yukicoder”さんのこちらの問題「No.634 硬貨の枚数1」です。要は「任意の自然数が何個の三角数で表せるのか判定しましょう」という問題です。大きな数だと一体何個必要なのか想像もつきません。そこで小さな数で試しに実験してみたのが図1です。

図1、１０までの自然数を三角数で分解した場合

・・・どうも必要な個数が3個を超えない予感がしてきました。
検索してみると、こういう定理(またはこちら)
「すべての自然数はたかだかｍ個のｍ角数で表せる」
が存在することがわかりました。やっぱ数学ってすごい。。。
この定理のお陰で与えられた問題は「任意の自然数は三角数１，２，３個で分割できるか判定する」と読み替えることが出来ます。この問題をPythonで解くこととしました。

【結果】
作成したプログラムは下記のとおりです。
もっとスマートな書き方があると思いますが、素人なので許してください。

import math

#三角数の計算
def triangle(n):
    p = n*(n+1)/2
    return p

#与えられたN以下の最大の三角数を満たすqを返す
def kirisute(n):
    p=(-1+math.sqrt(1+8*n))/2
    q=math.floor(p)
    return q

#与えられたnまでの三角数のリストを返す
def trilist(n):
    list=[]
    for i in range(1,n+1):
        x=triangle(i)
        list.append(x)
    
    return list

#与えられた自然数ｎを三角数何個で表記できるか判定する関数
def hantei(n):
    p=kirisute(n) #n以下の最大の三角数を示すｐを返す
    list=trilist(p) #1からn以下の最大の三角数までのリストを作る

    list.reverse() #1からｎ以下の最大の三角数までのリストの逆順
    
    #三角数何個で表記できるか場合分け
    if n in list: #ｎが三角数の場合、当然1個である
        print(1)
        
    else: #三角数2個または3個必要な場合
        for i in list:#ｎが三角数2個で表される場合
            if i>=n/2 and n-i in list: #三角数2個で合わされる場合iがn/2を下回ることはない
                print(2)
                break
            else: #iがn/2を下回る、またはn-iがリストになかった場合
                pass
            
        else: #上記のどちらでもなければ三角数3個必要である
             print(3)

print(hantei(100)) #判定の実行

一応これで、必要な三角数を判定できています。実際に１～１０と１００について出力してみたのが図２です。

図２、人力とPythonで必要な三角数の個数を判定した結果

ということで、おそらく正解していると思われます。
ただひとつの問題はこのプログラムを実行すると、
「”必要な個数”
None」
という謎の「None」が出力されてしまう点です。
ナンなんだ一体。。。（誰か助けて。。。

【まとめ】
　とはいえ、「任意の自然数は三角数１，２，３個で分割できるか判定する」Pythonプログラムを書けました。
達成感。。。

次の目標はRustへの移植です！

＊追記：print(hantei(100))、hantei()がreturnで返してないのが問題と教えてもらいました。print()を外すか、hantei()をreturnにするとNoneが消えました。