プロジェクトオイラー19

プロジェクトオイラーの問題19をPython3を使って解きました。
問題
Problem 19 - Project Euler
1901年1月1日から2000年12月31日までで、月の初めが日曜日である日数を求めなさいという問題です。上記問題ページにいくつかヒントがありますが、Pythonでは日付に関するdatetimeモジュールがあるのでヒントは必要ありません。datetimeモジュールを使って毎年毎月の１日が日曜日かどうかを判定していくだけです。

import time
start = time.time()
from datetime import date
ans = 0
for i in range(1901, 2001):
    for j in range(1, 13):
        if date(i, j, 1).weekday() == 6:
            ans += 1
print(ans)
print(time.time()-start)

プロジェクトオイラー23

プロジェクトオイラーの問題23をPython3で解きました。
問題
Problem 23 - Project Euler
問題は、２つの過剰数（自身を除く約数の和が、自分自身より大きい自然数のこと）の和で書き表すことのできない自然数の総和を求めなさいというものでした。ヒントとして、28124以上の全ての自然数は２つの過剰数の和で表されることが与えられていました。そこで、28123以下の自然数で、２つの過剰数の和で表せない自然数をリスト化し、総和をとるプログラムを書きました。

import time
start = time.time()

def divs_sum(S):
    '''約数の和（自分自身は除く）'''
    s = 1
    for i in range(2, int(S**0.5 + 1)):
        if S % i == 0:
            s += i + int(S / i)
    if S**0.5 == int(S**0.5):
        s -= int(S**0.5)
    return s

def abundant(N):
    '''Nが過剰数かどうか'''
    if divs_sum(N) > N:
        return 1
    else:
        return 0

ab = [n for n in range(12, 28112) if abundant(n)]
'''28111以下の番号で過剰数のものを格納'''

l = [0] + [1] * 28123
'''0-28123までのリストを用意'''

for i in ab:
    '''2つの過剰和で書ける整数のl-リスト番号は0にする'''
    for j in [num for num in ab if num >= i]:
        if i+j < 28124:
            l[i+j] = 0

s = 0
for i in range(28124):
    '''2つの過剰和で書けなかった整数を足していく'''
    if l[i]:
        s += i

print(s)
print(time.time()-start)

計算時間は酷い有様でした。

プロジェクトオイラー48

プロジェクトオイラーの97を解いていたところ、ゴリ押しで説いていた問題48が綺麗に解けたので解答を書きます。Python3で解きました。
問題
Problem 48 - Project Euler

問題は簡単で、

の下10桁を求めなさいというものです。

解答

import time
start = time.time()
n = 0 #下10桁を表す
'''
n^n = n * n * \cdot * nとみて、for文を作り、 n^nの下10桁を残す。
これを1から1000まで動かして和をとり、最後に再び下10桁を残す。
'''
for i in range(1, 1001):
    m = 1
    for j in range(i):
        m = (m * i) % 10**10
    n += m
n = n % (10**10)
print(n)
print(time.time()- start)

プロジェクトオイラー30

ProjectEulerの問題30をPython3を使って解きました。
問題
Problem 30 - Project Euler

この問題は、自然数nで、
n = nの各桁の数字の5乗の和
となるものを見つけ、全て足し合わせなさいという問題です。コンピュータに上の式を満たす自然数を計算させるだけで良いのですが、上限を定めないといつまでも終わりません。そこで大雑把にまず、10^n > 9^5 ×n となる自然数 n を見つけます。この n が上限になることは明らかです。後はプログラムを書くだけ。

import time
start = time.time()
n = 1 #n桁の整数 = 各桁の整数の5乗の和　となり得る桁数nの上限
while 10**n <= (9**5) * n:
    n += 1
'''
上を実行するとn <= 6だとわかる
'''
integers = [(a, b, c, d, e, f) \
            for a in range(10) \
            for b in range(10) \
            for c in range(10) \
            for d in range(10) \
            for e in range(10) \
            for f in range(10) ] #6桁までの整数を表す
answer = -1 #問の答え(1 = 1^5 を除く)
for a, b, c, d, e, f in integers: #整数 = 各桁の整数の5乗の和となる数を見つけて足すぜ！
    if 100000*a + 10000*b + 1000*c + 100*d + 10*e + f == a**5 + b**5 + c**5 + d**5 + e**5 + f**5:
        answer += 100000*a + 10000*b + 1000*c + 100*d + 10*e + f
print(answer)
print(time.time() - start)

プロジェクトオイラー22

プロジェクトオイラーの22をPython3を使って解きました。
問題

projecteuler.net

この問題はもうウルトラ簡単です。

import time
start = time.time()
names = input().split('')
names.sort()
sum_of_iden_nums = 0
for name in names:
    iden_num = 0
    for i in range(len(name)):
        iden_num += ord(name[i]) - 64
    iden_num = iden_num *(names.index(name) + 1)
    sum_of_iden_nums += iden_num
print(sum_of_iden_nums)
print(time.time() - start)

結果

プロジェクトオイラー18

プロジェクトオイラーの問題18をPythonで解きました。

projecteuler.net

全てのルートを探索し、その中から目当てのものを見つけるのが最も考え方としてシンプルだと思うのですが、それだと、15!通り調べなければならないため、時間がかかります。（たぶん）そこで、

動的計画法 - Wikipedia

を用いてコードを書きました。

import time
data = [input().split(' ') for i in range(15)] #a given data
start = time.time()
j = 14
while j > 0:
    for i in range(j):
        data[j-1][i] = int(data[j-1][i]) +  max(int(data[j][i]), int(data[j][i+1]))
    j += -1
print(data[0][0])
print(time.time() - start)

入れるデータは、

です。
今回から実行するのにかかった時間も計算してみました。

プロジェクトオイラー16

プロジェクトオイラーの問題16をPython3で解きました。

projecteuler.net

この問題も大きな数字を扱うんですが、Pythonでは大きな数字に困ることはないので、計算させるだけです。Pythonつよい。

N = int(input())
large_number_str = list(str(2 ** N))
large_number_int = [int(number) for number in large_number_str]
print(sum(large_number_int))