2012年8月26日日曜日

Project Euler - Problem 53

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
   ProjectEuler.net(英語サイト)

Problem 53
12345から3つ選ぶ選び方は10通りである.
123, 124, 125, 134, 135, 145, 234, 235, 245, 345.
組み合わせでは, 以下の記法を用いてこのことを表す: 5C3 = 10.

一般に, r≦n についてnCr = n!/(r!(n-r)!) である.
ここで, n! = n×(n-1)×...×3×2×1, 0! = 1と階乗を定義する.

n = 23になるまで, これらの値が100万を超えることはない:
23C10 = 1144066.
1≦n≦100について, 100万を超えるnCrは何通りか?

-----


私の解答例は以下です。畳んでいます。
def h(n):
	if n<=1: return 1
	else: return h(n-1)*n

def g(n, m): return h(n)//h(n-m)//h(m)

def f(n, m):
	s = 0
	for i in xrange(1, n+1):
		for j in xrange(1, i+1):
			if g(i, j)>m: s += 1
	return s

print f(100, 1000000)


1.関数h(n)
・nの階乗を返します。problem20と同じです。


2.関数g(n, r)
・順列nCrの値を返します。problem15と同じです。


3.関数f(m):
・順列nC*のすべての組み合わせ値のうちmを超える組の件数を返します。


・s = 0
 sは件数カウンターです。0クリアしておきます。


・for i in xrange(1, n+1):
 ループ関数iは順列nCr、n個のうちr個選ぶ組み合わせのnです。


・for j in xrange(1, i+1):
 ループ関数jは順列nCr、n個のうちr個選ぶ組み合わせのrです。


・if g(i, j)>m: s += 1
 関数g(i,j)で順列値を求めその値がmを超える場合、件数カウンターsをカウントアップします。


・return s
 iとjのループが終わったら、件数カウンターsを返します。

4.関数の外
 関数f(100,1000000)を呼び出し、その戻り値を出力します。


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

Project Euler - Problem 52

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
   ProjectEuler.net(英語サイト)

Problem 52
125874を2倍すると251748となる. これは元の数125874と同じ数を含む.

2x, 3x, 4x, 5x, 6xがxと同じ数を含むような最小の正整数xを求めよ.

-----

私の解答例は以下です。畳んでいます。
def f():
	for i in xrange(1, 10000000):
		s = set(str(i))
		for j in xrange(2, 7):
			t = set(str(i*j))
			if s!=t: break
		else: return i

print f()


1.関数f(n)
・for i in xrange(1, 10000000):
 iは1からの連番です。10000000は、とりあえずの終了値です。
 結果的に6桁で問題に合う値に到達します。

・s = set(str(i))
 連番iをstr関数で文字型にして、set関数で集合型にします。
 集合型にすることで、1文字ずつの重複要素を削除し、構成要素だけの集合にします。

・for j in xrange(2, 7):
 jは掛ける数です。範囲は2から6までです。

・t = set(str(i*j))
 連番iと掛ける数jの積について、上記iと同様に構成要素だけの集合にします。

・if s!=t: break
 元の連番とj倍した値のそれぞれの構成要素が異なれば、ループ変数iの次の値へ処理を進めます。

・else: return i
 ループ変数jのfor文のelseです。
 for文のelseは、for文を全部最後の要素まで回り終わった場合に実行します。
 途中でループを抜けた場合には実行されません。
 ここでは上記if文ででbreakぜずに、2倍値から6倍値までのすべてで、その構成要素が元の数iの構成要素と同じ場合にだけ、そのiを呼び出し元に返します。

2.関数の外
 関数f()を呼び出し、その戻り値を出力します。


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

Project Euler - Problem 51

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
   ProjectEuler.net(英語サイト)

Problem 51
*3の第1桁を置き換えることで,
13, 23, 43, 53, 73, 83という6つの素数が得られる.

56**3の第3桁と第4桁を同じ数で置き換ることを考えよう.
この5桁の数は7つの素数をもつ最初の例である:
56003, 56113, 56333, 56443, 56663, 56773, 56993.
よって, この族の最初の数である56003は, このような性質を持つ最小の素数である.

桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ.
(注:連続した桁でなくても良い)

-----


私の解答例は以下です。畳んでいます。
def p(n):
	L = [0,0]+[1]*(n-1)
	i = 2
	while i*i<=n:
		while not L[i]: i += 1
		for j in xrange(i+i, n+1, i): L[j] = 0
		i += 1
	return [i for i in xrange(n+1) if L[i]]

def h(n, L):
	for i in xrange(10):
		t = ""
		for j, k in enumerate(str(n)):
			if j in L: t += str(i)
			else: t += k
		yield int(t)

def g(m, n):
	d = {}
	for i, t in enumerate(str(m)):
		d[t] = d.get(t, [])+[i]
	for k,v in sorted(d.items()):
		if len(v)==n: yield int(k),v

def f():
	for i in xrange(3, 100, 3):
		for n in xrange(i+1, 100):
			P = [s for s in p(10**n) if s>10**(n-1)]
			for j in P:
				for k,L in g(j, i):
					if k>2: break
					if L[-1]>=n-1: break
					t = 0
					for u in h(j, L):
						if u not in P: t += 1
						if t>2: break
					if t==2: return j

print f()

候補を絞り込みます。

桁を同じ数で置き換えることで8つの素数が得られる最小の素数とのことなので、
置換後値が素数になる場合の置換数字には0~9うちの8個選ばれるので、
置換数字の最小値には0,1,2のどれかが含まれます。...(A)

素数でない数として、まず2の倍数をはずします。
置換数字には、0~9の10種類の数字のうちの8個選ばれるので、必ず偶数を含みます。
1の位に偶数がきたら2の倍数となり素数ではないので、
置換数字は1の位にきません。...(B)

つまり、置換数字は10の位よりも上の桁になるので、
全体桁数は置換数字の桁数よりも1桁以上多いです。...(C)

次に3の倍数をはずします。
置換数字が1桁の連番の場合、
3で割るとその余りは、0,1,2が繰り返しでてきます。
すると余り0,1,2が最低各3つずつあり、
3の倍数以外が8個あることはあり得ず問題に合いません。

置換数字が2桁の11,22,...の場合も同様で
余り0,1,2が最低各3つずつあり、
3の倍数以外が8個あることはあり得ず問題に合いません。

置換数字が3桁の111,222,...の場合は
置換数字そのものの各桁和が3の倍数なので、置換数字はすべて3の倍数なので、
3で割るとその余りはすべて同じで、0,1,2のどれかです。
この場合は問題に合うことがあり得ます。

置換数字が4桁以上の場合も上記と同様なので、
置換数字の桁数は3の倍数です。...(D)

上記の4条件を使って絞り込みます。
4つの関数を使っています。

1.関数p(n)
・n以下の素数リストを返します。problem37と同じです。

2.関数h(n, L):
・数値nの、位置リストLの位置を0-9に置換した数値を返します。
 指定位置の桁の値を置換数字で置換した値を返します。

・for i in xrange(10):
 ループ変数iは置換数字です。0~9の値を順に取ります。

・t = ""
 置換後数字を1桁ずつためていく変数です。初期値は""です。

・for j, k in enumerate(str(n)):
 ループ変数kは数字nを上から1文字ずつ取り出した値で、jはそのときの0からの連番です。

・if j in L: t += str(i)
 else: t += k
 連番jがリストLに含まれていれば現在位置が置換位置なので、置換数字iをstr関数で文字型変換した値を付け足します。
 そうでなければ数字nを上から1文字ずつ取り出した値kを付け足します。

・yield int(t)
 yield文で値が1つ決まるごとに処理を一旦凍結して呼び出し元に値を返却します。そして再度呼び出されたら処理を再開し続行、次の値を処理します。
 yield文では返却値が1つ決まるごとに処理凍結、値返却、処理再開を繰り返します。

このようにyield文で値を返す関数を「ジェネレータ関数」と呼びます。
これに対してreturn文で値を返し処理を終了してしまう関数は「イテレータ関数」といいます。
1つの関数の中にyield文とreturn文を両方含めることはできません。

3.関数g(m, n):
・数字mにn個含まれる構成文字とその位置リストの組を返します。
 置換数字を置換する位置を求めるときに使います。

・d = {}
 辞書dは数字mに含まれる各桁の値をキーに、その位置のリストを値として持ちます。初期値は空です。

・for i, t in enumerate(str(m)):
  d[t] = d.get(t, [])+[i]
 ループ変数iはenumerate関数による0からの連番で、数字mの中での左からの位置を示します。
 ループ変数tは数字mの上から1文字ずつの値です。
 get関数で、辞書dに数字mの上から1文字ずつの値tがキーとして存在すればtに対応する値を返し、存在しなければ空のリスト[]を返します。
 これに0からの連番iだけをを要素に持つリストを連結することで、
 数字mを構成する文字をキーとする、位置リストの辞書を作成します。

・for k,v in sorted(d.items()):
 items関数で辞書dのキーと値の組をループ変数k,vとして取得します。
 sorted関数でキー順に並べ替えます。
 これは1122のように同じ件数の構成文字が複数種類ある場合、小さい順に処理するためです。

・if len(v)==n: yield int(k),v
 ループ変数vは数字mの構成文字kの位置リストなので、len関数でその個数をみて、指定個数n個と等しければ、int関数で数値にした構成文字kとその位置リストを返します。

4.f():
・主処理です。

・for i in xrange(3, 100, 3):
 ループ変数iは置換文字の桁数です。
 絞り込み検討(D)より、置換数字の桁数は3の倍数なので、
 3から100まで3飛びの値をとります。100というのはとりあえずの終了値です。
 結果的にi=3のときに求める値に到達しました。

・for n in xrange(i+1, 100):
 ループ変数nは全体桁数です。
 絞り込み検討(C)より、全体桁数は置換数字の桁数よりも1以上多いので、
 i+1から100までの値をとります。100というのはとりあえずの終了値です。
 結果的にn=6のときに求める値に到達しました。

・P = [s for s in p(10**n) if s>10**(n-1)]
 Pはn桁の素数リストです。
 10**nは10のn乗、つまりn桁最大値+1なので、p(10**n)はn桁以下の素数リストです。
 内包表記で、for文でn桁以下の素数リストから順番に1つずつ取得してsとして、後ろのif文に送り、n桁の最小値を超える値をforの前に送り、そのまま要素にします。
 なお、n桁の最小値は1000などで決して素数ではありません。
 例えばn=4の場合、p(10000)は9999以下の素数で、Pはこのうち1000を超える素数です。

・for j in P:
 ループ変数jはn桁の素数リストから順に1つずつ取得します。
 このjが求める値の候補です。

・for k,L in g(j, i):
 ループ変数kとLには、関数gで算出した、
 候補jの置換数字候補とその位置リストの組をそれぞれ設定します。

・if k>2: break
 絞り込み検討(A)より、置換数字の最小値には0,1,2のどれかが含まれますので、置換数字候補が2を超えたら、次の候補jに進みます。

・if L[-1]>=n-1: break
 絞り込み検討(B)より、置換数字は1の位にきませんので、
 置換位置リストLの最後の値が全体桁数n-1以上ならば、次の候補jに進みます。

・t = 0
 候補jの置換後数値についての、素数以外カウンターです。
 素数判定の処理が重いで、10個中素数8個ということを素数以外が2個ということに代えて処理を軽くします。

・for u in h(j, L):
 ループ変数uは置換後数値です。
 関数hを使って、候補jの、位置リストLの位置の桁の値を0-9に置換した数値を1つずつ設定します。

・if u not in P: t += 1
 置換後数値uが素数でなければ、素数以外カウンターをカウントアップします。

・if t>2: break
 素数以外が2個以上(素数8個未満)が判明したら、次の値に処理を進めます。

・if t==2: return j
 素数以外が2個(素数8個)で問題の条件に合いますので、候補jを返し処理を終了します。

5.関数の外
 関数f()を呼び出し、その戻り値を出力します。


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

2012年8月19日日曜日

Project Euler - Problem 50

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
   ProjectEuler.net(英語サイト)

Problem 50
素数41は6つの連続する素数の和として表せる:
41 = 2 + 3 + 5 + 7 + 11 + 13.
100未満の素数を連続する素数の和で表したときにこれが最長になる.

同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ.

100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?


-----


私の解答例は以下です。畳んでいます。
def p(n):
	L = [0,0]+[1]*(n-1)
	i = 2
	while i*i<=n:
		while not L[i]: i += 1
		for j in xrange(i+i, n+1, i): L[j] = 0
		i += 1
	return [i for i in xrange(n+1) if L[i]]

def f(n):
	P = p(n)
	i, s, t = 0, 0, 0
	while s<n: i, s = i+1, s+P[i]
	for j in xrange(i):
		if i-j<t: break
		for k in xrange(i-1, j, -1):
			if k-j<t: break
			L = P[j:k+1]
			if sum(L) in P: M, t = L, len(L)
	return M

L = f(1000000)
print sum(L)
print "sum of "+str(len(L))+" consecutive primes, " \
+ "from "+str(L[0])+" to "+str(L[-1])+"."


連続する素数和が100万未満ということなので、
まず100万までの素数リストを作ります。
次にこの素数リストの小さい方から和が100万未満となる最大位置を把握します。
そしてこの最大位置までの範囲内で連続する区間を短くしならがその和が、
素数リストにあるかチェックするという流れでやります。

2つの関数を使っています。

1.関数p(n)
・n以下の素数リストを返します。problem37と同じです。

2.関数f(n)
・n以下の素数を連続する素数の和で表したときに最長になる素数のリストを返します。
 問題では100万未満ですが、100万は明らかに素数ではないのでこのまま使用します。

・P = p(n)
 n以下の素数リストです。

・i, s, t = 0, 0, 0
 初期設定です。0クリアしておきます。

・while s<n: i, s = i+1, s+P[i]
 iはカウンター、sは素数表のi番目までの和です。
 この和がnを超えたらループ終了です。
 カウンターiが、連続素数和の構成に使用できる最大位置となります。

・for j in xrange(i):
  if i-j<t: break
 ループ変数jは、連続素数和の最小値の位置です。
 範囲は0から使用最大位置iの1つ手前までです。
 tは後で出てきますが、連続素数の候補の連続する個数です。
 i-jが現在のjの値を固定したときに使用できる素数の最大件数なので、
 i-j<tになったら現在調査済みの連続個数を超えられないのでループをは終了します。

・for k in xrange(i-1, j, -1):
  if k-j<t: break
 ループ変数kは、連続素数和の最大値の位置です。
 範囲は上記最小値の位置jの1つ手前から使用できる最大位置iの1つ手前までです。
 大きい順にチェックするので、開始位置と終了位置を入れ替えて刻みを-1にしています。
 k-jが現在のkの値を固定したときに使用できる素数の最大件数なので、
 k-j<tになったら現在調査済みの連続個数を超えられないのでループをは終了します。

・L = P[j:k+1]
 リストLは上記の位置jと位置kの範囲で素数表Pから取り出した連続素数のリストです。

・if sum(L) in P: M, t = L, len(L)
 連続素数リストLの合計が素数表Pにあれば、連続素数リストLを連続素数最大長リストMとして、また連続数をtとして保存します。

・return M
 上記のループがすべて終了した時点で、連続素数最大長リストMを呼び出し元へ返します。

3.関数の外
 100万を関数fに渡し、100万未満の素数を連続する素数の和で表したときに最長になる素数のリストを受け取ります。
求める値はこのリストの和、sum(L)です。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
997651
sum of 543 consecutive primes, from 7 to 3931.

Project Euler - Probrem 49

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
   ProjectEuler.net(英語サイト)

Problem 49
項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ。

  • (i)3つの項はそれぞれ素数である。
  • (ii)各項は他の項の置換で表される。
1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが、4桁の増加列にはもう1つ存在する。
それではこの数列の3つの項を連結した12桁の数を求めよ。


-----

私の解答例は以下です。畳んでいます。
def p(n):
	L = [0,0]+[1]*(n-1)
 i = 2 while i*i<=n: while not L[i]: i += 1 for j in xrange(i+i, n+1, i): L[j] = 0 i += 1 return [i for i in xrange(n+1) if L[i]] def f(n): import itertools A = [] P = [i for i in p(10**n) if len(str(i))==n] for i in P: L = set(["".join(j) for j in itertools.permutations(str(i), n)]) M = sorted([int(j) for j in L if int(j) in P]) for j in xrange(len(M)-1): for k in xrange(j+2, len(M)): s, t = divmod(M[j]+M[k], 2) if (not t) and (s in M): v = int(str(M[j])+str(s)+str(M[k])) if v not in A: A.append(v) break return A L = f(4) for s in L: if s!=148748178147: print s


2つの関数を使っています。

1.関数p(n)
・n以下の素数リストを返します。problem37と同じです。

2.関数f(n)
・import itertools
 pythonの標準モジュール「itertools」をインポートします。

・A = []
 P = [i for i in p(10**n) if len(str(i))==n]
 初期設定です。
 戻り値用リストAは空リストです。
 リストPは、n桁の素数のリストです。
 内包表記です。
 **演算子は累乗で、10**nでn桁の最大値+1になります。
 まずfor文で0からn桁の最大値を1つずつループ変数iとします。
 次に後ろのif文へiを渡し、str関数で文字型にしてlen関数で文字列長を取得しこれがnの場合に限り、for文の前に渡し、そのままリストにためます。

・for i in P:
 n桁素数リストPから1つずつループ変数iとします。

・L = set(["".join(j) for j in itertools.permutations(str(i), n)])
 リストLは、素数iの構成数字を並び替えた値のリストです。
 標準モジュールitertoolsの関数permutations(t, n)は、文字列tの構成文字列から繰り返しを許さずにn個を選んで組にして返します。
 例えば、t="13",n=2ならば、("1","3")("3","1")を返します。

 ここでは、str関数で文字型にした素数iから
 n桁の「繰り返しを許さない順列タプル」を生成し、
 for文で1つずつループ変数jとして、
 このタプルjを区切り文字無しで連結してリストLにためます。
 例の場合、["13", "31"]となります。

・M = sorted([int(j) for j in L if int(j) in P])
 リストMは、素数iの構成数字を並び替えてさらに素数だった値のリストです。
 内包表記です。
 まずfor文で上記リストLから1つ取り出して要素jとします。
 そして後ろのif文へ渡し、int関数で数値にしたあと素数表Pにあるか判定し、素数の場合、for文の前に渡し、int関数で数値型にしてリストにためます。
 後で差を見るのでsorted関数で小さい順に並べなおしておきます。

・for j in xrange(len(M)-1):
  for k in xrange(j+2, len(M)):
 ループ変数jは求める等差数列のうち最小値に相当する値の、リストMでの位置です。
 ループ変数kは求める等差数列のうち最大値に相当する値の、リストMでの位置です。
 つまり、3項の等差数列の最小値と最大値の候補を、M[j]とM[k]とします。

・s, t = divmod(M[j]+M[k], 2)
 divmod関数は第1引数÷第2引数を計算し、整数の商と余りのタプルを返します。
 ここでは(M[j]+M[k])÷2の商と余りを計算し、それぞれs,tとします。
 商sは3項の等差数列の2番目の項、余りtは商sが整数として存在すれば余り0(論理的にFalse)になります。

・if (not t) and (s in M):
  v = int(str(M[j])+str(s)+str(M[k]))
  if v not in A: A.append(v)
  break
 (not t)で上記sが整数として存在し、(s in M)で上記sがリストMにあることをチェックします。
 このような条件が満たされる場合、3項の等差数列が存在することになるので、問題に合うように3項の値を文字型にして小さい順に連結しvとします。
 上記vが戻り値用リストAに無ければ追加します。

・return A
 このようにしてたまった戻り値リストAを呼び出し元に返します。

3.関数の外
・L = f(4)
 for s in L:
  if s!=148748178147: print s
 問題に合う関数fの戻り値を受け取り、さらに「148748178147」以外の値を表示します。
 


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

Project Euler - Probrem 48

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
   ProjectEuler.net(英語サイト)

Problem 48
次の式は、11 + 22 + 33 + ... + 1010 = 10405071317 である。
では、11 + 22 + 33 + ... + 10001000 の最後の10桁を求めよ。

-----


私の解答例は以下です。畳んでいます。
def f(n): return str(sum([i**i for i in xrange(1, n+1)]))

s = f(1000)
print s[-10:]


pythonでは多バイト長の数値であっても通常の数値として扱うことができます。

1.関数f(n)
・1からnまでの数字のその数字分の累乗の和を文字型にして返します

・return str(sum([i**i for i in xrange(1, n+1)]))
 内包表記です。
 for文で1からnまでの数字をループ変数iとして、forの前に渡します。
 **演算子は累乗です。i**iで、iのi乗値をリストにためます。
 sum関数で合計し、さらにstr関数で文字型に変換しておきます。

2.関数の外
・s = f(1000)
 引数1000で関数fを呼び出します。なお、この戻り値は3001桁ありました。

・print s[-10:]
 上記で取得したsの右から10桁分を取り出します。

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

Project Euler - Probrem 47

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
   ProjectEuler.net(英語サイト)

Problem 47
連続する2つの数がそれぞれ2つの異なる素因数を持つのは
  • 14 = 2 × 7
  • 15 = 3 × 5の場合である.
同様に連続する3つの数がそれぞれ3つの異なる素因数を持つのは
  • 644 = 22 × 7 × 23
  • 645 = 3 × 5 × 43
  • 646 = 2 × 17 × 19の場合である.
連続する4つの数がそれぞれ4つの異なる素因数を持つ場合を考え, 連続する数の中で最小のものを答えよ.

-----

私の解答例は以下です。畳んでいます。
def p(n):
	L = [0,0]+[1]*(n-1)
	i = 2
	while i*i<=n:
		while not L[i]: i += 1
		for j in xrange(i+i, n+1, i): L[j] = 0
		i += 1
	return [i for i in xrange(n+1) if L[i]]

def g(n, P):
	s, d = n, {}
	for i in P:
		while s>=i:
			if s%i: break
			else:
				while not s%i:
					d[i], s = d.get(i, 0)+1, s//i
		if s<i: break
	return d

def f(n):
	P = p(10000000)
	i, L = 0, []
	while True:
		i += 1
		s = g(i, P)
		if len(s)==n: L.append(s)
		else: L = []
		if len(L)==n: break
	return L

n = 4
for d in f(n):
	s = 1
	for k, v in d.items():
		s *= k**v
	print s, sorted(d.items())


3つの関数を使っています。

1.関数p(n)
・n以下の素数リストを返します。problem37と同じです。
2.関数g(n, P)
・素数リストPに含まれる素数にて、nを素因数分解した辞書を返します。
 キーが素数で値がその素数が含まれる数です。

・s, d = n, {}
 sを素数で割り算していきます。初期値はnです。
 dは返却用の辞書です。初期値は空の辞書です。

・for i in P:
 素数リストPの要素を1つずつループ変数iとします。

・while s>=i:
 割られる数sが割る数の素数i以下の場合に割り算をしていきます。

・if s%i: break
 %は割り算の余りです。余りがある(論理的にTrueの)場合、割る数iを次の値に進めます。

・else:
  while not s%i:
   d[i], s = d.get(i, 0)+1, s//i
 余りがない(論理的にFalseの)場合、割り切れなくなるまで、割る数iで割り続けます。
 辞書dのキーiの値を1ずつカウントアップします。
 割られる数sはiで割った商を設定します。

・if s<i: break
 割られる数sよりも割る数の素数iが大きくなったら終了します。

3.関数f(n)
・n個の素因数をもつ連続するn個の数について、その連続するそれぞれの値を素因数分解した辞書を要素とするリストを返します。

・P = p(10000000)
 リストPは1000万以下の素数の表です。
 これは私の手持ちの素数発生関数で1分ルールとメモリを満たす限界です。
 素因数分解をするときに割る数として使用します。

・i, L = 0, []
 iはカウンターで、Lは戻り値用リストです。、

・while True:
  i += 1
 無限ループです。ループの都度、カウンターiを1つカウントアップします。

・s = g(i, P)
 sはカウンター値iを素数表Pを使って素因数分解した辞書です。

・if len(s)==n: L.append(s)
 else: L = []
 len関数の辞書sを渡すと、辞書sのキー件数を返します。
 この辞書sのキー件数は素因数の数なので、n個の場合、戻り値用リストLにためます。
 n以外の場合、戻り値用リストLをクリアします。

・if len(L)==n: break
 戻り値用リストLの件数をチェックし、要素数がnならばループ終了です。

3.関数の外
・問題に合う値を表示します。

・n = 4
 for d in f(n):
 問題に合うように引数を4を関数fに渡します。

・s = 1
  for k, v in d.items():
   s *= k**v
  print s, sorted(d.items())
 問題に合う連続する数をsとして、素因数とその掛け合わせる数に基づいて、再現します。
 辞書d.itmes()は、辞書dのキーと値の組のタプルを返します。
 ここではそれぞれループ変数kにキー値を、ループ変数vに値を設定しています。
 **演算子は累乗です。ここではkのv乗値をsに掛け算で累積しています。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
134043 [(3, 1), (7, 1), (13, 1), (491, 1)]
134044 [(2, 2), (23, 1), (31, 1), (47, 1)]
134045 [(5, 1), (17, 1), (19, 1), (83, 1)]
134046 [(2, 1), (3, 2), (11, 1), (677, 1)]

Project Euler - Probrem 46

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
   ProjectEuler.net(英語サイト)

Problem 46
Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.
  • 9 = 7 + 2×12
  • 15 = 7 + 2×22
  • 21 = 3 + 2×32
  • 25 = 7 + 2×32
  • 27 = 19 + 2×22
  • 33 = 31 + 2×12
後に, この予想は誤りであることが分かった.

平方数の2倍と素数の和で表せない最小の奇合成数を答えよ.


-----

私の解答例は以下です。畳んでいます。
def p(n):
	L = [0,0]+[1]*(n-1)
	i = 2
	while i*i<=n:
		while not L[i]: i += 1
		for j in xrange(i+i, n+1, i): L[j] = 0
		i += 1
	return [i for i in xrange(n+1) if L[i]]

def g(n):
	import math
	L = []
	for i in xrange(1, int(math.sqrt(n//2))+1):
		s = i*i*2
		if s<=n: L.append(s)
	return L

def f():
	i = 1
	while True:
		i += 2
		P = p(i)
		if i in P: continue
		for j in g(i):
			if i-j in P: break
		else:
			return i

print f()


「平方数の2倍」と「素数」の和が「奇合成数」かを判定します。
「平方数の2倍」と「素数」の和の組合せ生成は相当の件数になるので避けます。
処理時間を短くするために、
同一範囲内では「平方数の2倍」が「素数」よりも件数が少ないことと、
奇合成数は奇数を発生させて素数リストに無い数という判定になることから、
奇数ループの中で、素数でない奇数から平方数2倍値を引いた値が素数かを判定する方法でやります。

3つの関数を使っています。

1.関数p(n)
・n以下の素数リストを返します。problem37と同じです。

2.関数g(n)
・n以下の「平方数の2倍値」リストを返します。

・import math
 python標準モジュールの「math」を使う準備としてインポートしておきます。

・for i in xrange(1, int(math.sqrt(n//2))+1):
 ループ変数1はカウンタです。範囲は1から上限値までです。
 上限値は、平方数の2倍がn以下ということから、n/2の平方根です。
 
・s = i*i*2
 sは平方数の2倍値です。

・if s<=n: L.append(s)
 平方数の2倍値がn以下ならば、リストLにためます。

3.関数f(n)
・i = 1
 while True:
  i += 2
 whileの無限ループで、iは奇数カウンタでチェック対象となる値です。

・P = p(i)
 奇数i以下の素数リストです。

・if i in P: continue
 奇数iが素数の場合、奇合成数ではないので次の奇数へ進みます。

・for j in g(i):
  if i-j in P: break
 else:
  return i

 奇数i以下の平方数2倍値リストの1つずつをループ変数jとします。
 奇数iから平方数2倍値jを引いた値が素数ならば、その奇数iは「平方数の2倍と素数の和で表せる奇合成数」なので、ゴールドバッハ予想に適合し対象外となるので次の奇数iへ進みます。
 
 for文のelse節は、for文がループの最後まで回った場合だけforループ終了後に行います。
 ここでは、ゴールドバッハ予想に適合することがなかった場合、else節に進み、奇数iを呼び出し元に返します。

3.関数の外
・print f()
 問題に合う値を表示します。


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

Project Euler - Probrem 45

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
    ProjectEuler.net(英語サイト)

Problem 45
三角数, 五角数, 六角数は以下のように生成される.
三角数Tn=n(n+1)/2 1, 3, 6, 10, 15, ...
五角数Pn=n(3n-1)/2 1, 5, 12, 22, 35, ...
六角数Hn=n(2n-1) 1, 6, 15, 28, 45, ...
T285 = P165 = H143 = 40755であることが分かる.
次の三角数かつ五角数かつ六角数な数を求めよ.


-----

私の解答例は以下です。畳んでいます。
import math

def h(n): return not (-1+math.sqrt(1+n*8))%2

def g(n): return not (1+math.sqrt(1+n*24))%6

def f(n):
	i = 0
	while True:
		i += 1
		s = i*(2*i-1)
		if s<=n: continue
		if g(s) and h(s): return s

print f(40755)


六角数の進み方が一番早いので、六角数を1つずつ計算してそれが五角数、三角数であるか判定する方法でやります。

3つの関数を使っています。

1.関数h(n)
・return not (-1+math.sqrt(1+n*8))%2
 三角数の判定です。
 定義式から、x(x+1)/2 = nを満たす整数xが存在すればnは三角数です。
 xの二次方程式として、二次方程式の解の公式より、
 x = -1±√(1+8n)/2
 %演算子は割り算の余りです。
 整数xが存在すれば上記の余りがない(論理的にFalse)です。
 このxが整数かどうかは、+か-のどちらで判定しても同じなので、
 ここでは+の方を採用しています。

2.関数g(n)
・五角数の判定です。problem44と同じです。

3.関数f(n)
・nを超える最小の三角数かつ五角数かつ六角数である数を返します。

・i = 0
 初期値としてnを設定します。

・while True:
 無限ループです。

・i += 1
 iは1ずつ増えるカウンターです。

・s = i*(2*i-1)
 sはi番目の六角数です。

・if s<=n: continue
 六角数sがn以下の場合は次の六角数に進みます。

・if g(s) and h(s): return s
 六角数sが五角数かつ三角数の場合、その数sを返します。

3.関数の外
・print f(40755)
 問題に従い、40755を超える範囲で関数f(n)を呼び出します。


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

Project Euler - Probrem 44

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
    ProjectEuler.net(英語サイト)

Problem 44
五角数は Pn = n(3n-1)/2で生成される. 最初の10項は
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
である.

P4 + P7 = 22 + 70 = 92 = P8である. しかし差 70 - 22 = 48は五角数ではない.

五角数のペア PjとPkについて, 差と和が五角数になるものを考える.
差を D = |Pk - Pj| と書く. 差 D の最小値を求めよ.


-----


私の解答例は以下です。畳んでいます。
def g(n):
	import math
	return not (1+math.sqrt(1+n*24))%6

def f():
	i, t, L, M = 0, 0, [], []
	while len(M)<1:
		i += 1
		s = i*(3*i-1)//2
		for j in L[::-1]:
			if g(s+j) and g(s-j):
				M.append((j, s))
		L.append(s)
	return M

t = f()[0]
print t[1]-t[0], t


上記プログラムでは、求めた差がその時点での五角数の数列の増分よりも大きいので、これよりも大きな値のところで、最小値となる差が存在する可能性があります。
増分の方が差よりも大きくなるところまで検証したいところですが、1分ルールを満たせず、五角数の和と差が五角数である最小の組を見つけたところで処理を終了しています。
結果として答えは合っていましたが、さらに改良が必要です。

2つの関数を使っています。

1.関数g(n)
・五角数の判定です。

・return not (1+math.sqrt(1+n*24))%6
 定義式から、x(3x-1)/2 = nを満たす整数xが存在すればnは五角数です。
 xの二次方程式として、二次方程式の解の公式より、
 x = (1±√(1+24n))/6
 このxが整数かどうかは、+か-のどちらで判定しても同じなので、ここでは+の方を採用しています。

2.関数f(n)
・問題の条件に合う値をリストLにためていきます。

・while len(M)<1:
 Mに1でも解がたまれば終了にします。
 上限値を設けて全ての値を検証したいのですが、1分ルールを守れませんでしたので、ここでは1つ見つけたら終了しています。

・i += 1
 iは1ずつ増えるカウンターです。

・s = i*(3*i-1)//2
 sはi番目の五角数です。

・for j in L[::-1]:
 差が小さいものを抽出するため、すでにチェックの済んだ大きい値から順に比較します。
 リストLには五角数が小さい順に入っていますので、逆順にループして大きい値から取り出して、ループ変数jとします。
 リスト[開始位置:終了位置:刻み]です。[::-1]で逆順に1つずつです。

・if g(s+j) and g(s-j):
  M.append((j, s))
 sとjの和と差が両方とも五角数の場合、s,jの組をリストMにためていきます。

・L.append(s)
 sをチェック済みの五角数としてリストLにためていきます。

3.関数の外
・t = f()[0]
 print t[1]-t[0], t
 関数fの戻り値から、その差を求めます。


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

2012年8月18日土曜日

Project Euler - Probrem 43

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
    ProjectEuler.net(英語サイト)

Problem 43
数1406357289は0から9のPandigital数である (0から9が1度ずつ現れるので).
この数は部分語が面白い性質を持っている.
d1を1桁目, d2を2桁目の数とし, 以下順にdnを定義する.
この記法を用いると次のことが分かる.
  • d2d3d4=406は2で割り切れる
  • d3d4d5=063は3で割り切れる
  • d4d5d6=635は5で割り切れる
  • d5d6d7=357は7で割り切れる
  • d6d7d8=572は11で割り切れる
  • d7d8d9=728は13で割り切れる
  • d8d9d10=289は17で割り切れる
このような性質をもつ0から9のPandigital数の総和を求めよ.


-----

私の解答例は以下です。畳んでいます。
def g(n):
	import itertools
	t = "".join([str(i) for i in xrange(n)])
	return ["".join(s) for s in itertools.permutations(t, n)]

def f(n):
	L = []
	for j in g(n):
		if int(j[1:4])%2: continue
		elif int(j[2:5])%3: continue
		elif int(j[3:6])%5: continue
		elif int(j[4:7])%7: continue
		elif int(j[5:8])%11: continue
		elif int(j[6:9])%13: continue
		elif int(j[7:10])%17: continue
		else:L.append(j)
	return L

L = f(10)
print sum([int(s) for s in L])
print L


9桁以下のpandigital数を生成しこれを素数判定することにしました。
pandigital数の定義がproblem38problem41と異なり、0~9までの10種類の数字で構成されます。

2つの関数を使っています。

1.関数g(n)
・n桁の0からn-1までの数字で構成されるpandigital数のリストを返します。
・1文字目に0がくることもあるので、数値型にせず文字型でためます。
problem41は1からnまでのn桁のpandigital数リストなのでこれを改良しました。

2.関数f(n)
・問題の条件に合う値をリストLにためていきます。

3.関数の外
・L = f(10)
 リストLは10桁(0-9)のpandigital数のリストです。

・print sum([int(s) for s in L])
 print L
 リストLの値を1つずつint関数で数字型にしてリストにため、sum関数で合計を計算します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
16695334890
['1406357289', '1430952867', '1460357289', '4106357289', '4130952867', '4160357289']

Project Euler - Probrem 42

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
    ProjectEuler.net(英語サイト)

Problem 42

三角数のn項は tn = ½n(n+1)で与えられる. 最初の10項は
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
である.

単語中のアルファベットを数値に変換した後に和をとる.
この和を「単語の値」と呼ぶことにする.
例えば SKY は 19 + 11 + 25 = 55 = t10である.
単語の値が三角数であるとき, その単語を三角語と呼ぶ.

16KBのテキストファイル words.txt 中に約2000語の英単語が記されている.
三角語はいくつあるか?


-----

私の解答例は以下です。畳んでいます。
def f(sIn):
	#alphabet dic
	D = {}
	for i, s in enumerate(xrange(ord("A"), ord("Z")+1)):
		D[chr(s)] = i+1

	#read
	s = open(sIn).read()
	L = [t for t in s.split(",")]

	#triangle number List
	s = max([len(t) for t in L])
	i, t, T = 0, 0, []
	while t<=s*26:
		i += 1
		t += i
		T.append(t)

	#count
	i = 0
	for s in L:
		u = sum([D.get(t, 0) for t in s])
		i += int(u in T)
	return i

import os, sys
sIn = os.path.join(os.path.dirname(sys.argv[0]), "words.txt")
print f(sIn)


1.アルファベット辞書
problem22と同じです。

2.読み込み
problem22と同じです。
 当pythonソースファイルと同じフォルダ位置に"words.txt"を置きます。

3.三角数リスト
・s = max([len(t) for t in L])
 読み込んだ単語の長さの最大値をsとします。

・while t<=s*26:
 tは三角数です。
 s*26は、読み込んだ単語の長さの最大長だけzが連続した場合の三角数です。
 これを超えない三角数のリストを作成します。

・i += 1
 t += i
 T.append(t)
 iは連番です。tは三角数です。Tは三角数リストで、これに三角数tをためていきます。

4.三角語のカウント
・for s in L:
 対象となる単語リストLから単語を1つずつ取り出し、ループ変数sとします。

・u = sum([D.get(t, 0) for t in s])
 単語sから1文字ずつ取り出し、ループ変数tとします。
 アルファベット辞書Dを文字tで検索して、あれば辞書の値、無ければ0をリストにためます。
 sum関数で上記リストの合計、「単語の値」を変数uとします。

・i += int(u in T)
 単語の値uが三角リストTにあるか、「u in T」は論理型で返します
 論理型をint関数で数値型に変換すると、Trueが1、Falseが0に変換されますので、
 このint値をそのまま累積すればTrueの件数をカウントアップできます。


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

Project Euler - Probrem 41

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
    ProjectEuler.net(英語サイト)

Problem 41

n桁Pandigitalであるとは, 1からnまでの数を各桁に1つずつもつこととする.

#下のリンク先にあるような数学的定義とは異なる
例えば2143は4桁Pandigital数であり, かつ素数である.

n桁(この問題の定義では9桁以下)Pandigitalな素数の中で最大の数を答えよ.


-----

私の解答例は以下です。畳んでいます。
def p(n):
	L = [0,0]+[1]*(n-1)
	i = 2
	while i*i<=n:
		while not L[i]: i += 1
		for j in xrange(i+i, n+1, i): L[j] = 0
		i += 1
	return [i for i in xrange(n+1) if L[i]]

def g(n):
	import itertools
	t = "".join([str(i) for i in xrange(1, n+1)])
	return [int("".join(s)) for s in itertools.permutations(t, n)]

def f(n):
	M = []
	for i in xrange(1, n+1):
		#print i
		L = p(10**(i//2+1))
		for j in g(i):
			for k in L:
				if not j%k: break
			else:
				M.append(j)
	return M

L = f(9)
print L[-1]


problem37の素数リストを、problem38のpandigital数判定すればできるかと
思いましたが、そもそも9桁の素数リストがメモリエラーで作成できませんでした。
そこで方針を変えて、9桁以下のpandigital数を生成しこれを素数判定することにしました。
3つの関数を使っています。

1.関数p(n)
・n以下の素数リストを返します。problem37と同じです。

2.関数g(n)
・n桁のpandigital数のリストを返します。

・import itertools
 pythonの標準モジュール「itertools」をインポートします。

・t = "".join([str(i) for i in xrange(1, n+1)])
 1からnまでの数字を文字型にして、区切り文字無しで連結します。
 例えば、n=9ならばt="123456789"になります。

・return [int("".join(s)) for s in itertools.permutations(t, n)]
 標準モジュールitertoolsの関数permutations(t, n)は、
 文字列tの構成文字列から繰り返しを許さずにn個を選んで組にして返します。
 例えば、t="122",n=2ならば、("1","2")("2","1")を返します。

 ここでは、上記の「繰り返しを許さない順列タプル」をfor文で1つずつループ変数sとして、このタプルsを区切り文字無しで連結しint関数で数字型にしてリストにためます。
 例の場合、[12, 21]となります。
 
3.関数f(n)
・n桁以下のpandigitalな素数のリストを返します。

・for i in xrange(1, n+1):
 ループ変数iは桁数です。値の範囲は1からnまでです。

・L = p(10**(i//2+1))
 関数p(n)による素数リストです。
 最大値の平方根まであれば十分なので、上限値は半分の桁数+1桁分の、10の累乗です。

・for j in g(i):
 ループ変数jは、i桁のpandigital数です。

・for k in L:
  if not j%k: break
 else:
  M.append(j)

 ループ変数kは、チェックで使用する素数です。
 %演算子は割り算の余りです。
 for文のelse節は、for文がループの最後まで回った場合だけforループ終了後に行います。
 ここでは、割り切れて余りが0(論理的にFalse)の場合、素数ではないので、kのfor文を終了し、1つ上のjのfor文の次の値に進みます。
 kのfor文が最後の要素まで全部終わった(途中のifでひっかからなかった)場合が素数です。
 この場合はelse節に進み、リストMにjをためます。

・return M
 上記の要領でためたpandigitalな素数リストMを呼び出し元に返します。

2.関数の外
・L = f(9)
 リストLは9桁以下のpandigitalな素数リストです。

・print L[-1]
 最大の値はリストLの最後の要素です。
 リスト[-1]で最後の要素を取得します。

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

Project Euler - Probrem 40

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
    ProjectEuler.net(英語サイト)

Problem 40

正の整数を順に連結して得られる以下の10進の無理数を考える:
0.123456789101112131415161718192021...
小数第12位は1である.

dnで小数第n位の数を表す.
d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000を求めよ.


-----

私の解答例は以下です。畳んでいます。

def f(n):
	m, s = 0, "."
	while len(s)<=n:
		m += 1
		s += str(m)
	return int(s[n])

s = 1
for i in xrange(7): s *= f(10**i)
print s


1.関数f(n)
・正の整数を順に連結して得られる文字列のn桁目の値を返します。


・m, s = 0, "."
 mは連結する数、sは連結した文字列です。
 初期値はそれぞれ0と小数点とします。


・while len(s)<=n:
  m += 1
  s += str(m)
 mは連結する数字です。1ずつカウントアップします。
 sは上記mを文字型に変換して右へ連結していきます。
 連結した文字列sの長さがnを超えたら終了です。


・return int(s[n])
 連結した文字列sのn番目の値だけを数値型にして返します。


2.関数の外
・s = 1
 for i in xrange(7): s *= f(10**i)
 print s
 問題に合う値を指定して、関数f(n)で戻り値を取得し掛け算で累積します。
 **演算子は累乗です。



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

2012年8月17日金曜日

Project Euler - Probrem 39

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
    ProjectEuler.net(英語サイト)

Problem 39

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

p ≦ 1000 で解の数が最大になる p を求めよ.

-----


私の解答例は以下です。畳んでいます。
def f(p):
	d = {}
	for i in xrange(1, p//3+1):
		for j in xrange(i, (p-i)//2+1):
			for k in xrange(j, p-i-j+1):
				if i*i+j*j==k*k:
					s = i+j+k
					d[s] = d.get(s, [])+[(i,j,k)]
	return d

p = 1000
d = f(p)
n = 0
for k, v in d.items():
	if len(v)>n: r, n, L = k, len(v), v
print r


1.関数f(p)
・周長がp以下で、各辺の長さが整数である直角三角形について、
 周長をキーに3辺の長さの組のリストを値とする辞書(連想配列)を返します。

・for i in xrange(1, p//3+1):
 ループ変数iは最短辺の長さです。
 値の範囲は、1以上で周長の1/3までの整数です。

・for j in xrange(i, (p-i)//2+1):
 ループ変数jは2番目の長さの辺の長さです。
 値の範囲は、最短辺長i以上で、最大周長pから最短辺長iを引いた残りの長さの半分以下です。

・for k in xrange(j, p-i-j+1):
 ループ変数kは最長辺の長さです。
 値の範囲は、第2辺長j以上で、最大周長pから他の2辺長を引いた残りです。

・if i*i+j*j==k*k:
 上記i,j,kが直角三角形を構成するかのチェックです。
 ピタゴラスの定理、そのままです。

・s = i+j+k
 d[s] = d.get(s, [])+[(i,j,k)]
 辞書dの周長sをキーとする値リストに3辺の組(i,j,k)を登録します。
 辞書dからキーsの値を取得するには、d[s]とd.get(s)の2つの方法があります。
 d[s]は、辞書dにキーsが存在しないときエラーになります。
 d.get(s,[])は、辞書dにキーsが存在しないとき、第2引数を返します。
 ここでは第2引数に初期値として空リスト[]を設定しています。
 そして3辺の組のタプル(i,j,k)を要素とするリストに追加していきます。

2.関数の外
・関数f()で問題に合う値の辞書が戻ってくるので、3辺の組の件数が最大のときの周長を求めます。

・for k, v in d.items():
 d.items()で、辞書dのキーと値を一緒に取り出し、それぞれk,vとします。

・if len(v)>n: r, n, L = k, len(v), v
 len(v)で値の件数を求め、今までの抽出値より大きければ、キー、件数、値(3辺の組のリスト)を、それぞれr,n,Lとして取り出しておきます。
 


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
840
8 [(40, 399, 401), (56, 390, 394), (105, 360, 375), (120, 350, 370), (140, 336,364), (168, 315, 357), (210, 280, 350), (240, 252, 348)

Project Euler - Probrem 38

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
    ProjectEuler.net(英語サイト)

Problem 38

192に1, 2, 3を掛けてみよう.
192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
積を連結することで1から9の全ての数字で構成される数、Pandigital数 192384576 が得られる.
192384576を 192と(1,2,3)の連結積と呼ぶ.


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

整数と(1,2,...,n) (n > 1) との連結積として得られる9桁のPandigital数の中で最大のものを答えよ.


-----


私の解答例は以下です。畳んでいます。
def f(n):
	N = set([str(i) for i in xrange(1, n+1)])
	L = []
	for i in xrange(1, 10**(n//2)):
		for j in xrange(1, n//len(str(i))+1):
			t = "".join([str(i*k) for k in xrange(1, j+1)])
			if len(t)==n and set(t)==N: L.append((i, j, int(t)))
	return L

L = f(9)
m = max([s[2] for s in L])
print m
for s in L:
	if s[2]==m:
		print [str(s[0])+"x"+str(i)+"="+str(s[0]*i) for i in xrange(1,s[1]+1)]


1.関数f(n)
・1~nまでの数字を使ったpandigital数のリストを返します。

・N = set([str(i) for i in xrange(1, n+1)])
 1からnまでの数字を1つずつ文字型に変換したリストを、さらに集合型に変換しておきます。後で候補値による集合と比較します。

・for i in xrange(1, 10**(n//2)):
 ループ変数iは連結積の左側部分の数字候補です。
 問題文からpandigital数x1だけはダメで、最低でも2つの数字の連結が必要なことから、対象となる数字の桁数は桁数nの半分以下となります。
 そのため、最大値は10のn//2乗です。//演算子は割り算の商の整数部分です。

・for j in xrange(1, n//len(str(i))+1):
 ループ変数jは連結積の右側部分の数字です。
 jの最大値の数の分だけ掛け算結果を連結することになるので、
 桁数nを連結積左側部分iの桁数で割った商が、その最大値になります。

・t = "".join([str(i*k) for k in xrange(1, j+1)])
 iと(1~j)との連結積を返します。
 内包表記を使っています。
 まず、1からjの連番を1つずつループ変数kとし、forの前に渡し、iとkの積を計算し、連結するのでstr関数で数字型から文字型に変えてリストにためます。
 そのリストを区切り文字無しで連結しtとします。

・if len(t)==n and set(t)==N: L.append((i, j, int(t)))
 上記の計算値tがpandigital数か判定します。
 長さがn桁であり、かつ構成要素が1からnまでの数字かを判定します。
 set関数で文字列tの構成要素を集合型にすることで、重複文字を削除し集合Nと一致するか判定します。
 条件に合えば、そのときのi,j,tのタプルをリストLにためます。

2.関数の外
・関数f()で問題に合う値のリストが戻ってくるので、max関数でその最大値を求めます。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
932718654
['9327x1=9327', '9327x2=18654']

2012年8月16日木曜日

Project Euler - Probrem 37

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
    ProjectEuler.net(英語サイト)

Problem 37

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

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

注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.

-----

私の解答例は以下です。畳んでいます。
def p(n):
	L = [0,0]+[1]*(n-1)
	i = 2
	while i*i<=n:
		while not L[i]: i += 1
		for j in xrange(i+i, n+1, i): L[j] = 0
		i += 1
	return [i for i in xrange(n+1) if L[i]]

def hl(n):
	s = str(n)
	L = [int(s[i:]) for i in xrange(len(s))]
	return L

def hr(n):
	s = str(n)
	L = [n]+[int(s[:-i]) for i in xrange(1, len(s))]
	return L

def g(L, M): return [int(str(s)+str(t)) for s in L for t in M]

def f():
	L = [2, 3, 5, 7]
	R = [1, 3, 7, 9]
	N = []
	i = 1
	while len(N)<11:
		i += 1
		P, L, Mr, Ml = set(p(10**(i))), g(L, R), [], []
		for s in L:
			if set(hr(s))<P: Mr.append(s)
			if set(hl(s))<P: Ml.append(s)
		N += sorted(set(Mr)&set(Ml))
	return N

L = f()
print sum(L), L



問題に合う素数は11個しかないという記述を受けて、11個見つかれば処理終了にしています。
当初は、提示された個数を終了条件にせず、右から切り詰めた値と左から切り詰めた値から問題に合う値が無いところまで処理して、結果として11個でしたという方法を狙っていました。
しかしこの方法では上限が1億以上となる素数リストが必要で1分ルールを守れず断念しました。

ここでは5つの関数を使っています。

1.関数p(n)
・n以下の素数を返します。

problem7problem10problem27problem35を改良して速度向上を図りました。
割り算をなくし、「エラトステネスのふるい(wikipedia)」のロジックで素数が1つ確定したらその倍数は素数ではないとフラグを立てていきます。
そして最後に連番とフラグリストからから素数を抽出する方法にしました。
これで前のロジックの約10倍の速度に改良できました。

・L = [0,0]+[1]*(n-1)
 リストLのi番目が数値iが素数かどうかの判定結果を持ちます。
 0と1は素数の対象外なので0として、それ以降は素数候補として全部1にしておきます。

・i = 2
 2から順に素数判定します。

・while i*i<=n:
 素数iは二乗して上限値n以下である必要があるので、これを終了判定に使用します。

・while not L[i]: i += 1
 リストLで素数フラグが0になっているものは読み飛ばし、素数iを探します。

・for j in xrange(i+i, n+1, i): L[j] = 0
 iは素数なのでiのフラグは1のままにしておき、iより大きいiの倍数である、i+iからnまでi刻みのフラグに0を設定します。
 
・i += 1
 次の値の判定に進みます。

・return [i for i in xrange(n+1) if L[i]]
 内包表記です。
 0からnまでの値のうち、リストLに1が立っている値(論理判定でTrue)だけを抽出したリストを返します。

2.関数hl(n)
・nを左から切り詰めた値のリストを返します。

・s = str(n)
 str関数で文字型変数sにしておきます。

・L = [int(s[i:]) for i in xrange(len(s))]
 内包表記です。
 ループ変数iとして0から文字数分の整数を発生させ、
 s[i:]で位置i以降の文字列を取り出しリストにためます。

3.関数hr(n)
・nを右から切り詰めた値のリストを返します。
 関数hl(n)とほぼ同じです。
 s[:-i]で右からの位置iまでの文字列を取り出してリストにためます。
 i=0のときに文字列全体ではなく空文字になるので、nは別途リストに足します。

4.関数g(L, M)
・return [int(str(s)+str(t)) for s in L for t in M]
 リストLの要素の右側にリストMの要素を組み合わせて結合し数値型にしてためたリストを返します。
 二重ループの内包表記です。
 リストLの要素をs、リストMの要素をtとして、for文の前に渡し、結合した値を作ります。

5.関数f(n)
 問題に合う素数の範囲を絞るにあたり、一番左の桁に置くことができる数字Lと、Lの右に置くことができる数字Rに分けて、LにRを次々と右に連結していくことで問題に合う候補を発生させていきます。

・L = [2, 3, 5, 7]
 一番左に置ける数字のリストです。1桁の素数です。

・R = [1, 3, 7, 9]
 Lの右に置ける数字のリストです。5以外の奇数です。2桁以上の数字で1桁目が5の場合はすべて素数ではありません。

・while len(N)<11:
 ループ開始と終了条件です。問題のとおりに11個たまったら終了とします。

・i += 1
 iは求める素数の桁数です。少ない桁から順に桁数を増やしていきます。

・P, L, Mr, Ml = set(p(10**(i))), g(L, R), [], []
 Pは素数判定する際の素数リストで、i桁をすべて含む値としてその上限値は10のi乗です。set文で集合型に変換しておきます。
 LはリストLの要素の右にリストRの要素を連結したリストで、ループの都度、リストRの要素が右に継ぎ足されていきます。

・for s in L:
 上記で作成した候補リストLの要素をsとして、問題に合うか判定します。

・if set(hr(s))<P: Mr.append(s)
 if set(hl(s))<P: Ml.append(s)
 右から切り詰めた値がすべて素数ならば、リストMrにためます。
 右から切り詰めた値のリストをset文で集合型にして、集合Pにすべて含まれたらリストMrにためます。
 左から切り詰めた値も同様にリストMlにためます。
 
・N += sorted(set(Mr)&set(Ml))
 上記のリストMr、Mlを集合型にして、&演算子で両方に含まれる要素の集合を作成します。
 これで右から切り詰めても左から切り詰めてもすべて素数になる値だと判定できます。
 このような値をsorted関数で小さい順に並べて、リストNにためます。
  
6.関数の外
・関数f()で問題に合う値のリストが戻ってくるので、sum関数でその合計を計算します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
748317 [23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]

2012年8月15日水曜日

Project Euler - Probrem 36

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典:
Project Euler(日本語 翻訳サイト)
     ProjectEuler.net(英語サイト)

Problem 36

585 = 10010010012 (2進) は10進でも2進でも回文数である.
100万未満で10進でも2進でも回文数になるような数の総和を求めよ.
(注: 先頭に0を含めて回文にすることは許されない.)


-----

私の解答例は以下です。畳んでいます。
def g(s): return s==s[::-1]
def f(n): return [i for i in xrange(1, n, 2) if g(str(i)) and g(format(i, "b"))]

n=1000000
print sum(f(n))
 

二進数表記で先頭に0を含めて回文にしてはいけないとのことなので、
回文になったときの最後の桁も0ではいけないことになります。
二進数で最後の桁が1ということは、十進数では奇数ということになります。


2つの関数を使っています。

1.関数g(s)
・引数の文字列sが回文数かどうかを判定します。

・s==s[::-1]
 シーケンス[start:stop:step]です。stepが-1で逆順になります。
 これで文字列sとその逆順文字列が同じであるかをが判定しています。


2.関数f(n)
・十進数表記と二進数表記がともに回文数である奇数の十進数でのリストを返します。
・[i for i in xrange(1, n, 2) if g(str(i)) and g(format(i, "b"))]
 内包表記です。
 まずfor文で、1からnまでの整数を2つ飛び、つまり奇数だけ1つずつループ変数iに設定します。
 そして後ろのif文に渡し、条件に合った値のみfor文の前に送り、そのままリストにためます。
 

 条件部分は、奇数iを文字列にして回文判定した結果と、
 format文で奇数iを二進数変換して回文判定した結果をandで結び、
 両方とも回文数の場合に正とする、という意味です。
 
 なお、format文は第1引数の値を第2引数の書式にする文です。
 "b"の二進数表記のほかに、"d"が十進数、"o"が八進数、"x"が十六進数になります。
  

3.関数の外
・関数f()で問題に合う値のリストが戻ってくるので、sum関数でその合計を計算します。



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

2012年8月14日火曜日

Project Euler - Probrem 35

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
     ProjectEuler.net(英語サイト)

Problem 35
197は巡回素数と呼ばれる.
桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.
100未満には巡回素数が13個ある:
2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である.
100万未満の巡回素数は何個か?


-----


def h(n):
	if n<=2: return []
	L = [2]
	for t in xrange(3, n+1, 2):
		for s in L:
			if not t%s: break
			elif t<s*s: L.append(t); break
	return L

def g(n):
	s, t, M = str(n), str(n)*2, []
	for i in xrange(len(s)):
		L = []
		for j in xrange(i, i+len(s)): L.append(t[j])
		M.append(int("".join(L)))
	return M

def f(n):
	L = set(h(n))
	return [i for i in L if set(g(i))<L]

n = 1000000
L = f(n)
print len(L), L


3つの関数を使っています。

1.関数h(n)
・nまでの素数のリストを返します。
 詳しくは
problem27, problem10を参照してください。

2.関数g(n)
・巡回数のリストを返します。

・s, t, M = str(n), str(n)*2, []
 引数の数字nを文字型にしたものをs、それを2つ連結したものをtとします。
 リストMには順回数をためます。

・for i in xrange(len(s)):
 ループ変数iは、順回数の1文字目です。文字列sの1文字目から最後まで順に1文字ずつ設定します。

・L = []
 for j in xrange(i, i+len(s)): L.append(t[j])
 リストLには順回数を構成する文字を順に1つずつためます。
 ループ変数jにはi番目から元の文字列分の長さだけ、連番を設定します。
 t[j]で文字列tのj番目の文字を取得します。


3.関数f()
・主処理です。

・L = set(h(n))
 nまでの素数リストを集合型に変換します。
 集合型は集合的な演算が可能な変数型です。
 集合的な演算とは、例えば2つの集合の片方がすべて含まれるかとか、
 片方にだけある要素とか、両方にある要素の重複削除した集合、などの演算です。

・return [i for i in L if set(g(i))<L]
 内包表記です。
 まずfor文で、nまでの素数リストLから1つずつループ変数iに設定します。
 そして後ろのif文に渡し、渡された素数iの順回数のリストの要素集合が、集合Lにすべて含まれる、そのようなiだけをfor文の前に送り、そのままリストにためます。
 演算がすべて終わったら、呼び出し元にためたリストを返します。
 

4.関数の外
・関数f()で問題に合う値のリストが戻ってくるので、len関数でその要素数を計算します。


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

2012年8月13日月曜日

Project Euler - Probrem 34

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
     ProjectEuler.net(英語サイト)

Problem 34

145は面白い数である.1! + 4! + 5! = 1 + 24 + 120 = 145となる.
各桁の数の階乗の和が自分自身と一致するような数の総和を求めよ.
注: 1! = 1 と 2! = 2 は総和に含めてはならない.

-----


私の解答例は以下です。畳んでいます。
def h(n):
	if n<=1: return 1
	else: return h(n-1)*n

def g():
	i, m = 0, h(9)
	while True:
		i += 1
		if m*i<10**(i): break
	return m*i

def f():
	d = dict([[i, h(i)] for i in xrange(10)])
	return [i for i in xrange(3, g()) if i==sum([d[int(t)] for t in str(i)])]

L = f()
print sum(L),L



3つの関数を使っています。

1.関数h(n)
・nの階乗を返します。詳しくはproblem20を参照してください。

2.関数g()
・各桁の階乗値の和が元の数と一致するような数を求めるにあたり、その最大可能値、つまり候補として検討すればいい最大値を返します。

・値が小さい場合は各桁の階乗値の方が元の数よりも大きいことがありますが、桁数を増やしていくと、9をn乗して桁数分足した値が、その桁数の最小値(10のn乗)にすら達しない桁数が来ます。
 そのような桁数までチェックすれば十分ということになります。

・具体的には、その桁の最大値として9がn個並んだ数字を想定し、9の階乗値を桁数分足した値が、その桁数の最小値(10のn乗)を下回った場合に、9の階乗値を桁数分足した値を返します。

3.関数f()
・各桁の数の階乗の和が自分自身と一致するような数のリストを返します。
・d = dict([[i, h(i)] for i in xrange(10)])
 階乗値の辞書です。0から9の整数とこれに対応する階乗値をあらかじめ用意しておきます。

・return [i for i in xrange(3, g()) if i==sum([d[int(t)] for t in str(i)])]
 内包表記で書いています。
 まずfor文で、問題に合うように1と2は飛ばして3から最大可能値までの整数をループ変数iとします。
 その後、後ろのif文でiと各桁の階乗値の和が同じ場合だけforの前に渡します。
 そしてfor文の前で渡されたiをリストにためます。
 なお、sum関数により以下で説明する内包表記のリストの合計値を求めています。
 まずfor文でiを文字型にした値から1文字ずつループ変数tとします。
 そしてforの前に渡し、int型に戻して階乗値辞書を検索し対応する階乗値を取得しリストにためます。
 
4.関数の外
・関数f()で問題に合う値のリストが戻ってくるので、sum関数でその合計を計算します。

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

2012年8月12日日曜日

Project Euler - Probrem 33

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
       ProjectEuler.net(英語サイト)

Problem 33

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

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

このような分数のうち、1より小さく分子・分母がともに2桁の数になるような自明でないものは、4個ある.
その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ.

-----

私の解答例は以下です。畳んでいます。

def gcd(a, b):
	if a<b: a, b = b, a
	if b: return gcd(b, a%b)
	else: return a

def h(i, s):
	L = [t for t in str(i) if t!=s]
	return float("".join(L))

def g(m, n):
	for s in str(m):
		for t in str(n):
			if s==t: return s

def f():
	si = sj = 1
	for i in xrange(10, 100):
		if not i%11: continue
		for j in xrange(10, i):
			if not j%11: continue
			s = g(i, j)
			if s>"0" and h(i, s) \
			and float(j)/float(i)==h(j, s)/h(i, s):
				si *= i
				sj *= j
	return si//gcd(si, sj)

print f()


4つの関数を使っています。

1.gcd(a, b)
・「ユークリッドの互除法」を使用して最大公約数を返します。
 説明はProblem5を参照してください。

2.関数g(m, n)
・n,m両方にある同じ文字を返します。
 「正しくない約分」で削除する1文字を探す操作に相当します。

・for s in str(m):
  for t in str(n):
 m,nそれぞれをstr関数で文字型にして、1文字ずつループ変数s,tとして取り出します。

・if s==t: return s
 上記のようなs,tで値が等しい場合、その値を返します。
 等しくない場合は何も記述していませんが、初期値Noneが返ります。
 

3.関数h(i, s)
・引数iの構成文字から文字sを取り除き、浮動小数点型にして返します。
 正しくない約分で1文字削除する操作に相当します。

・L = [t for t in str(i) if t!=s]
 内包表記で記述しています。
 まず中ほどのfor文を実行し、引数iをstr関数で文字型にしてから1文字ずつ取り出しループ変数tにセットします。
 次に後ろのif文を実行し、先ほどのtと引数sが異なるか判定し、判定に通った場合のみ、forの前に引渡します。
 forの前に引き渡されたそのようなtをリストLにためます。

・return float("".join(L))
 上記リストLの要素を連結し、float関数で不動小数点型に変換します。
 イテレータの要素を連結するjoinメソッドは区切り文字のメソッドです。
 区切り文字無しの場合は、今回のように""のメソッドを使います。
 pythonを始めた頃は、連結するデータ側のメソッドでなく、
 区切り文字のメソッドというところに違和感を感じていましたが、
 今ではすっかり慣れました。
 
4.f()
・主処理です。

・si = sj = 1
 問題に合う分数の分母と分子をsi,sjとして、掛け算累積するため初期値は1とします。

・for i in xrange(10, 100):
 if not i%11: continue
 ループ変数iは分母です。10から99までの2桁の整数を範囲です。
 ただし、「正しくない約分」をするためには異なる数字で構成される必要がありますので、11で割り切れない値だけを対象にします。
 直後のif文で11で割った余りがない、つまり余り0、論理判定でFalseとなる場合は次の値へ進みます。

・for j in xrange(10, i):
 if not j%11: continue
 ループ変数jは分子です。1より小さい分数の分子なので、分子は分母より小さな値になります。
 範囲は10からi-1までの整数となります。if文の考え方は上記の分母のときと同じです。

・s = g(i, j)
 「正しくない約分」で消去対象となる数字をsとします。

・if s>"0" and h(i, s) \
 and float(j)/float(i)==h(j, s)/h(i, s):
  si *= i
  sj *= j
 問題に合う分数かチェックします。
 チェック条件は以下の3つで順ににandでつないでいます。
 条件に合えば、分母分子それぞれを掛け算累積します。
 1.「正しくない約分」で消去対象となる数字が0でないこと。0は「自明な約分」になるため。
 2.「正しくない約分」をした場合の分母が0でないこと。
 3.「正しくない約分」をした場合の値が約分前の値と等しいこと。
 
・return si//gcd(si, sj)
 「問題に合う分数の積を正しく約分したときの分母」を返します。
 「問題に合う分数の積」の分母、分子はそれぞれsi,sjです。
 このsiを、分母分子の最大公約数で割った値が、戻す値となります。
 

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

2012年8月7日火曜日

Project Euler - Probrem 32

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
       ProjectEuler.net(英語サイト)

Problem 32
7254は面白い性質を持っている. 39 × 186 = 7254と書け,
掛けられる数/掛ける数/積に1から9の数が1回ずつ出現する.

掛けられる数/掛ける数/積に1から9の数が1回ずつ出現するような積の総和を求めよ.

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

-----

私の解答例は以下です。畳んでいます。

def f(m, n):
	L = []
	for i in xrange(10**(m-1), 10**m):
		for j in xrange(10**(n-1), 10**n):
			k = i*j
			s = str(i)+str(j)+str(k)
			if (len(s)==9) and ("0" not in s) \
			and (len(s)==len(set(list(s)))):
				L.append([i, j, k])
	return L
	
L = f(1,4)+f(2,3)
print sum(set([s[2] for s in L]))
	


・問題の条件に合う掛け算の桁数は以下の組合せのいずれかになります。
 1桁×4桁=4桁、2桁×3桁=4桁。

1.関数f(m, n)
・m桁とn桁の掛け算において、掛けられる数/掛ける数/積に1から9の数が1回ずつ出現する場合の、掛けられる数/掛ける数/積の組合せのリストを返します。

・for i in xrange(10**(m-1), 10**m):
  for j in xrange(10**(n-1), 10**n):
 ループ変数i、jはそれぞれm桁、n桁の整数です。演算子**はべき乗です。

・k = i*j
 s = str(i)+str(j)+str(k)
 kは積、sは掛ける数/掛けられる数/積を構成する数字を文字扱いで連結したものです。
 
・if (len(s)==9) and ("0" not in s) \
and (len(s)==len(set(list(s)))):
  L.append([i, j, k])
 問題の条件に合えば、数/掛ける数/積の組合せリストをリストLに貯めていきます。問題の条件とは以下の3つで、順にandでつなぎました。
 1.掛けられる数/掛ける数/積を構成する文字列長は9。
 2.掛けられる数/掛ける数/積を構成する文字に0は含まれない。
 3.掛けられる数/掛ける数/積を構成する文字列と、これを重複削除した文字列が同じ長さ。
 なお、最後の部分は、list関数で構成文字列をリスト化し、set関数で要素を一意にして、len関数で要素数を求めています。
\演算子は継続行を示しています。

2.関数の外側
・L = f(1,4)+f(2,3)
 関数fで、「1桁×4桁」と「2桁×3桁」について問題に合う
 掛けられる数/掛ける数/積の組合せを求め、1つにまとめてリストLとします。
 
・print sum(set([s[2] for s in L]))
 上記のリストLから要素1つひとつを取り出しsとし、forの前に送り、sの中のインデックス値2の要素である積を取り出して、順にリストに収めます。(内包表記)
 さらにset関数で重複削除し、sum関数で合計を求めます。

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

2012年8月5日日曜日

Project Euler - Probrem 31

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
   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を作る方法は何通りあるか?

-----


私の解答例は以下です。畳んでいます。
def f(n, L, i=0):
	cnt, imax = 0, len(L)-1
	for s in xrange(0, n+1, L[i]):
		t = n-s
		if t<0: break
		if i<imax: cnt += f(t, L, i+1)
		if i==imax and t==0: cnt += 1
	return cnt
	
L = [1, 2, 5, 10, 20, 50, 100, 200]
print f(200, sorted(L, reverse=True))

1.関数f(n, L, i)
・nペンスをリストLの硬貨(単位:ペンス)で作る方法が何通りあるかを返します。
 iは試行する硬貨がリストLの何番目かというインデックス値です。
・関数fは、自分で自分自身を呼び出すという再帰呼び出しをしますので、
 どの硬貨で試行するかというインデックス値をiとします。初期値は0です。
・Lは大きい順に並べておきます。
 大きい順に硬貨を当てはめていった方が少ない試行回数で済むからです。


・cnt, imax = 0, len(L)-1
 初期値です。通り数カウンターcntは0クリアしておきます。
硬貨リストのインデックス値iの最大値imaxは硬貨リストの要素数-1です。


・for s in xrange(0, n+1, L[i]):
 ループ変数sは、0からnの範囲で試行する硬貨金額刻みの値です。
 つまり、試行する硬貨を0枚から順に増やしたときのその硬貨での金額です。
 例えば、100ペンスならば、0,100,200・・・と変化します。


・t = n-s
 対象金額nから使用硬貨による金額を差し引き、余りをtとしています。
 つまり、tはまだこの時点では割り当て切れていない余り金額です。


・if t<0: break
 余り金額tが0より小さい場合、現時点での割り当て枚数での金額では
 もう大きすぎてダメなので、ループ変数sのループを終了します。


・if i<imax: cnt += f(t, L, i+1)
 硬貨リストのインデックス値iがその最大値imaxよりも小さい場合は、
 余り金額tを1つ小さい金額の硬貨(i+1番目の硬貨)で割り当ててできる通り数を
 求めて、件数カウンタに累積します。
 このときの1つ小さい金額の硬貨の場合を当関数を再帰呼び出しして求めます。


・if i==imax and t==0: cnt += 1
 硬貨リストの最後まで検討した結果、余り金額が0ならば、現在の割り当てで
 元の金額がくずせたわけなので、件数カウンタを当パターン分として+1します。


2.関数の外側
・L = [1, 2, 5, 10, 20, 50, 100, 200]
 硬貨リストです。問題の通り、小さい順に並べてリストに設定しました。

・print f(200, sorted(L, reverse=True))
 sorted関数でリストLをソートします。reverseキーワードをTrueにして降順(値の大きい順)に直しています。
 なお、似た関数でsort関数もありますが、引数にリストオブジェクトしか許容せず、その引数に設定したリストオブジェクトを直接並び替えてしまうので、私はあまり使いません。sorted関数は引数に設定したイテラブルオブジェクトはそのままで、ソート結果を別オブジェクトとして作成します。



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