Project Euler26〜30をpythonで解く

Problem 26

問題（英語）

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that ¹/₇ has a 6-digit recurring cycle.

Find the value of d < 1000 for which ¹/_d contains the longest recurring cycle in its decimal fraction part.
「 https://projecteuler.net/problem=26 」

問題（日本語）

単位分数とは分子が1の分数である. 分母が2から10の単位分数を10進数で表記すると次のようになる.

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

0.1(6)は 0.166666... という数字であり, 1桁の循環節を持つ. 1/7 の循環節は6桁ある.

d < 1000 なる 1/d の中で小数部の循環節が最も長くなるような d を求めよ.
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2026 」

コード1

#参考:「https://note.nkmk.me/python-list-index/」
#リストlに検索したいxが何番目に含まれているか返す関数。
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
#print(my_index_multi([0,1,2,3,1]),1) → [1,4]

#単位分数の分母nを受け取り、サイクルの周期を返す関数
def digit_cycle(n):
    remainder = 1
    remainder_list = [1]
    while True:
        remainder = (remainder * 10) % n
        if remainder == 0:
            return 0
        remainder_list.append(remainder)
        if remainder in remainder_list[:-1]:
            ls = my_index_multi(remainder_list, remainder)
            return ls[1] - ls[0]
            #indexを記録する変数を用意した方が簡潔に書けた。

def main():
    max_digit_cycle = 0
    TOP = 1000
    for d in range(2,1000):
        if digit_cycle(d) > max_digit_cycle:
            max_digit_cycle = digit_cycle(d)
            max_d = d
    print(max_d) #983 答え
    print(max_digit_cycle) #982

main()

#参考:「https://note.nkmk.me/python-list-index/」

#リストlに検索したいxが何番目に含まれているか返す関数。

def my_index_multi(l, x):

return [i for i, _x in enumerate(l) if _x == x]

#print(my_index_multi([0,1,2,3,1]),1) → [1,4]

#単位分数の分母nを受け取り、サイクルの周期を返す関数

def digit_cycle(n):

remainder = 1

remainder_list = [1]

while True:

remainder = (remainder * 10) % n

if remainder == 0:

return 0

remainder_list.append(remainder)

if remainder in remainder_list[:-1]:

ls = my_index_multi(remainder_list, remainder)

return ls[1] - ls[0]

#indexを記録する変数を用意した方が簡潔に書けた。

def main():

max_digit_cycle = 0

TOP = 1000

for d in range(2,1000):

if digit_cycle(d) > max_digit_cycle:

max_digit_cycle = digit_cycle(d)

max_d = d

print(max_d) #983 答え

print(max_digit_cycle) #982

main()

コード2

#単位分数の分母nを受け取り、サイクルの周期を返す関数
def digit_cycle(n):
    (i,remainder) = (1,1)
    remainder_list = []
    while True:
        remainder = (remainder * 10) % n
        if remainder == 0:
            return 0
        remainder_list.append(remainder)
        if remainder in remainder_list[:-1]:
            length = i - (remainder_list.index(remainder) + 1)
            return length
            #indexを記録する変数を用意した方が簡潔に書けた。
        i += 1

def main():
    max_digit_cycle = 0
    TOP = 1000
    for d in range(2,1000):
        if digit_cycle(d) > max_digit_cycle:
            max_digit_cycle = digit_cycle(d)
            max_d = d
    print(max_d) #983 答え
    print(max_digit_cycle) #982

main()

#単位分数の分母nを受け取り、サイクルの周期を返す関数

def digit_cycle(n):

(i,remainder) = (1,1)

remainder_list = []

while True:

remainder = (remainder * 10) % n

if remainder == 0:

return 0

remainder_list.append(remainder)

if remainder in remainder_list[:-1]:

length = i - (remainder_list.index(remainder) + 1)

return length

#indexを記録する変数を用意した方が簡潔に書けた。

i += 1

def main():

max_digit_cycle = 0

TOP = 1000

for d in range(2,1000):

if digit_cycle(d) > max_digit_cycle:

max_digit_cycle = digit_cycle(d)

max_d = d

print(max_d) #983 答え

print(max_digit_cycle) #982

main()

考え方

意外と数学力が必要な問題。

循環の判定

まず、何を持って「循環した」と判断出来るか。

一見、桁に同じ数字が出てきた時に「循環した」と言えそうだが、そうではない。

例えば1/17なんかがその例。

1/17 = 0.(0588235294117647)

1/17は上のように16桁周期になり、同じ数字が出てきても循環しない。

つまり、小数の桁の見た目では判断できない。

余りで判定

ならどうするかというと余り（mod）で判定すれば良い。

d=7の例で考える。

1/7 = 0.(142857)

これは、次のように書ける。

割られる数 = 余り,商（割る数はd=7）

1 = 1,0

10 = 3,1

30 = 2,4

20 = 6,2

60 = 4,8

40 = 5,5

50 = 1,7

10 = 3,1

これは筆算で小数を求めることと同じことをやっている。

注目すべきは右側の商ではなく、左側の余りである。

赤字にしている「3」で初めて余りが一致したので、そこで循環すると分かる。

循環の桁数は一致した余りの距離（間の桁数）で求まる。

循環の桁数の取得

remainder_listに余りを追加していく。

余りが一致した際に、「循環の桁数＝一致した余りの距離」が成り立つのだが、これを求めるのが少々厄介だった。

コード1とコード2でそれぞれ別の方法を取っている。

単にindexを取得すると...

一致する要素のindexを調べるにはindexメソッドがあるが、これは一致する「最初の」値のインデックスしか分からない。

l = [0,1,2,3,1]
print(l.index(1))

1 2	l = [0,1,2,3,1] print(l.index(1))

実行結果:

1

my_index_multi

コード1で使った関数。

参考「 Pythonのリストの要素のインデックス（何番目か）を取得」

このサイトを参考にして自作関数を書いた。（丸パクリ）

l = [0,1,2,3,1]
print(my_index_multi(l,1))

1 2	l = [0,1,2,3,1] print(my_index_multi(l,1))

実行結果:

[1,4]

[1,4]

この関数を使えば検索した値と一致する全ての要素のインデックスを取得出来る。

よって、余りの距離は、求めたインデックスの差を計算することで分かる。

ls = my_index_multi(remainder_list, remainder)
return ls[1] - ls[0]

1 2	ls = my_index_multi(remainder_list, remainder) return ls[1] - ls[0]

インデックスを記録する変数を導入する

この方法を取ったのがコード2。

indexメソッドでは一致する最初の要素のインデックスしか分からなかったので、二つ目の要素のインデックスを求めるための変数を用意すれば良い。

コード2の変数iがそれである。

これは、この方のコードを参考にした。

Project Euler 26「逆数の循環節その1」

関数を定義するより簡潔でいい感じ。

main関数

このコードからmain関数を書くようにした。

Problem 27

問題（英語）

うまくコピー出来なかった。

「 https://projecteuler.net/problem=27 」

問題（日本語）

オイラーは以下の二次式を考案している:

n^2 + n + 41.

この式は, n を0から39までの連続する整数としたときに40個の素数を生成する. しかし, n = 40 のとき 402 + 40 + 41 = 40(40 + 1) + 41 となり41で割り切れる. また, n = 41 のときは 412 + 41 + 41 であり明らかに41で割り切れる.

計算機を用いて, 二次式 n^2 - 79n + 1601 という式が発見できた. これは n = 0 から 79 の連続する整数で80個の素数を生成する. 係数の積は, -79 × 1601 で -126479である.

さて, |a| < 1000, |b| ≤ 1000 として以下の二次式を考える (ここで |a| は絶対値): 例えば |11| = 11 |-4| = 4である.

n^2 + an + b

n = 0 から始めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数 a, b の積を答えよ.
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2027 」

コード

#time:3.810328960418701
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 Euler_formula_val(a,b,n):
    return n * n + a * n + b

#a,bを受け取り、素数が何回続くかを返す関数。
def Euler_formula_len(a,b):
    n = 0
    while True:
        if not isPrime(Euler_formula_val(a,b,n)):
            return n
        n += 1

def main():
    TOP = 1000
    max_lenth = 0
    for a in range(-999,TOP):
        for b in range(-1000,TOP+1):
            if Euler_formula_len(a,b) > max_lenth:
                max_lenth = Euler_formula_len(a,b)
                ans = a * b #-61*971=-59231
    print(ans)

main()

#time:3.810328960418701

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 Euler_formula_val(a,b,n):

return n * n + a * n + b

#a,bを受け取り、素数が何回続くかを返す関数。

def Euler_formula_len(a,b):

n = 0

while True:

if not isPrime(Euler_formula_val(a,b,n)):

return n

n += 1

def main():

TOP = 1000

max_lenth = 0

for a in range(-999,TOP):

for b in range(-1000,TOP+1):

if Euler_formula_len(a,b) > max_lenth:

max_lenth = Euler_formula_len(a,b)

ans = a * b #-61*971=-59231

print(ans)

main()

考え方

さすがオイラー、面白いこと考えるよなぁ。

関数をうまく定義すればすっきり書ける。

range関数の範囲指定

for a in range(-999,TOP):
    for b in range(-1000,TOP+1):

1 2	for a in range(-999,TOP): for b in range(-1000,TOP+1):

aとbが負の場合も検討しなくてはならないので、range関数の範囲指定で第一引数にstartの数を指定する。

この範囲指定は便利なので覚えておくべき。

range(start, stop, step)

1	range(start, stop, step)

3つ引数を指定すると飛び飛び（step）の値を生成出来る。

print(list(range(100,200,10)))

1	print(list(range(100,200,10)))

実行結果:

[100, 110, 120, 130, 140, 150, 160, 170, 180, 190]

1	[100, 110, 120, 130, 140, 150, 160, 170, 180, 190]

問題はよく読もう...

絶対値を問われていると思ってしばらく-をつけ忘れて、うーんと唸っていた。

問題はよく読もう。

Problem 28

問題（英語）

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20 7  8 9 10
19 6 1  2 11
18 5  4 3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?
「 https://projecteuler.net/problem=28 」

問題（日本語）

1から初めて右方向に進み時計回りに数字を増やしていき, 5×5の螺旋が以下のように生成される:

21 22 23 24 25

20 7 8 9 10

19 6 1 2 11

18 5 4 3 12

17 16 15 14 13

両対角線上の数字の合計は101であることが確かめられる.

1001×1001の螺旋を同じ方法で生成したとき, 対角線上の数字の和はいくつか?
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2028 」

コード

#対角線の数
num = 1
#index
i = 0
#次の数との差
add_num = 0
tot = 0
SIZE = 1001

while num < SIZE * SIZE:
    num += add_num
    tot += num
    if i % 4 == 0:
        add_num += 2
    i += 1
print(tot)

#対角線の数

num = 1

#index

i = 0

#次の数との差

add_num = 0

tot = 0

SIZE = 1001

while num < SIZE * SIZE:

num += add_num

tot += num

if i % 4 == 0:

add_num += 2

i += 1

print(tot)

考え方

たくさんの視点がありそうな問題。

僕は対角線の数の差に注目した。

1,3,5,7,9,13,17,21,25

1	1,3,5,7,9,13,17,21,25

最初は2ずつ増えていき、次に4ずつ増えていっている。

観察すると、+2,+4,+6,+8,... と増えていくことが分かる。

よって、4つごとに足す数（add_num）に2を足していけば良い。

加速度のような考え方である。

「右上の数」=「(1辺の長さ)^2」が成り立っているので、最後の項は1001^2になる。（この値を上限とする。）

Problem 29

問題（英語）

Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
「 https://projecteuler.net/problem=29 」

問題（日本語）

2 ≤ a ≤ 5 と 2 ≤ b ≤ 5について, ab を全て考えてみよう:

22=4, 23=8, 24=16, 25=32

32=9, 33=27, 34=81, 35=243

42=16, 43=64, 44=256, 45=1024

52=25, 53=125, 54=625, 55=3125

これらを小さい順に並べ, 同じ数を除いたとすると, 15個の項を得る:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

2 ≤ a ≤ 100, 2 ≤ b ≤ 100 で同じことをしたときいくつの異なる項が存在するか?
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2029 」

コード

def main():
    TOP = 100
    data = set()
    for a in range(2,TOP+1):
        for b in range(2,TOP+1):
            data.add(a ** b)
    print(len(data))
main()

def main():

TOP = 100

data = set()

for a in range(2,TOP+1):

for b in range(2,TOP+1):

data.add(a ** b)

print(len(data))

main()

考え方

「重複しない」というキーワードが出てきた時はセット型が適切である。

この問題でセット型を知る。

1行でも書ける。

print(len({ a ** b for a in range(2, 100+1) for b in range(2, 100+1) }))

1	print(len({ a ** b for a in range(2, 100+1) for b in range(2, 100+1) }))

リスト内包表記の[ ]を{ }にするとset型の内包表記になるらしい。

参考「 Project Euler 29「個別のべき乗」」

Problem 30

問題（英語）

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.
「 https://projecteuler.net/problem=30 」

問題（日本語）

驚くべきことに, 各桁を4乗した数の和が元の数と一致する数は3つしかない.

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

ただし, 1=1⁴ は含まないものとする. この数たちの和は 1634 + 8208 + 9474 = 19316 である.

各桁を5乗した数の和が元の数と一致するような数の総和を求めよ.
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2030 」

コード

#参考「http://tsumuji.cocolog-nifty.com/tsumuji/2009/07/project-euler-6.html」の冒頭
TOP = (9 ** 5) * 6
tot = 0
ls = []
for num in range(TOP):
    if sum(map(lambda x:int(x)**5 , str(num))) == num:
        tot += num
        ls.append(num)
print(tot) #443840
print(ls) #[0, 1, 4150, 4151, 54748, 92727, 93084, 194979]

#参考「http://tsumuji.cocolog-nifty.com/tsumuji/2009/07/project-euler-6.html」の冒頭

TOP = (9 ** 5) * 6

tot = 0

ls = []

for num in range(TOP):

if sum(map(lambda x:int(x)**5 , str(num))) == num:

tot += num

ls.append(num)

print(tot) #443840

print(ls) #[0, 1, 4150, 4151, 54748, 92727, 93084, 194979]

考え方

便利なstr型とmap関数を使って簡潔に書けているいいコード。

上限

最初は上限が分からず、適当に大きな数を入れて答えを出した。

7桁だと、最高、(9^5)*7=413343<10^(7-1)で元の数に届かない。

よって、6桁まで調べればいいので上限は(9^5)*6となる。

参考「 http://tsumuji.cocolog-nifty.com/tsumuji/2009/07/project-euler-6.html 」

興味本位で

lsに関するコードは答えには関係ないが興味があったので書いた。

思ったより条件に当てはまる数がたくさんあった。

以上！

段々と数学的にも難しくなってきた。

次の記事↓

Project Euler31〜35をpythonで解く