ruskのメモブログ

python勉強記録

Project Euler

Project Euler 21〜25をpythonで解く

更新日：

Problem 21

問題（英語）

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

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

問題（日本語）

d(n) を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. )
もし, d(a) = b かつ d(b) = a (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという.

例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である.
また, 284 の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である.

それでは10000未満の友愛数の和を求めよ.

「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2021 」

コード

考え方

みんな大好き友愛数。

約数を求める関数は調べてしまった。

1から10000まで順番に約数の和を求めていって辞書型のdataに記録する。

itemsメソッド

辞書型は今だに慣れない。

itemsメソッドでキー（key）とその値（value）をセット（タプル）として受けとることが出来る。

正確には一種のイテレータになり、一つ一つの要素がタプルである。

説明が下手なので、詳しく知りたい方はこのページで。（丸投げ）

「 https://note.nkmk.me/python-dict-keys-values-items/ 」

友愛数の判定

今回はkeyに整数(i)、valueにその約数の和(tot_div(total_divisors))を入れて記録しているので、以下のようにすることで友愛数の判定が出来る。

iとtot_divを入れ替えたセットがdataに存在するかをチェックしている。

（あればTrue、なければFalse）

約数を求める関数

参考「 https://qiita.com/LorseKudos/items/9eb560494862c8b4eb56 」

リストの方が早い？

辞書型を使わずともリストで書ける。

例の「n番目に整数nの情報（今回は約数の和）を入れたリスト」を使えばいい。

このリストを使うと、友愛数の探索が早くなる。（と思っていた。）

mainを以下のように書き換える。

友愛数の探索は、

から

になっている。

タイム計測

どれぐらい早くなるか計測してみた。

辞書型のデータに記録:

リスト型のデータに記録:

あれ？

あまり変わらなかった...。

TOP = 10万としてみてもほぼ同じスピードだった。

辞書型の探索はリストと違う挙動をするらしい。

調べてみた

これについて書いてある記事があった。

「 python リスト、辞書、セット型のinを使った時の参照速度を調べてみた。 」

setsや辞書を使った要素の検証（O(1)）は、配列の検索（O(n)）よりも高速です。 a in b を調べるとき、bはリストやタプルではなくsetsや辞書であるべきです。

なるほど。

辞書型はO(1)の高速な検証が出来るらしい。

Problem 22

問題（英語）

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

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

問題（日本語）

5000個以上の名前が書かれている46Kのテキストファイル filenames.txt を用いる. まずアルファベット順にソートせよ.

のち, 各名前についてアルファベットに値を割り振り, リスト中の出現順の数と掛け合わせることで, 名前のスコアを計算する.

たとえば, リストがアルファベット順にソートされているとすると, COLINはリストの938番目にある. またCOLINは 3 + 15 + 12 + 9 + 14 = 53 という値を持つ. よってCOLINは 938 × 53 = 49714 というスコアを持つ.

ファイル中の全名前のスコアの合計を求めよ.

「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2022 」

コード

考え方

必要な情報はスコアとその名前の位置（index）の二つ。

スコアを求める関数を作り、位置はindexを記録する変数countを用意する。

アルファベット順にソート

sortメソッドで簡単にアルファベット順にソート出来る。

ord関数

ord関数は文字列を渡すと、その文字列のUnicodeコードポイントを表す整数を返す関数。

アルファベットのindex(何番目か)を取得するために使う。

例:

実行結果:

よって以下のようにして、そのアルファベット（ここではi）が何番目かを求めることが出来る。

map関数でも書ける

for文はmap関数で書けることも多く、今回はそのほうがスッキリしたかも。

before:

after:

スッキリした...のか？

ちなみにスピードは変わるん？

for文とmap関数、どちらかが極端に早いならそちらを使おうと思ったが、ググってもすぐには分からなかった。

なので、適当にコードを書いた。

実行結果:

map関数の方が少し早いのかな？

ケースバイケースの可能性もあるし、分からない。

Problem 23

問題（英語）

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

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

問題（日本語）

完全数とは, その数の真の約数の和がそれ自身と一致する数のことである. たとえば, 28の真の約数の和は, 1 + 2 + 4 + 7 + 14 = 28 であるので, 28は完全数である.

真の約数の和がその数よりも少ないものを不足数といい, 真の約数の和がその数よりも大きいものを過剰数と呼ぶ.

12は, 1 + 2 + 3 + 4 + 6 = 16 となるので, 最小の過剰数である. よって2つの過剰数の和で書ける最少の数は24である. 数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている. 2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない.

2つの過剰数の和で書き表せない正の整数の総和を求めよ.

「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2023 」

コード

考え方

この問題には相当手を焼いた。

（mainで）やることを手順を追って説明する。

手順１

過剰数（abundant number）のリストを作る。

手順２

過剰数を2つ選んで、その和をcan_writtenに記録する。

手順３

（上限の28123まで）can_writtenに入っていない数字を足し行く。

その値が答え。

何が大変だったかと言うと...

苦戦した点は、過剰数の和で同じ数が複数回出てくる可能性があり、重複して数えてしまう、ということだった。

今思うとこれはまさしくセット型で記録するのが適切なのだが、この時はセット型の存在を知らなかった（orz）。

最終的にcan_writtenをキャッシュとして利用してブール値で記録することにした。

（いつもの、n番目に整数nの情報を入れたリスト）

まずデフォルトでFalseを入れる。

記録する際は、過剰数の和（num）のindexをTrueに書き換える。

これなら再び同じ値が出てきてもTrueをTrueにするだけで、重複して数えることはない。

ただのリストだと...

初めはただのリストで書いていて、相当時間がかかった。（15分ぐらい）

どう書いていたかというと、まずデフォルトでnot_written_listに1~28123（上限）を入れる。

そして過剰数の和をnot_written_listから消していき、残ったのが過剰数の和で書けない整数というつもりだった。

しかし、リストから消す時に以下のように書くのだが、

removeメソッドはリストにない値を指定するとエラーになってしまう。

よって、過剰数の和が再び同じ値になった時にエラーが出てしまうので、弾かなくてはならず、removeの前に以下のコードが必要になる。

これが諸悪の根源。

はリストが大きい時は使ってはいけない...。

set型を使えば解決

set型を使えば重複しないデータを扱える。

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

「 Python, set型で集合演算（和集合、積集合や部分集合の判定など） 」

次のように書き換える。

can_writtenをset型として、addメソッドで過剰数の和を追加する。

すでにある値の場合は、何も追加されない。

これで簡潔に書ける。

無知って怖いね...。

Problem 24

問題（英語）

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

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

問題（日本語）

順列とはモノの順番付きの並びのことである. たとえば, 3124は数 1, 2, 3, 4 の一つの順列である. すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ. 0と1と2の順列を辞書順に並べると

012 021 102 120 201 210

になる.

0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目はいくつか?

「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2024 」

コード

考え方

最初はfor文の中にfor文、という感じで10個のfor文を並べて書こうとしたが、時間がかかりすぎたのでやめた。

pythonに順列の組を生成するモジュールがないかなと調べたら、さすがpython、僕が欲しいやつがまんまあった。

itertools

参考「 https://docs.python.org/ja/3/library/itertools.html 」

こんな感じで順列の組を生成できる。

実行結果:

順番も昇順で、今回欲しいリストそのものである。

これはありがたく使わせて頂くに限る。

Problem 25

問題（英語）

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

The 12th term, F12, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

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

問題（日本語）

フィボナッチ数列は以下の漸化式で定義される:

Fn = Fn-1 + Fn-2, ただし F1 = 1, F2 = 1.

最初の12項は以下である.

  • F1 = 1
  • F2 = 1
  • F3 = 2
  • F4 = 3
  • F5 = 5
  • F6 = 8
  • F7 = 13
  • F8 = 21
  • F9 = 34
  • F10 = 55
  • F11 = 89
  • F12 = 144

12番目の項, F12が3桁になる最初の項である.

1000桁になる最初の項の番号を答えよ.

「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2025 」

コード

考え方

みんな大好きフィボナッチ数列。

見返してみても、いいコードだ（笑）。

Fnはフィボナッチ数列のリストで、関数Fibonacciで末項を求めていき、その値をFnに追加していく。

桁の取得

桁の取得はstrにお任せ。

で整数nの桁数を取得できる。

これが1000桁以上になったらwhileの繰り返しを終えて、答えが得られる。

while文の書き方

今思うと、

なんて書かなくても、

で良かった。

以上！

辞書型やセット型が便利だということが分かった。

Project Euler26〜30をpythonで解く

-Project Euler

Copyright© python勉強記録 , 2026 All Rights Reserved Powered by AFFINGER4.