今回はプロジェクトオイラーの
数学の問題を解いてみました
解説動画はこちら
さて
プロジェクト・オイラー
は、英語で書かれた
数学的/コンピューター プログラミングの問題集です
リンクから色々な問題をみる事ができます
レオンハルト・オイラーは
18世紀の数学者・天文学者のことですね
今回はこれを解いていきたいと思います
1000未満の3か5の倍数の合計値を求めよ
・・・・・
・・・・
・・・
・・
・
解答1
比較的簡単な問題です
1000未満の数値の生成
3と5の倍数の判定
合計値を求める
これらが達成出来ていれば
解けると思います
1, 2, 3, 5, 8, 13, 21, 34, 55, 89 のように
どの数字も前2つの数字を足した数字のこと
解答2
フィボナッチ数を求める関数を作って
400万までのリストを作り
偶数のものを抜き出せば解けます
フィボナッチ数のリストを返す関数
ジェネレーター式でも同様に出来ます
解答3
素因数分解をする手法はたくさん有りますが
なお、ライブラリを用いれば
簡単に素因数分解できてしまいます
回文になる数値の最大値を求める
解答4
数値を文字列に直してひっくり返せば
回文の出来上がりです
解答5
最小公倍数は
次の様な計算式で求められます
最小公倍数 = 数値の積 ÷ 最大公約数
python3.8以降なら
ライブラリでも求められます
(1 + 2 + 3)^2 − (1^2 + 2^2 + 3^2)
= 36 −14
= 22
解答6
和の2乗は比較的楽に計算できますが
2乗の和は少しコツがいります
map関数は関数を引数に指定できるので
リストの要素に
関数を適応した結果を求めるのに
すごく役立ちます
解答7
素数を求めるのは流石に面倒くさいので
ライブラリの力を借りましょう
isprimeメソッドは
実行速度がめちゃくちゃ速いので
大抵の人が実装したものよりも
速いだろうと思います
ライブラリでその数値までの
素数の個数を数える事も出来ます
解答8
解答9
a<b<c かつ a+b+c=1000 なので
abcの数値の最大値はおのずと決まってきます
あとはピタゴラスの定理のような
関係性になる数値を探し当てれば
それが答えです
さて、ここまでが今回の内容です
なかなか面白い問題ばかりですねえ
まだまだプロジェクトオイラーには
たくさんの問題が残っているので
これからも問題を解いていきたいと思います
それでは
数学の問題を解いてみました
解説動画はこちら
さて
プロジェクト・オイラー
は、英語で書かれた
数学的/コンピューター プログラミングの問題集です
リンクから色々な問題をみる事ができます
レオンハルト・オイラーは
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つの数字を足した数字のこと
・・・・・
・・・・
・・・
・・
・
解答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つの自然数の最大公約数を求める
手法の一つですが
比較的実装が楽です
ユークリッドの互除法は
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 乗の和の差を求めよ
和の 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関数などを使って
まとめる事ができます
きちんとゴミを取り除いておきましょう
文字列を数値に直して
計算すれば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
さて、ここまでが今回の内容です
なかなか面白い問題ばかりですねえ
まだまだプロジェクトオイラーには
たくさんの問題が残っているので
これからも問題を解いていきたいと思います
それでは
コメントする