質問の箱と球の問題をPythonで解いてみました。(^_^;
やっぱり、箱と球の問題というより、「約数の個数」の問題といった方がいいかも知れません。(^_^;
1から100までの番号が書かれた箱がある。箱には球が5個ずつ入っている。次の操作で球を取り出す。
操作 1:2の倍数が書かれた箱から1つ取り出す
操作 2:3の倍数が書かれた箱から1つ取り出す
操作 3:4の倍数が書かれた箱から1つ取り出す
…
操作99:100の倍数が書かれた箱から1つ取り出す
問題:最後の操作のあと、球が3個入っている箱は、いくつありますか?
ちなみに、数学的には、1〜100までのうち、1を除く約数が2つのもの、すなわち、約数の個数が3つのものになっています。それで、結局、素数の平方数を見つければいいことになるようです。(^_^;
2×3×5=30<100<2×3×5×7=210なので、題意の自然数Mは、高々3つの素数a,b,cとそれぞれの指数x,y,zを使って、次のよう書ける。
このとき、その約数の個数Nは、
N=(x+1)(y+1)(z+1)
となります。題意から、約数の個数が3つなので、
(x+1)(y+1)(z+1)=3
これを満たす整数解は、x≧y≧zとすると、
(x,y,z)=(2,0,0)
よって、題意の自然数Mは、次式のようになって素数の平方数となることがわかります。
● BallsInBoxes1.py
# coding: UTF-8 # BallsInBoxes1.py from time import time def main(): tm=time() # Timer Start # 箱をbox[1]〜box[100]まで用意。box[0]はダミー box = [5]*101; box[0] = 0 for i in range(2,101): for j in range(1,101): if j%i==0: box[j]-=1; ## print(box) hit = [] for i in range(101): if box[i]==3: hit.append(i) print(hit) print(u"∴%d"%len(hit)) print("Runtime : %.3f [sec]"%(time()-tm)) # Timer Stop & Disp if __name__ == '__main__': main()
●実行結果
[4, 9, 25, 49] ∴4 Runtime : 0.002 [sec]
※参考URL
●約数 - Wikipedia
●約数の個数の求め方!素因数分解すれば一発で求まる!
●受験算数の「約数の個数」の問題をPythonで解いてみた。
●受験算数の「約数の個数」の問題をPythonで解いてみた。(2)