Project Euler31〜35をpythonで解く

Problem 31

問題（英語）

In the United Kingdom the currency is made up of pound (£) and pence (p). There are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?
「 https://projecteuler.net/problem=31 」

問題（日本語）

イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である.

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

以下の方法で£2を作ることが可能である．

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

これらの硬貨を使って£2を作る方法は何通りあるか?
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2031 」

コード

val = 200
a_ = val // 1 + 1
b_ = val // 2 + 1
c_ = val // 5 + 1
d_ = val // 10 + 1
e_ = val // 20 + 1
f_ = val // 50 + 1
g_ = val // 100 + 1
h_ = val // 200 + 1
#[200],[100,100]
lenth = 2
ls_g0 = [[a,b,c,d,e,f] for a in range(a_) for b in range(b_) for c in range(c_) \
for d in range(d_) for e in range(e_) for f in range(f_) \
if a*1 + b*2 + c*5 + d*10 + e*20 + f*50 == 200]

val = 100
a_ = val // 1 + 1
b_ = val // 2 + 1
c_ = val // 5 + 1
d_ = val // 10 + 1
e_ = val // 20 + 1
f_ = val // 50 + 1
g_ = val // 100 + 1
h_ = val // 200 + 1

ls_g1 = [[a,b,c,d,e,f] for a in range(a_) for b in range(b_) for c in range(c_) \
for d in range(d_) for e in range(e_) for f in range(f_) \
if a*1 + b*2 + c*5 + d*10 + e*20 + f*50 == 100]

lenth += len(ls_g0) + len(ls_g1)

print(lenth)

val = 200

a_ = val // 1 + 1

b_ = val // 2 + 1

c_ = val // 5 + 1

d_ = val // 10 + 1

e_ = val // 20 + 1

f_ = val // 50 + 1

g_ = val // 100 + 1

h_ = val // 200 + 1

#[200],[100,100]

lenth = 2

ls_g0 = [[a,b,c,d,e,f] for a in range(a_) for b in range(b_) for c in range(c_) \

for d in range(d_) for e in range(e_) for f in range(f_) \

if a*1 + b*2 + c*5 + d*10 + e*20 + f*50 == 200]

val = 100

a_ = val // 1 + 1

b_ = val // 2 + 1

c_ = val // 5 + 1

d_ = val // 10 + 1

e_ = val // 20 + 1

f_ = val // 50 + 1

g_ = val // 100 + 1

h_ = val // 200 + 1

ls_g1 = [[a,b,c,d,e,f] for a in range(a_) for b in range(b_) for c in range(c_) \

for d in range(d_) for e in range(e_) for f in range(f_) \

if a*1 + b*2 + c*5 + d*10 + e*20 + f*50 == 100]

lenth += len(ls_g0) + len(ls_g1)

print(lenth)

考え方

難問。

再帰関数を使うと簡単に書けるらしい。

僕のやり方は全パターン試して合計が200になるか調べるというゴリゴリ系。

少しでもパターンを減らそうと、100円玉を何枚使うかで場合分けした。

（実際はペンスだが、面倒なので円で書く。）

実行時間は多分10分ぐらいはかかったと思う。

再帰関数

このページのコードをほぼ丸パクリさせて頂く。

https://qiita.com/cof/items/1a38e1303d3a7d84d05e

#参考「https://qiita.com/cof/items/1a38e1303d3a7d84d05e」
def count_methods(target, coins):
  if len(coins) == 0:
    return 1
  else:
    s = 0
    c = coins[0]
    q = (target // c) + 1
    for i in range(0,q):
      s += count_methods(target - c * i, coins[1:])
    return s

def main():
  TARGET = 200
  COINS = [200,100, 50, 20, 10, 5, 2]
  print(count_methods(TARGET,COINS))

main()

#count_methods(target,[]) = 1　（なぜなら1で表すのは1通りしかないから）
#count_methods(200,[2]) = 101 (101回for文を回すから。2を0枚~100枚使うパターンがある)
#count_methods(195,[2]) = 98
#count_methods(200,[5,2]) =

#参考「https://qiita.com/cof/items/1a38e1303d3a7d84d05e」

def count_methods(target, coins):

if len(coins) == 0:

return 1

else:

s = 0

c = coins[0]

q = (target // c) + 1

for i in range(0,q):

s += count_methods(target - c * i, coins[1:])

return s

def main():

TARGET = 200

COINS = [200,100, 50, 20, 10, 5, 2]

print(count_methods(TARGET,COINS))

main()

#count_methods(target,[]) = 1　（なぜなら1で表すのは1通りしかないから）

#count_methods(200,[2]) = 101 (101回for文を回すから。2を0枚~100枚使うパターンがある)

#count_methods(195,[2]) = 98

#count_methods(200,[5,2]) =

再帰関数は複雑で分かりにくい...。

ドミノ倒し、帰納法に近い考え方である。

なぜ再帰関数で表せるか

自作関数count_methodsは第一引数にtarget(合計金額) 、第一引数にcoins（使える硬貨のリスト）を入れると何通りの払い方があるか返してくれる関数。

もし、そういう関数があったと仮定する。

ここで大事なのはこれは仮定であって、具体的にどういう形の関数か、というのは二の次ということである。

金額が上の硬貨から何枚使うか決めていく。

実際にやってみよう。

count_methods(200,[200,100,50,20,10,5,2,1])

1	count_methods(200,[200,100,50,20,10,5,2,1])

を求めたい。

200円玉を0枚使う。

すると、次の問題に置き換わる。

count_methods(200,[100,50,20,10,5,2,1])

1	count_methods(200,[100,50,20,10,5,2,1])

100円玉を1枚使う。

すると、次の問題に置き換わる。

（200円-100円=100円なので、）

count_methods(100,[50,20,10,5,2,1])

1	count_methods(100,[50,20,10,5,2,1])

同様に50円玉を1枚、20円玉を0枚、10円玉を2枚、5円玉を0枚,2円玉を0枚（合計70円）使ったとしよう。

すると、次の問題に置き換わる。

（100円-70円=30円なので、）

count_methods(30,[1])

1	count_methods(30,[1])

これの意味は「30円を1円玉のみで支払うパターンは何通りありますか？」であり、もちろんこれは1円玉を30枚出す「1通り」である。

このようにして、関数の第二引数に渡すリストの長さを減らしていけば、最後に値が求まり、逆方向のドミノ倒しで元の値が求まる。

細かい説明は端折っているがだいたいこんな感じである。

僕も再帰関数を自在に操れるようになりたい。

Problem 32

問題（英語）

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.
「 https://projecteuler.net/problem=32 」

問題（日本語）

すべての桁に 1 から n が一度だけ使われている数をn桁の数がパンデジタル (pandigital) であるということにしよう: 例えば5桁の数 15234 は1から5のパンデジタルである.

7254 は面白い性質を持っている. 39 × 186 = 7254 と書け, 掛けられる数, 掛ける数, 積が1から9のパンデジタルとなる.

掛けられる数/掛ける数/積が1から9のパンデジタルとなるような積の総和を求めよ.

HINT: いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ.
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2032 」

コード

#a*b=c
def pandigital_9(a,b,c):
    if '0' in str(a)+str(b)+str(c):
        return False
    digit = [i for i in str(a)+str(b)+str(c)]
    digit_set = set(digit)
    if len(digit) == 9 and len(digit_set) == 9:
        return True
    else:
        return False

def main():
    tot = 0
    data = set()
    #4桁*1桁
    for a in range(1000,10000):
        for b in range(1,10):
            if pandigital_9( a , b ,a * b):
                #print('a,b,c:'+str(a)+','+str(b)+','+str(a*b))
                if not a*b in data:
                    tot += a*b
                    data.add(a*b)
    #3桁*2桁
    for a in range(100,1000):
        for b in range(10,100):
            if pandigital_9( a , b ,a * b):
                #print('a,b,c:'+str(a)+','+str(b)+','+str(a*b))
                if not a*b in data:
                    tot += a*b
                    data.add(a*b)
    print(tot)
    #print(data)

main()

#a*b=c

def pandigital_9(a,b,c):

if '0' in str(a)+str(b)+str(c):

return False

digit = [i for i in str(a)+str(b)+str(c)]

digit_set = set(digit)

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

return True

else:

return False

def main():

tot = 0

data = set()

#4桁*1桁

for a in range(1000,10000):

for b in range(1,10):

if pandigital_9( a , b ,a * b):

#print('a,b,c:'+str(a)+','+str(b)+','+str(a*b))

if not a*b in data:

tot += a*b

data.add(a*b)

#3桁*2桁

for a in range(100,1000):

for b in range(10,100):

if pandigital_9( a , b ,a * b):

#print('a,b,c:'+str(a)+','+str(b)+','+str(a*b))

if not a*b in data:

tot += a*b

data.add(a*b)

print(tot)

#print(data)

main()

考え方

結構綺麗に書けたコードだと思う。

product（積）の桁

productが5桁の場合、合計4桁の積で5桁は表わせないのでだめ。(99*99<100*100=10000)

productが3桁の場合、合計6桁の積で3桁は表わせないのでこれもだめ。

ということでproductは4桁。他は合計5桁。

pandigital_9の判定

掛けられる数をa,掛ける数をb(<a)、積をcとする。

a,b,cに0が含まれていたらそもそもFalse。

リストdigitにa,b,cの桁を全て入れる。

セット型のdigit_setにリストdigitをセット型化したものを入れる。

（つまり、重複する要素（桁）が一つだけになり、後は消去される。）

この時、次がpandigital_9の判定になっている。

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

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

リストdigitの長さ（要素の数）が9であり、かつ、セット型のdigit_setの長さも9である時、(a,b,c)が「pandigital_9」であると言える。

一見、

len(digit_set) == 9

1	len(digit_set) == 9

だけで十分に思えるが、実は不十分である。

僕たちが今欲しいのは、9桁全てが重複せずに9桁のまま残っている(a,b,c)だが、これだけでは重複した数を消した結果、偶然9桁になった10桁以上の(a,b,c)もTrueとなってしまう。

なので、

len(digit) == 9

1	len(digit) == 9

上の条件も必要である。

重複する積を除く

HINTにあるように、

HINT:いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ.

重複する積があるので、set型のdataに積を記録しておく。

重複の判定を次で行なっている。

a*b in data

1	a*b in data

今回はデータの大きさが少ないので関係ないが、set型なのでこの判定は高速（O(1)）である。

興味本位で

a,b,cの組みを全て出してみた。

a,b,c:1738,4,6952
a,b,c:1963,4,7852
a,b,c:138,42,5796
a,b,c:157,28,4396
a,b,c:159,48,7632
a,b,c:186,39,7254
a,b,c:198,27,5346
a,b,c:297,18,5346
a,b,c:483,12,5796

a,b,c:1738,4,6952

a,b,c:1963,4,7852

a,b,c:138,42,5796

a,b,c:157,28,4396

a,b,c:159,48,7632

a,b,c:186,39,7254

a,b,c:198,27,5346

a,b,c:297,18,5346

a,b,c:483,12,5796

重複する積を確認出来た。(5346と5796は2パターンある。)

Problem 33

問題（英語）

The fraction ⁴⁹/₉₈ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ⁴⁹/₉₈ = ⁴/₈, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, ³⁰/₅₀ = ³/₅, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.
「 https://projecteuler.net/problem=33 」

問題（日本語）

49/98は面白い分数である.「分子と分母からそれぞれ9を取り除くと, 49/98 = 4/8 となり, 簡単な形にすることができる」と経験の浅い数学者が誤って思い込んでしまうかもしれないからである. (方法は正しくないが，49/98の場合にはたまたま正しい約分になってしまう．)

我々は 30/50 = 3/5 のようなタイプは自明な例だとする.

このような分数のうち, 1より小さく分子・分母がともに2桁の数になるような自明でないものは, 4個ある.

その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ.
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2033 」

コード

from fractions import Fraction
#（分子、分母）を受け取り、分母、分子に同じ数を含むなど、条件に当てはまればTrueを返す関数
#例外 12/12(これはmain()で除外する),34/43,30/50
def judg(a,b):
    #0が含まれる
    if a % 10 == 0 or b % 10 == 0:
        return False
    #a=22など連番
    if a % 11 == 0 or b % 11 == 0:
        return False
    (l_a,l_b) = (str(a),str(b))
    #a=34,b=43など桁を入れ替えた値が一致
    if l_a == l_b[::-1]:
        return False
    for i in range(2):
        for j in range(2):
            if l_a[i] == l_b[j]:
                return True
    return False

#（分子,分母）を受け取り、同じ数字を消去し、約分した値を返す関数
#前提条件:judgでTrue
def simplify(a,b):
    (l_a,l_b) = (str(a),str(b))
    for i in range(2):
        for j in range(2):
            if l_a[i] == l_b[j]:
                common = l_a[i]
    l_a = l_a.strip(common)
    l_b = l_b.strip(common)
    return Fraction(int(l_a[0]),int(l_b[0]))

ls = []
#ls_2 = []
for top in range(10,100):
    for bot in range(10,100):
        if top >= bot:
            continue
        if judg(top,bot):
            if simplify(top,bot) == Fraction(top,bot):
                #ls_2.append([top,bot])
                ls.append(Fraction(top,bot))
ans = 1
#print(ls_2) #[[16, 64], [19, 95], [26, 65], [49, 98]]
for i in ls:
    ans *= i
print(ans.denominator) #100

from fractions import Fraction

#（分子、分母）を受け取り、分母、分子に同じ数を含むなど、条件に当てはまればTrueを返す関数

#例外 12/12(これはmain()で除外する),34/43,30/50

def judg(a,b):

#0が含まれる

if a % 10 == 0 or b % 10 == 0:

return False

#a=22など連番

if a % 11 == 0 or b % 11 == 0:

return False

(l_a,l_b) = (str(a),str(b))

#a=34,b=43など桁を入れ替えた値が一致

if l_a == l_b[::-1]:

return False

for i in range(2):

for j in range(2):

if l_a[i] == l_b[j]:

return True

return False

#（分子,分母）を受け取り、同じ数字を消去し、約分した値を返す関数

#前提条件:judgでTrue

def simplify(a,b):

(l_a,l_b) = (str(a),str(b))

for i in range(2):

for j in range(2):

if l_a[i] == l_b[j]:

common = l_a[i]

l_a = l_a.strip(common)

l_b = l_b.strip(common)

return Fraction(int(l_a[0]),int(l_b[0]))

ls = []

#ls_2 = []

for top in range(10,100):

for bot in range(10,100):

if top >= bot:

continue

if judg(top,bot):

if simplify(top,bot) == Fraction(top,bot):

#ls_2.append([top,bot])

ls.append(Fraction(top,bot))

ans = 1

#print(ls_2) #[[16, 64], [19, 95], [26, 65], [49, 98]]

for i in ls:

ans *= i

print(ans.denominator) #100

考え方

少し複雑で分かりづらい問題。

まず、自作関数judgで条件を絞り、自作関数simplifyで分子・分母の同じ数を消去する。

その値が元の値と一致する時、それをリストlsに追加していき、最後に全てを掛ける。

例外

以下を例外として、judgで弾く。

分母、分子が同じ値（これはmainの記述で弾く）
どちらかに0が含まれる
どちらかに連番（22など）が含まれる
分母の桁を入れ替えた値が分子に一致（a=34,b=43）

これらを弾くことで共通する数字は一つだけという前提でsimplifyが書ける。

Fraction

Fractionは分数を扱うクラス。

初めて使ったが、扱いやすくて便利

Problem 34

問題（英語）

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: As 1! = 1 and 2! = 2 are not sums they are not included.
「 https://projecteuler.net/problem=34 」

問題（日本語）

145は面白い数である. 1! + 4! + 5! = 1 + 24 + 120 = 145となる.

各桁の数の階乗の和が自分自身と一致するような数の和を求めよ.

注: 1! = 1 と 2! = 2 は総和に含めてはならない.
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2034 」

コード

import math
#import time

def fac_sum(n):
    tot = 0
    for i in str(n):
        tot += math.factorial(int(i))
    return tot

def main():
    #t1 = time.time()
    TOP = 1000000
    ans = 0
    #ls = []
    for i in range(3,TOP):
        if i == fac_sum(i):
            ans += i
            ls.append(i)
    print(ans) #40730
    #print(ls) #[145, 40585]
    #t2 = time.time()
    #print(t2-t1) #2.9976613521575928

main()

import math

#import time

def fac_sum(n):

tot = 0

for i in str(n):

tot += math.factorial(int(i))

return tot

def main():

#t1 = time.time()

TOP = 1000000

ans = 0

#ls = []

for i in range(3,TOP):

if i == fac_sum(i):

ans += i

ls.append(i)

print(ans) #40730

#print(ls) #[145, 40585]

#t2 = time.time()

#print(t2-t1) #2.9976613521575928

main()

考え方

シンプルな問題。

基本的にそのまま実装するだけ。

階乗は標準モジュールmathの関数factorialを使った。

上限

9! * 7 = 362880 * 7 < 10*(7-1) より7桁以上の数字は答えになり得ない。

よって最大は6桁（上限は999999）。

興味本位で

求めるのは和だが、条件に当てはまる数がどれくらいあるのか気になったため調べた。（コードではコメントアウトしている。）

すると、例の145の他には40585しか存在しなかった。

予想していたよりレアな性質だった。

Problem 35

問題（英語）

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?
「 https://projecteuler.net/problem=35 」

問題（日本語）

197は巡回素数と呼ばれる. 桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.

100未満には巡回素数が13個ある: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である.

100万未満の巡回素数はいくつあるか?
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2035 」

コード

import math

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [False] * 2 + [True] * (n-1)
    limit = int(math.sqrt(n))
    for i in range(2,limit+1):
        if prime[i]:
            for j in range(i*2,n+1,i):
                prime[j] = False
    return prime

def is_circular_prime(n):
    num = str(n)
    for i in range(len(num)):
        if not is_prime[int(num)]:
            return False
        num = num[1:] + num[0]
    return True


def main():
    TOP = 1000000
    global is_prime
    is_prime = get_sieve_of_eratosthenes(TOP)
    count = 0
    #ls = []
    for i in range(TOP):
        if is_circular_prime(i):
            #ls.append(i)
            count += 1
    print(count) #55
    #print(ls)
    #[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199,\
    # 311, 337, 373, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793,\
    # 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719,\
    # 93911, 99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393,\
    # 933199, 939193, 939391, 993319, 999331]

main()

import math

def get_sieve_of_eratosthenes(n):

if not isinstance(n, int):

raise TypeError('n is int type.')

if n < 2:

raise ValueError('n is more than 2')

prime = [False] * 2 + [True] * (n-1)

limit = int(math.sqrt(n))

for i in range(2,limit+1):

if prime[i]:

for j in range(i*2,n+1,i):

prime[j] = False

return prime

def is_circular_prime(n):

num = str(n)

for i in range(len(num)):

if not is_prime[int(num)]:

return False

num = num[1:] + num[0]

return True

def main():

TOP = 1000000

global is_prime

is_prime = get_sieve_of_eratosthenes(TOP)

count = 0

#ls = []

for i in range(TOP):

if is_circular_prime(i):

#ls.append(i)

count += 1

print(count) #55

#print(ls)

#[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199,\

# 311, 337, 373, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793,\

# 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719,\

# 93911, 99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393,\

# 933199, 939193, 939391, 993319, 999331]

main()

考え方

エラトネスのふるいで100万未満の素数をまず生成する。

巡回素数の判定をこの生成した素数リストで行う。

巡回素数の判定

次のコードで桁を1つずらす。

num = num[1:] + num[0]

1	num = num[1:] + num[0]

numはstr型の数字。

スライスでずらす方法をとった。

やってることを具体例で示す。

num = 'あいうえお'

の場合、

num[1:]　は　'いうえお'

num[0]　は　'あ'

なので、

num[1:] + num[0]　は　'いうえおあ'

となる。

（strとスライスって便利！）

後は、ずらした数字を素数かどうか調べ、一つでも違えば即Falseとする。

以上！

やっと記事が解答済み問題に追いついたので、ようやく再び問題に取り組める！

Problem40が解き終わったら、またまとめて記事にする。

次の記事↓

Project Euler 36〜40をpythonで解く