Problem 012
三角数の数列は自然数の和で表わされ, 7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である.
角数の最初の10項は:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
となる.
最初の7項について, その約数を列挙すると, 以下のとおり.
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
これから, 7番目の三角数である28は, 5個より多く約数をもつ最初の三角数であることが分かる.
では, 500個より多く約数をもつ最初の三角数はいくつか.
Answer 012 (Python)
数学的な面白さもない完全な力技でごめんなさい。
もう少し考えたい...
import functools
from collections import defaultdict
class Problem12:
PRIME = []
def main(self, num):
i, s, count = 0, 0, 0
while(count < num):
i += 1
s += i
primes = self.primeFactorize(s)
count = self.divisorCount(primes)
print(s)
def primeFactorize(self, num):
data = []
i = 1
while(i < num ** (1/2)):
i += 1
if i in self.PRIME:
pass
elif self.isPrime(i):
self.PRIME.append(i)
else:
continue
if num == i:
break
if num % i == 0:
data.append(i)
num //= i
i -= 1
data.append(num)
return data
def isPrime(self, num):
for i in self.PRIME:
if i > num ** (1/2):
return True
if num % i == 0:
return False
return True
def divisorCount(self, primeList):
data = defaultdict(lambda: 0)
for i in primeList:
data[i] += 1
return functools.reduce(lambda x, y: x * y, (i + 1 for i in data.values()))
import sys
if __name__ == '__main__':
num = 500
if len(sys.argv) == 2:
num = sys.argv[1]
p = Problem12()
p.main(int(num))
(参考) Project Euler とは
Project Euler はプログラミングで数学の問題を解くサイトです。問題は600問以上あるので、勉強に使うのも良し、楽しむのも良しです。
サイトに登録すれば、解答を submit することができ、その場であっているか判定してくれます。
また、問題だけであれば、日本語に翻訳された Wiki もあるのでそちらを見ながらやると捗ると思います。