[Pythonプログラミング]プロジェクトオイラーの数学の問題をプログラムで解いてみよう : 乙Py先生のプログラミング教室

今回はプロジェクトオイラーの
数学の問題を解いてみました

解説動画はこちら

さて
プロジェクト・オイラー

は、英語で書かれた
数学的/コンピュータープログラミングの問題集です
リンクから色々な問題をみる事ができます

レオンハルト・オイラーは
18世紀の数学者・天文学者のことですね

今回はこれを解いていきたいと思います

数学の問題をプログラムを
駆使して解いてみましょう

問題を考えたい人は
動画を止めて考えてみて下さい

解答そのものは動画をご覧ください

問題1

1000未満の3か5の倍数の合計値を求めよ

・・・・・

・・・・

・・・

・・

・

解答1

比較的簡単な問題です

1000未満の数値の生成
3と5の倍数の判定
合計値を求める

これらが達成出来ていれば
解けると思います

sum([i for i in range(1,1000) if i%3==0 or i%5==0])

問題2

400万未満のフィボナッチ数で

偶数の物の合計値を求めよ

フィボナッチ数とは

1, 2, 3, 5, 8, 13, 21, 34, 55, 89 のように

どの数字も前２つの数字を足した数字のこと

・・・・・

・・・・

・・・

・・

・

解答2

フィボナッチ数を求める関数を作って
400万までのリストを作り
偶数のものを抜き出せば解けます

フィボナッチ数のリストを返す関数

# その数までのフィボナッチ数を求める
def fib(num):
    a , b , fib_l = 0 , 1 , []
    while b <= num:
        fib_l.append(b)
        a , b = b , a+b
    return fib_l

sum(([f for f in fib(4000000) if f%2==0]))

ジェネレーター式でも同様に出来ます

# ジェネレーター形式
def fib_gen(num):
    a , b = 1 , 1
    while b <= num:
        yield b
        a , b = b , a+b
        
sum(([f for f in fib_gen(4000000) if f%2==0]))

問題3

600851475143 の最大の素因数を求めよ

素因数分解をして、その最大値を求める

・・・・・

・・・・

・・・

・・

・

解答3

素因数分解をする手法はたくさん有りますが

中でも簡単な試し割り法を使って
素因数分解してみましょう

素因数分解しようとする整数nを
小さい順に割ってみて

割り切れるかどうかを調べる手法です

num = 600851475143

# 3から奇数で割っていく
f , a = 3 , []
while f * f <= num:
    
    # 割り切れたら素因数に採用
    if num % f == 0:
        a.append(f)
        
        # 次の数は、素因数で割った数で探す
        num //= f
    
    # 割り切れなければ次の素数へ
    else:
        f += 2
        
if num != 1:
    a.append(num)

# 素因数の組み合わせ
print(a)

# 素因数の最大値 
print(sorted(a,reverse=True)[0])

なお、ライブラリを用いれば
簡単に素因数分解できてしまいます

# ライブラリで素因数分解
import sympy

num = 600851475143
sympy.factorint(num)

問題4

2 つの 3 桁の数の積から作られる

最大の回文数値を求めよ

101*101 = 10201 のような

回文になる数値の最大値を求める

・・・・・

・・・・

・・・

・・

・

解答4

数値を文字列に直してひっくり返せば
回文の出来上がりです

answer = {}

for a in range(100,1000):
    for b in range(100,1000):
        s_num = str(a * b)
        if s_num == s_num[::-1]:
            answer[a * b] = [a,b]

for k,v in sorted(answer.items(),reverse=True):
    print(k,v)
    break

問題5

1 から 20 までのすべての数で割り切れる

最小の正の数を求めよ

最小公倍数を求める問題

・・・・・

・・・・

・・・

・・

・

解答5

最小公倍数は
次の様な計算式で求められます

最小公倍数 = 数値の積 ÷ 最大公約数

最大公約数を求めるには

ユークリッドの互除法を用います

ユークリッドの互除法は
2つの自然数の最大公約数を求める
手法の一つですが
比較的実装が楽です

# ユークリッドの互除法
# 最大公約数を求める
def gcd(a, b):
    if a == 0:
        return b
    m = b % a
    return gcd(m, a)

# 最小公倍数 = 数値の積 / 最大公約数
from functools import reduce

# 最小公倍数を計算する(2つ)
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

# 最小公倍数を計算する(複数)
def lcm(*nums):
    return reduce(lcm_base , nums, 1)


s = [i for i in range(2,21)]
# 最小公倍数をリストで求める際は * を付ける
lcm(*s)

python3.8以降なら
ライブラリでも求められます

# 最小公倍数を求める
import math
s = [i for i in range(2,21)]

# 最小公倍数をリストで求める際は * を付ける
math.lcm(*s)

問題6

100 個の自然数の

和の 2 乗と 2 乗の和の差を求めよ

例1,2,3

(1 + 2 + 3)^2 − (1^2 + 2^2 + 3^2)

= 36 −14

= 22

・・・・・

・・・・

・・・

・・

・

解答6

和の2乗は比較的楽に計算できますが
2乗の和は少しコツがいります

map関数は関数を引数に指定できるので
リストの要素に
関数を適応した結果を求めるのに
すごく役立ちます

nums = [i for i in range(1,101)]

# 和の2乗
sum_square = sum(nums) ** 2
print(sum_square)

# 2乗の和
sum_of_squares = sum(map(lambda n : n**2 , nums))
print(sum_of_squares)

# 2乗の和と和の2乗の差
print(sum_square - sum_of_squares)

問題7

10001 番目の素数を求めよ

・・・・・

・・・・

・・・

・・

・

解答7

素数を求めるのは流石に面倒くさいので
ライブラリの力を借りましょう

isprimeメソッドは
実行速度がめちゃくちゃ速いので
大抵の人が実装したものよりも
速いだろうと思います

# 素数を求めるライブラリ
from sympy import isprime

primes = [2,3]
for i in range(5,200001,2):
    if isprime(i):
        primes.append(i)
    if len(primes)==10001:
        answer = i
        print(answer)
        break

ライブラリでその数値までの
素数の個数を数える事も出来ます

# ライブラリで素数の個数を数える
from sympy import primepi

print(primepi(answer))

問題8

次の1000 桁の数の中で

最大の積を持つ隣接する13桁は何か

数値は下記をお使いください

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450

・・・・・

・・・・

・・・

・・

・

解答8

まずは文字列をデータ化しますが
きちんとゴミを取り除いておきましょう

文字列を数値に直して
計算すればOKです

総積を求めるのは
for文を使っても良いですが
reduce関数などを使って
まとめる事ができます

data = '''
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
'''.replace('\n','')

import operator
from functools import reduce

answer = {}
for i in range(0 , len(data)-12):
    nums = data[i : i+13]
    if '0' in nums:
        continue
    
    # 総積を求める
    a = reduce(operator.mul, [int(n) for n in nums],1)
    answer[a] = nums
    
for k,v in sorted(answer.items(),reverse=True):
    print('数値 :  {0} , 文字列 : {1}'.format(k,v))
    break

問題9

a < b < c で a + b + c = 1000である時

ピタゴラスのトリプレットとなる数値の

a * b * c の値を求める

ピタゴラスのトリプレットとは

a^2 + b^2 = c^2

・・・・・

・・・・

・・・

・・

・

解答9

a<b<c かつ a+b+c=1000 なので
abcの数値の最大値はおのずと決まってきます

あとはピタゴラスの定理のような
関係性になる数値を探し当てれば
それが答えです

# aの最大値は1000の3分の1より小さい
for a in range(1, 332):
    
    # bの最小値は a+1、最大値は 1000から a を引いた半分
    for b in range(a + 1 , (1000 - a)//2):
        c = 1000 - (a + b)
        if a**2 + b**2 == c**2:
            print(a * b * c , a , b , c)
            break
    else:
        continue
    break

さて、ここまでが今回の内容です
なかなか面白い問題ばかりですねえ

まだまだプロジェクトオイラーには
たくさんの問題が残っているので
これからも問題を解いていきたいと思います

それでは