Project Euler 36〜40をpythonで解く

Problem 36

問題（英語）

The decimal number, 585 = 1001001001₂ (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)
「 https://projecteuler.net/problem=36 」

問題（日本語）

585 = 10010010012 (2進) は10進でも2進でも回文数である.

100万未満で10進でも2進でも回文数になるような数の総和を求めよ.

(注: 先頭に0を含めて回文にすることは許されない.)
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2036 」

コード

#参考「https://qiita.com/umeda_takumi/items/29cf4ecd7f9c33f79336」(2進数について)
def symmetry(s):
    if s == s[::-1]:
        return True
    return False

def main():
    TOP = 1000000
    ans = sum([i for i in range(TOP) if symmetry(str(i)) and symmetry(format(i,'b'))])
    print(ans) #872187

main()

#参考「https://qiita.com/umeda_takumi/items/29cf4ecd7f9c33f79336」(2進数について)

def symmetry(s):

if s == s[::-1]:

return True

return False

def main():

TOP = 1000000

ans = sum([i for i in range(TOP) if symmetry(str(i)) and symmetry(format(i,'b'))])

print(ans) #872187

main()

考え方

2進数はこれが初登場？

今回はformat関数で2進数に変換した。

回文数の判定

Problem4でも出てきた回文数。

この判定にはstrをスライスで反転させて一致するか確認するのが簡潔で良い。

s == s[::-1]

1	s == s[::-1]

step数を-1にすることで、後ろから1つずつ並べてくれるので反転させることができる。

sum関数 + リスト内包表記

短く簡潔に書ける。

最初は、次のように書いていた。

tot = 0
    for i in range(TOP):
        if symmetry(str(i)) and symmetry(format(i,'b')):
            tot += i

tot = 0

for i in range(TOP):

if symmetry(str(i)) and symmetry(format(i,'b')):

tot += i

sum関数とリスト内包表記を使えばワンラインで書ける。

ans = sum([i for i in range(TOP) if symmetry(str(i)) and symmetry(format(i,'b'))])

1	ans = sum([i for i in range(TOP) if symmetry(str(i)) and symmetry(format(i,'b'))])

単純なfor,if,totはsum,[]（リスト内包表記）で書くように心がけたい。

Problem 37

問題（英語）

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
「 https://projecteuler.net/problem=37 」

問題（日本語）

3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).

右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.

注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2037 」

コード

import math

def isPrime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    m = math.floor(math.sqrt(n)) + 1
    for p in range(3, m, 2):
        if n % p == 0:
            return False
    return True

def isTruncatable(n):
    for i in range(len(str(n))):
        if i == 0:
            if not isPrime(n):
                return False
        else:
            l_n = int(str(n)[i:])
            r_n = int(str(n)[:-i])
            if not isPrime(l_n) or not isPrime(r_n):
                return False
    return True

def main():
    num = 11
    ans = 0
    count = 0
    NUM_OF_PRIME = 11
    ##ls = []
    while count < NUM_OF_PRIME:
        if isTruncatable(num):
            ans += num
            count += 1
            ##ls.append(num)
        num += 1
    print(ans) #748317
    ##print(ls) #[23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]

main()

import math

def isPrime(n):

if n < 2:

return False

if n == 2:

return True

if n % 2 == 0:

return False

m = math.floor(math.sqrt(n)) + 1

for p in range(3, m, 2):

if n % p == 0:

return False

return True

def isTruncatable(n):

for i in range(len(str(n))):

if i == 0:

if not isPrime(n):

return False

else:

l_n = int(str(n)[i:])

r_n = int(str(n)[:-i])

if not isPrime(l_n) or not isPrime(r_n):

return False

return True

def main():

num = 11

ans = 0

count = 0

NUM_OF_PRIME = 11

##ls = []

while count < NUM_OF_PRIME:

if isTruncatable(num):

ans += num

count += 1

##ls.append(num)

num += 1

print(ans) #748317

##print(ls) #[23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]

main()

考え方

自作関数isPrime

今回は上限が分からないのでエラトネスのふるいは不適切。

素直に毎回素数判定をする。（少し遅い）

切り詰め可能(truncatable)素数の判定

以下のコードで切り詰めをする。

l_n = int(str(n)[i:])
r_n = int(str(n)[:-i])

1 2	l_n = int(str(n)[i:]) r_n = int(str(n)[:-i])

l_nが左、r_nが右から切り詰めたもの。

iが切り詰める桁数。

やはり、str型+スライスの組み合わせは使いやすい。

切り詰めた数に対して素数判定を行い、一つでも素数でない数が出てきたらFalseとする。

最後まで生き残ったらTrue。

Problem 38

問題（英語）

Take the number 192 and multiply it by each of 1, 2, and 3:

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?
「 https://projecteuler.net/problem=38 」

問題（日本語）

192 に 1, 2, 3 を掛けてみよう.

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

積を連結することで1から9のパンデジタル数 192384576 が得られる. 192384576 を 192 と (1,2,3) の連結積と呼ぶ.

同じようにして, 9 を 1,2,3,4,5 と掛け連結することでパンデジタル数 918273645 が得られる. これは 9 と (1,2,3,4,5) との連結積である.

整数と (1,2,...,n) (n > 1) との連結積として得られる9桁のパンデジタル数の中で最大のものはいくつか?
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2038 」

コード

#類題P32
def pandigital_9(num,ls):
    l_product = [str(num * i) for i in ls]
    #concatenated_product(連結積)
    global conc_pro
    conc_pro = ''.join(l_product)
    if '0' in conc_pro:
        return False
    digit = [i for i in conc_pro]
    digit_set = set(digit)
    if len(digit) == 9 and len(digit_set) == 9:
        return True
    else:
        return False

def main():
    ans = 0
    for n in range(2,10):
        ls = list(range(1,n+1))
        #桁数
        digit = 9 // n
        for num in range( 10**(digit-1) , 10**digit ):
            if pandigital_9(num,ls):
                if int(conc_pro) > ans:
                    ans = int(conc_pro)
                    ##interest = (num,ls)
    print(ans) #932718654
    ##print(interest) #(9327, [1, 2])

main()

#類題P32

def pandigital_9(num,ls):

l_product = [str(num * i) for i in ls]

#concatenated_product(連結積)

global conc_pro

conc_pro = ''.join(l_product)

if '0' in conc_pro:

return False

digit = [i for i in conc_pro]

digit_set = set(digit)

if len(digit) == 9 and len(digit_set) == 9:

return True

else:

return False

def main():

ans = 0

for n in range(2,10):

ls = list(range(1,n+1))

#桁数

digit = 9 // n

for num in range( 10**(digit-1) , 10**digit ):

if pandigital_9(num,ls):

if int(conc_pro) > ans:

ans = int(conc_pro)

##interest = (num,ls)

print(ans) #932718654

##print(interest) #(9327, [1, 2])

main()

考え方

num = 192, ls = [1,2,3]

と、それぞれをnum,lsとして説明する。

numの桁数

numの桁数（digit）はlsの長さ（n）で決まる。

結論から言うと、

digit = 9 // n

1	digit = 9 // n

で求まる。

(//は余りありの割り算の商を求めるもの。9//2 -> 4)

これは確認していけば分かる。

(1,2)の時は、4桁→5桁で合計9桁しかありえない。

(1,2,3)の時は、9//3 = 3 で、3桁→3桁→3桁で合計9桁しかありえない。

以降も同様である。

m桁の数字を生成

digit =m 桁の数字は以下で生成できる。

range( 10**(digit-1) , 10**digit )

1	range( 10(digit-1) , 10digit )

pandigital_9の判定

これはProblem32で作ったものをほぼそのまま採用。

Project Euler31〜35をpythonで解く

len(digit) == 9 and len(digit_set) == 9

1	len(digit) == 9 and len(digit_set) == 9

上で判定する。

joinメソッド

listの要素をstr型として一つに結合する時はjoinメソッドが便利。

l = ['あ','い','う','え','お']
s = ''.join(l)
print(s)

l = ['あ','い','う','え','お']

s = ''.join(l)

print(s)

実行結果:

あいうえお

あいうえお

グローバル変数

自作関数pandigital_9内の変数conc_pro(concatenated_product(連結積))はmain関数でも再び使いたいので、グローバル変数とする。

関数内の変数は本来その関数の中でのみ呼び出し可能だが、グローバル変数はある関数で使ったのち、別の関数でも呼びだすことが出来る。

以下のように書くことでグローバル変数とすることができる。

global conc_pro

1	global conc_pro

興味本位で

最大の時の、numとlsを調べてみた。

(9327, [1, 2])

1	(9327, [1, 2])

答えには関係ないが興味本位で知りたい情報を求めるためのコードには、「##」でコメントアウトしている。

Problem 39

問題（英語）

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?
「 https://projecteuler.net/problem=39 」

問題（日本語）

辺の長さが {a,b,c} と整数の3つ組である直角三角形を考え, その周囲の長さを p とする. p = 120のときには3つの解が存在する:

{20,48,52}, {24,45,51}, {30,40,50}

p ≤ 1000 のとき解の数が最大になる p はいくつか?
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2039 」

コード

import itertools

#和がNになる3個の整数の組を返す関数
def combination_of_3numbers_totalN(n):
    ls_n = list(range(n+1))
    result = []
    for l in itertools.combinations_with_replacement(ls_n,2):
        l = list(l)
        (num1,num2) = (l[0],l[1])
        num3 = n - (num1+num2)
        if num3 < 0 :
            continue
        #num3がnum1,num2の少なくともどちらか一方より小さい時、\
        #すでにその組み合わせは出てるのでスルー
        if num3 < num1 or num3 < num2:
            continue
        l.append(num3)
        result.append(l)
    return result

#print(combination_of_3numbers_totalN(10))
#[[0, 0, 10], [0, 1, 9], [0, 2, 8], [0, 3, 7], [0, 4, 6], [0, 5, 5], [1, 1, 8],\
# [1, 2, 7], [1, 3, 6], [1, 4, 5], [2, 2, 6], [2, 3, 5], [2, 4, 4], [3, 3, 4]]

def is_Pythagorean_triplet(a,b,c):
    return a*a + b*b == c*c

def main():
    TOP = 1000
    ans = 0
    max_lenth = 0
    for p in range(TOP+1):
        ls = [l for l in combination_of_3numbers_totalN(p) if not 0 in l and is_Pythagorean_triplet(l[0],l[1],l[2])]
        length = len(ls)
        if length > max_lenth:
            ans = p
            max_lenth = length
            ##max_ls = ls
    print(ans) #840
    ##print(max_lenth) #8
    ##print(max_ls) #[[40, 399, 401], [56, 390, 394], [105, 360, 375], [120, 350, 370], [140, 336, 364], [168, 315, 357], [210, 280, 350], [240, 252, 348]]

main()

import itertools

#和がNになる3個の整数の組を返す関数

def combination_of_3numbers_totalN(n):

ls_n = list(range(n+1))

result = []

for l in itertools.combinations_with_replacement(ls_n,2):

l = list(l)

(num1,num2) = (l[0],l[1])

num3 = n - (num1+num2)

if num3 < 0 :

continue

#num3がnum1,num2の少なくともどちらか一方より小さい時、\

#すでにその組み合わせは出てるのでスルー

if num3 < num1 or num3 < num2:

continue

l.append(num3)

result.append(l)

return result

#print(combination_of_3numbers_totalN(10))

#[[0, 0, 10], [0, 1, 9], [0, 2, 8], [0, 3, 7], [0, 4, 6], [0, 5, 5], [1, 1, 8],\

# [1, 2, 7], [1, 3, 6], [1, 4, 5], [2, 2, 6], [2, 3, 5], [2, 4, 4], [3, 3, 4]]

def is_Pythagorean_triplet(a,b,c):

return a*a + b*b == c*c

def main():

TOP = 1000

ans = 0

max_lenth = 0

for p in range(TOP+1):

ls = [l for l in combination_of_3numbers_totalN(p) if not 0 in l and is_Pythagorean_triplet(l[0],l[1],l[2])]

length = len(ls)

if length > max_lenth:

ans = p

max_lenth = length

##max_ls = ls

print(ans) #840

##print(max_lenth) #8

##print(max_ls) #[[40, 399, 401], [56, 390, 394], [105, 360, 375], [120, 350, 370], [140, 336, 364], [168, 315, 357], [210, 280, 350], [240, 252, 348]]

main()

考え方

実行時間が1分ぐらいかかってしまった。

main

和がpになるa,b,c(a<=b<=c)の組み合わせを全て生成して、それらがピタゴラス数か地道に判定していく方法を取った。

他の方のコードでいいと思ったのがこちら。

Project Euler 39「整数の直角三角形」

この方のコードはまずピタゴラス数の組a,b,cを生成してから求めるもので、こちらのアプローチの方が無駄がなくて早い。

itertools

iteartoolsは何かと便利なライブラリ。

色々できるが、直積（デカルト積）、順列、組み合わせなどが特に便利。

今回は「重複組み合わせ」というものを使った。

import itertools
ls = [0,1,2,3]
#重複組み合わせ
for tpl in itertools.combinations_with_replacement(ls,2):
    print(tpl)

import itertools

ls = [0,1,2,3]

#重複組み合わせ

for tpl in itertools.combinations_with_replacement(ls,2):

print(tpl)

実行結果:

(0, 0)
(0, 1)
(0, 2)
(0, 3)
(1, 1)
(1, 2)
(1, 3)
(2, 2)
(2, 3)
(3, 3)

(0, 0)

(0, 1)

(0, 2)

(0, 3)

(1, 1)

(1, 2)

(1, 3)

(2, 2)

(2, 3)

(3, 3)

a=bも考慮する組み合わせを生成する。

itertoolsはその名の通り、イテレータを生成する。

詳しくはこのページなどをご参考なさってください。

Pythonで階乗、順列・組み合わせを計算、生成

Problem 40

問題（英語）

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021...

It can be seen that the 12^th digit of the fractional part is 1.

If d_n represents the n^th digit of the fractional part, find the value of the following expression.

d₁ × d₁₀ × d₁₀₀ × d₁₀₀₀ × d₁₀₀₀₀ × d₁₀₀₀₀₀ × d_1000000
「 https://projecteuler.net/problem=40 」

問題（日本語）

正の整数を順に連結して得られる以下の10進の無理数を考える:

0.123456789101112131415161718192021...

小数第12位は1である.

dnで小数第n位の数を表す. d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000 を求めよ.
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2040 」

コード

import math

def main():
    TOP = 1000000
    digit = ''.join([str(i) for i in range(TOP)])
    ans = 1
    for i in range(int(math.log10(TOP)) + 1):
        ans *= int(digit[10 ** i])
    print(ans)

main()

import math

def main():

TOP = 1000000

digit = ''.join([str(i) for i in range(TOP)])

ans = 1

for i in range(int(math.log10(TOP)) + 1):

ans *= int(digit[10 ** i])

print(ans)

main()

考え方

久々に比較的優しい問題。

logを初めて使った。

上限

小数第100万位までしか必要ないので、整数を100万まで繋げる必要はない。

しかし、そこまで時間のかかる作業でもないし、減らしたとしてもオーダーが1つ下がる程度でモチベを感じなかったので、100万まで整数を繋げることにした。

対数（log）

最後の

d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000

1	d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000

を求める時のコードが簡潔にならずに戸惑った。

まず、100万(=TOP)は10^6だから10^0,10^1,...,10^6番目を調べるので、

for i in range(6+1):

1	for i in range(6+1):

と書きたいが、この6が何を表すのか分かりにくくなってしまう。

プログラミングのコードで僕が心がけていることの一つが「いきなり意味が分からない定数を出さない」である。

なので、本来の意味の次のコードに書き換えた。

for i in range(int(math.log10(TOP)) + 1):

1	for i in range(int(math.log10(TOP)) + 1):

Project Euler 36〜40をpythonで解く

Problem 36

問題（英語）

問題（日本語）

コード

考え方

回文数の判定

sum関数 + リスト内包表記

Problem 37

問題（英語）

問題（日本語）

コード

考え方

自作関数isPrime

切り詰め可能(truncatable)素数の判定

Problem 38

問題（英語）

問題（日本語）

コード

考え方

numの桁数

m桁の数字を生成

pandigital_9の判定

joinメソッド

グローバル変数

興味本位で

Problem 39

問題（英語）

問題（日本語）

コード

考え方

main

itertools

Problem 40

問題（英語）

問題（日本語）

コード

考え方

上限

対数（log）

以上！