よしたく blog

ITエンジニアとして自分が知らなかったことをまとめています

【Project Euler】Special Pythagorean tripletをPythonで解く

この問題をPythonで解いた。

#9 Special Pythagorean triplet - Project Euler

日本語の問題文はこちら

ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である.

a2 + b2 = c2 例えば, 32 + 42 = 9 + 16 = 25 = 52 である.

a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する. これらの積 abc を計算しなさい.

Problem 9 - PukiWiki

for a in range(1, 1000):
    for b in range(a + 1, 1000):
        c = 1000 - a - b
        if a < b and b < c and c * c == a * a + b * b:
            print(a * b * c)

【Python】itertoolモジュールのpermutations関数を使って順列を作る

itertoolモジュールのpermutations関数を使うと、簡単に順列を作ることができる。 permutationはなかなか見慣れない英単語だが、「順列、交換、置換、並べ換え」といった意味がある。パッと思い出せるぐらいには覚えておくと良さそう。

今回はpermutations関数を実行し、使い方や動きを確認する。

前提条件

Google Colab上で確認

このときのバージョンはPython 3.7.12

実行

エンジニアに親しみのあるプログラミング言語についてのランキングを作成する例とした。 permutations関数はiterableオブジェクトを引数に取る。そのため、language変数に3つの言語名を入れたリストを渡している。 これだけで順列を作成できる。

Python

language = ['Python', 'Ruby', 'Go']

import itertools
list(itertools.permutations(language))
[('Python', 'Ruby', 'Go'),
 ('Python', 'Go', 'Ruby'),
 ('Ruby', 'Python', 'Go'),
 ('Ruby', 'Go', 'Python'),
 ('Go', 'Python', 'Ruby'),
 ('Go', 'Ruby', 'Python')]

テーブル形式に変換すると、下記と同じデータになっている。

1位 2位 3位
Python Ruby Go
Python Go Ruby
Ruby Python Go
Ruby Go Python
Go Python Ruby
Go Ruby Python

permutations関数の2つめの引数に、これは取り出したい個数を入力する。今回は2と入力する。 指定することで ['Python', 'Ruby', 'Go']の3つの中から2つだけ取り出したいことを実現することができる。

language = ['Python', 'Ruby', 'Go']

import itertools
list(itertools.permutations(language,2))
[('Python', 'Ruby'),
 ('Python', 'Go'),
 ('Ruby', 'Python'),
 ('Ruby', 'Go'),
 ('Go', 'Python'),
 ('Go', 'Ruby')]
1位 2位
Python Ruby
Python Go
Ruby Python
Ruby Go
Go Python
Go Ruby

ちなみに、元の要素より大きい数を指定すると、空のオブジェクトが返る。 空のリストが表示されているのは、list関数で囲んでいるからである。

language = ['Python', 'Ruby', 'Go']

import itertools
list(itertools.permutations(language,4))
[]

【Project Euler】10001st primeをPythonで解く

この問題をPythonで解いた。

#7 10001st prime - Project Euler

日本語の問題文はこちら

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である. 10 001 番目の素数を求めよ.

Problem 7 - PukiWiki

import sympy

print(sympy.prime(10001))

【Project Euler】Largest product in a seriesをPythonで解く

この問題をPythonで解いた。

#8 Largest product in a series - Project Euler

日本語の問題文はこちら

次の1000桁の数字のうち, 隣接する4つの数字の総乗の中で, 最大となる値は, 9 × 9 × 8 × 9 = 5832である.

73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450 この1000桁の数字から13個の連続する数字を取り出して, それらの総乗を計算する. では、それら総乗のうち、最大となる値はいくらか.

EX 6桁の数123789から5個の連続する数字を取り出す場合, 12378と23789の二通りとなり, 後者の23789=3024が最大の総乗となる.

Problem 8 - PukiWiki

num = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'

from operator import mul
from functools import reduce

ans = []
for i in range(len(num)):
  ans.append(reduce(mul, list(map(int, num[i:i + 13]))) )
print(max(ans))

【Project Euler】Sum square differenceをPythonで解く

この問題をPythonで解いた。

#6 Sum square difference - Project Euler

日本語の問題文はこちら

最初の10個の自然数について, その二乗の和は,

12 + 22 + ... + 102 = 385 最初の10個の自然数について, その和の二乗は,

(1 + 2 + ... + 10)2 = 3025 これらの数の差は 3025 - 385 = 2640 となる.

同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ.

Problem 6 - PukiWiki

ans1 = 0
for i in range(1,101):
  ans1 += i ** 2
print(ans1)

ans2 = 0
for i in range(1,101):
  ans2 += i
ans2 = ans2 ** 2
print(ans2)

print(ans2 - ans1)

【Project Euler】Smallest multipleをPythonで解く

この問題をPythonで解いた。

#5 Smallest multiple - Project Euler

日本語の問題文はこちら

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.

では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

Problem 5 - PukiWiki

from math import gcd
from functools import reduce

def lcm(a,b):
    return a*b//gcd(a,b)

print(reduce(lcm, range(1,21)))

【Project Euler】Largest palindrome productをPythonで解く

この問題をPythonで解いた。

#4 Largest palindrome product - Project Euler

日本語の問題文はこちら

左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.

では, 3桁の数の積で表される回文数の最大値を求めよ.

Problem 4 - PukiWiki

ans = []

for a in range(999, 99, -1):
    for b in range(999, 99, -1):
        result = str(a * b)
        if result == result[::-1]:
            ans.append(int(result))

print((max(ans)))

【Project Euler】Largest prime factorをPythonで解く

この問題をPythonで解いた。

#3 Largest prime factor - Project Euler

日本語の問題文はこちら

13195 の素因数は 5, 7, 13, 29 である.

600851475143 の素因数のうち最大のものを求めよ.

Problem 3 - PukiWiki

N = 600851475143
i = 2
while i * i <= N:
  while N % i == 0:
    N //=  i
  i += 1
print(N)

【Project Euler】Even Fibonacci numbersをPythonで解く

この問題をPythonで解いた。

Problem 2 - Project Euler

日本語の問題文はこちら

フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 数列の項の値が400万以下のとき, 値が偶数の項の総和を求めよ.

Problem 2 - PukiWiki

sum,a,b, MAX = 0, 1, 2, 4000000
while b < MAX:
  if b % 2 == 0:
    sum += b
  a, b = b, a+b
print(sum)

【Project Euler】Multiples of 3 or 5をPythonで解く

この問題をPythonで解いた。

Problem 1 - Project Euler

日本語の問題文はこちら

10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる. 同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.

Problem 1 - PukiWiki

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