プロジェクトオイラー Problem5

「プロジェクト　オイラー」の問題をpythonでやってみます。

出典：Project Euler（日本語翻訳サイト）
参考：サイエンスもの置き場　プロジェクトオイラーを遊び倒すガイド（初級編）

Problem 5
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり、そのような数字の中では最小の値である。
では、1 から 20 までの整数全てで割り切れる数字の中で最小の値はいくらになるか。

私の解答例は以下のとおりです。
－－－－－

def gcd(a, b):
 if a<b: a, b = b, a
 if b: return gcd(b, a%b)
 else: return a
 
def lcm(a, b): return a*b/gcd(a,b)
 
def f(n):
 t = 1
 for i in xrange(1, n+1):
  t = lcm(t, i)
 return t
 
print f(20)

－－－－－

関数を３つ使います。

１．関数gcd(a, b)
　aとbの最大公約数(Greatest Common Divisor)を返します。
　ロジックは 以下の数学公式 を利用した解き方です。
「a≧bのとき、aとbの最大公約数は、bと"a/bの余り"の最大公約数と等しい」

「ユークリッドの互除法」と呼ばれている解法です。（参考： wikipedia ）

・if a<b: a, b = b, a
　aとbのうち、大きい方をaにします。bの方が大きいときは入れ替えます。

・if b:
　文の条件式は、Trueが0以外で、Falseが0です。
　小さい方の数bが0になるまで、小さい方の数bとaをbで割った余り(a%b)で当関数を再帰呼び出し（自分で自分自身を呼び出すこと）します。

２．関数lcm(a, b)
　aとbの最小公倍数(Least Common Multiple)を返します。
　ロジックは数学公式の「２数の積はそれらの最小公倍数と最大公約数の積に等しい」を使用し、aとbの積を最大公約数で割った値を最小公倍数として返します。

なお、上記の数学公式の証明は以下のとおりです。
　aとbの最大公約数をGとすると、２数a,bとその最小公倍数Lは以下の通りです。
　a = AxG
　b = BxG　（AとBは、互いに素）
　L = AxBxG
　よって、axb = (AxG)x(BxG) = (AxBxG)xG = LxG（証明終り）
　例）a=12,b=18の場合、12=2x6、18=3X6と表せ、
　　　G=6、L=2x3x6=36 です。　12x18 = 6x36。

３．関数f(n)
　n以下の全ての整数の最小公倍数を返します。

・for i in xrange(1, n+1):
　xrange関数は[1, 2, ・・・, n]と同じ意味です。
　今までの最小公倍数tとループ変数iの最小公倍数tを求め、ループ最後まで繰り返します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
232792560


（追記）
・20120716
　ソースコード部分にSyntaxHighlighterを導入。

プロジェクトオイラー Problem4

「プロジェクト　オイラー」の問題をpythonでやってみます。

出典：Project Euler（日本語翻訳サイト）
参考：サイエンスもの置き場　プロジェクトオイラーを遊び倒すガイド（初級編）

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

私の解答例は以下のとおりです。
－－－－－

m = 0
for i in xrange(100,1000):
	for j in xrange(i,1000):
		k = i*j
		L = list(str(k))
		if L==L[::-1] and m<k:
			x, y, m = i, j, k
			
print m, "=", x, "x", y

－－－－－

変数iとjで３桁の数を２個用意します。
変数iのxrange(100,1000)は、100,101,102,・・・,998,999を返します。
変数jのxrange(i,1000)は、i,i+1,i+2,・・・,998,999を返します。
123×456と456×123は同じ扱いとする組み合わせの積を求めています。

L = list(str(k))
数値kを文字型に変換し、さらに１文字ずつのlist型に変換しています。
123456　→　['1', '2', '3', '4', '5', '6']

L==L[::-1]
リストとその逆順リストの比較をしています。
list型の添え字部分の[]は「:」で区切るとリスト内インデックスを表します。
L=[開始位置:終了位置:刻み]
開始位置、終了位置を省略すると、リストの最初から最後までの全要素のことです。
また、刻みをマイナス値にすると、要素内を逆順に扱います。
なので、L[::-1]は、リストLの全要素を逆順並べたリストです。
L==L[::-1]で、回文数かの判定をしてます。

回文数最大値mを超える回文数kが出現した場合、
２つの３桁の数i,jと回文数kを、x,y,mとして保存します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
906609 (= 913 x 993)

（追記）
・20120716
　ソースコード部分にSyntaxHighlighterを導入

プロジェクトオイラー Problem3

「プロジェクト　オイラー」の問題をpythonでやってみます。


出典：Project Euler（日本語翻訳サイト）
参考：サイエンスもの置き場　プロジェクトオイラーを遊び倒すガイド（初級編）

Problem 3
13195 の素因数は 5、7、13、29 である。
600851475143 の素因数のうち最大のものを求めよ。

私の解答例は以下のとおりです。
－－－－－

def f(n):
	a, p, b, q = 2, n, n, n
	while a<=b:
		if q%a: a += (a%2 + 1)
		else: p, b, q = a, b/a, q/a
	return p
	
print f(600851475143)

－－－－－

処理本体は関数fに記述し、答えをprint文で出力します。

やり方は最大素数の候補pを、その最小値候補aと最大値候補bで挟み、その範囲を狭くしていって、最小値候補a≦最大値候補bが成り立たなくなったら終了というものです。

１．whileループの前の変数初期化
　以下の４つの変数を１行で初期化しています。
・a：最大素因数の最小値候補です。初期値は最小の素数である2です。
・p：求める素因数です。引数そのものが素数である場合が最大なので初期値はnです。
・b：最大素因数の最大値候補です。初期値は引数nです。
・q：割り切れるかの判定対象値です。初期値は引数nです。

次にwhileループの中の処理です。
２．割り切り判定
　%演算子は割り算の余りを返し、論理判定では0がFalse、0以外がTrueと判定されます。
　if文の条件式q%aでは、Trueが割り切れない場合で、Falseが割り切れる場合です。

３．判定対象値qが最小値候補aで割り切れないとき
　最小値候補aを次に大きい値に進めて、whileループの先頭に戻ります。
　最小値候補aは素数を小さい順に試せばいいのですが、処理を簡単にするためにここでは「２と３以上の奇数」を順に試しています。
　この方法で素数は必ず含みますが、9や15などの素数ではない数でも割り切れるか余分に判定することになります。
　
　(a%2 + 1)は、2で割り切れると1、2で割り切れないと2になります。

　a += でaに次々に加算していきます。
　最初にa=2の場合、a=2+1=3が次の最小候補値aになります。
　次にa=3の場合、a=3+2=5というように、この後は3以上の奇数が順に最小値候補aになります。

４．判定対象値qが最小値候補aで割り切れるとき
　以下の設定をして、whileループの先頭に戻ります。
・p：最大素因数候補pは、割り切ることができたその割った値aです。
・b：最大素因数の最大値候補bは、割り切れた数の分だけ小さな値b/aで十分です。
・q：この割り切り判定の商q/aが次の判定対象値です。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
6857


（追記）
・20120716
　ソースコード部分にSyntaxHighlighterを導入
　
　

プロジェクトオイラー 問２

プロジェクトオイラーの問題をpythonでやってみます。
出典：
英語サイトは、Project Euler でネット検索してください。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索してください。


問２
フィボナッチ数列の項は前の2つの項の和である。 最初の2項を 1, 2 とすれば、最初の10項は以下の通りである。
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 数列の項の値が400万を超えない範囲で、偶数値の項の総和を求めよ。


注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の解答例は以下のとおりです。
－－－－－

L, t = [1, 2], 0
while L[1]<4000000:
	if not L[1]%2: t += L[1]
	L = [L[1], sum(L)]
print t

－－－－－

リストLは２つの要素を持つ配列で、L[0]に２つ前の値、L[1]に１つ前の値を格納しています。
変数ｔには合計する対象の値を累積していきます。
１行目でこのリストと変数の初期設定をしています。


%演算子は割り算の余りを返し、
２で割ったあまりが０か１かで奇数か偶数かを判定します。


論理判定では０がFalse、０以外がTrueと判定されます。
偶数の場合、余りは０なので、
L[1]%2がFalseのときに、変数tにL[1]を累積します。


累積し終わったら、次の準備として、
現在の１つ前の値と次のフィボナッチ数を、新たなL[0]、L[1]として格納し処理を続けます。


別解です。フィボナッチ数の計算部分を関数にしてみました。

def p(n):
	L = [1, 2]
	while L[1]<n:
		yield L[1]
		L = [L[1], sum(L)]
	
print sum([i for i in p(4000000) if not i%2])

－－－－－
関数pは、nまでのフィボナッチ数を小さい順に１つずつ返します。
returnでは値を１度返したら終わりですが、
yieldでは値を一つずつ返し、for文の中で値を取り出すことができます。

sum関数の中の配列[]の意味は以下のとおりです。
関数p(4000000)の１つずつの戻り値iのうち、偶数（not i%2）だけを格納した配列

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
4613732


（追記）
・20120716　ソースコード部分にSyntaxHighlighterを導入
・20130120　ネタバレ注意の追記など

プロジェクトオイラー 問１

プロジェクトオイラーの問題をpythonでやってみます。
出典：
英語サイトは、Project Euler でネット検索してください。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索してください。


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



注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の解答例は以下のとおりです。
－－－－－

def p(n,m): return sum([i for i in xrange(0, n, m)])
print p(1000, 3)+p(1000, 5)-p(1000, 15)

－－－－－

１行目の関数p(n,m)の意味は以下の通りです。

０からｎまでのｍ刻みの整数を発生させて、
そのすべての値を小さい順に要素に持つリストを作成し、
そのリスト内の値の合計値を返します。

つまり、「ｎ未満のｍの倍数の合計」を返します。

２行目で、1000未満の３の倍数の合計と、同じく５の倍数の合計を足し、
重複して足してしまった１５の倍数の合計を引いて、コンソールに表示します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
233168

（追記）
・20120716　ソースコード部分にSyntaxHighlighterを導入
・20130120　ネタバレ注意の追記など

京都市の通り名住所の案内文言（３） 方角情報複数

実際の京都市内の住所を例にして、通り名住所の案内文言をたどってみましょう。
前回の続きです。

京都市上京区西町　（３つの西町のうち、郵便番号「602-8374」の西町）

・一条通御前西入上る　（いちじょうどおり　おんまえ　にしいるあがる）

「通り名１＋通り名２＋方角文言」というのが京都市内の通り名住所の基本形ですが、この方角文言が「西入る」「上る」と２つあるパターンです。

このように方角文言が複数つながっている場合は、その順番に道案内の文章として解釈します。
つまりこの場合、西に進んでから北に進む、という意味です。
どのくらい西で、どのくらい北か、という距離情報は含まれていません。

なので、「一条通御前西入上る」という住所表記の意味は以下の通りです。

一条通という東西の通りに沿って、御前通り（おんまえどおり）という南北の通りとの交差点から西に進み、その後、北に進んだあたり。

・一条通御前西入上る西入（いちじょうどおり　おんまえ　にしいるあがるにしいる）
　これも上記と同様で、

一条通という東西の通りに沿って、御前通り（おんまえどおり）という南北の通りとの交差点から西に進み、その後、北に進み、さらに西に進んだあたり。

距離情報が無いと、これでたどりつけるのか？　と心配になりますが、
昔から使われてきた住所なので大丈夫なのでしょう。
もしたどり着けないのならば距離情報を付加しているはずです。
では、続きは次回。

京都市の通り名住所の案内文言（２） 距離情報

実際の京都市内の住所を例にして、通り名住所の案内文言をたどってみましょう。
前回の続きです。

京都市上京区西町　（３つの西町のうち、郵便番号「602-8374」の西町）

・一条通御前３丁目西入　（いちじょうどおり　おんまえ　３ちょうめ　にしいる）
　
「通り名１＋通り名２＋方角文言」という基本形に、「３丁目」が付いています。
この「数字＋丁目」は、昔の距離の単位としての「町」に由来しています。
ややこしいのですが、市区町村や大字などの領域名の接尾語の「町」ではなく、距離の単位の「町」です。
距離の単位の場合に限り、「丁」とも表記してきたものです。

（参考）
町(単位) (wikipedia)

１丁　＝　１０９．０９ｍ、「目」は序数（順番を表す数）の接尾語なので、
「３丁目」は、距離として、１丁の３つ目、現在の３００ｍくらいということです。

なので、「一条通御前３丁目西入」という住所表記の意味は以下の通りです。

一条通という東西の通りに沿って、御前通り（おんまえどおり）という南北の通りとの交差点から約３００ｍ西に進んだあたり。

では、続きは次回。