Pythonで整数1~1億の総和を求める 【Pythonで数学】
はじめに
業務未経験で就職活動中にとある企業のコーディングテストを受けたことがある。 当時はPHPの書籍を1周したぐらいでプログラミングの知識はほとんどなかった。結果問題を一つも解くことができなかったのだ。その時の問題が1~1億数千の和を求めるものだった。今となってはそう難しいことではないが、Pythonなら簡潔に解を求めることができるのでメモ✅
余談ですが筆者は文系で数学に弱い(-_-;)
数学 1から100の総和を求める
億に行く前に一旦は100で練習をしてみる。
結論1から100の総和は5050。
求め方だが、総和ならまだしも1,3,5,7,9と飛び飛びの数字の問題が出題されたときにグヌヌ(-_-;)とならないようにまずは数学的アプローチから確認する。
等差数列の一般項の公式
等差数列ってなんだっけ????
例) 1, 5, 9, 13, 17, 21, ⋯
等差数列とは隣り合う2項の差が常に一定の数列のこと。後に登場する公差はこの(4)のこと。
じゃあ一般項ってなんだっけ????
数列 an の第n項 an が n の式で表されるとき,これを数列anの一般項 という。
初項 a,公差 d の等差数列 an の一般項は
an = a+(n−1)d
(第n項)=(初項)+(n-1)×(公差)
1, 5, 9, 13, 17, 21, ⋯ とした時に第4項の値を求めてみる。
Pythonで実行してみる。
a = 1 # 初項
n = 4 # 第4項
d = 4 # 交差
result = int(a + (n - 1) * d)
print(result)
# 13
13を求めることができた。
等差数列の和の公式
本題に近づくとする。
初項から第 n 項までの等差数列の和を Sn とする。
① 初項 a,末項 l,項数 n のとき
Sn=12n(a+l)
このように表せる。
これをPythonで実行してみる。
a = 1 # 初項
l = 100 # 末項
n = 100 # 項数
result = int((n / 2) * (a + l))
print(result)
# 5050
1から100の総和5050の値を得ることができた。
② 初項 a,公差 d,項数 n のとき
Sn = 1/2n{2a+(n−1)d}
このように表せる。 これをPythonで実行してみる。
a = 1 # 初項
d = 1 # 公差
n = 100 # 項数
result = int((0.5 * n) * (2 * a + (n - 1) * d))
print(result)
# 5050
こちらも 1から100の総和5050の値を得ることができた。
表をつかったアプローチ
1 | 2 | 3 | ・・・ | 98 | 99 | 100 |
---|---|---|---|---|---|---|
100 | 99 | 98 | ・・・ | 3 | 2 | 1 |
表で見たときに上下足すと101。これが100個あるから10100。10100は二列分の和なので半分にすると5050
正直これが文系にも分かりやすい。
※台形や折り返しなど視覚的なアプローチは今回は割愛させてもらう。
Python 関数 range
さあ、この記事もメイン部分だ。ここでも一旦1から100の総和
result = sum(range(1,101))
print(result)
# 5050
まさかの1行だった。
メインイベント、1~1億の総和を求める。
result = sum(range(1,100000001))
print(result)
# 5000000050000000
以下検算。
a = 1 # 初項
d = 1 # 公差
n = 100000000 # 項数
result = int((0.5 * n) * (2 * a + (n - 1) * d))
print(result)
# 5000000050000000
A. 5000000050000000
終わりに
数学を知っていることに大きな優位性を 書籍にも出ているがPythonで中学数学、Pythonで高校数学などを試してみたい。
他の言語だとJavaScriptとPerl、PHPで試してみたがこのぐらい大きい桁になると実行時間のほうが気になった。Java C言語など比較検証を後日行ってみようと思う。