漫ろ草 SozoroGusa

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

2017-03-20T09:19:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１２５「連続する平方数の和で表せる回文数の和」
回文数 595 は連続する平方数の和で表すことができるという面白い性質を持つ:
6² + 7² + 8² + 9² + 10² + 11² + 12²

1000 未満で連続する平方数の和で表せる回文数はちょうど 11 あり, その合計は 4164 である.
正の整数の平方のみをこの問題では扱うため, 1 = 0² + 1² は含めないことに注意せよ.

回文数でありかつ連続する平方数の和で表せる, 10⁸ 未満のすべての数の合計を求めよ.

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

私の回答例は以下の通りです。

def f(nmax):
	L = []
	M = [i*i for i in xrange(1, int(nmax ** 0.5)+1)]
	
	for i in xrange(len(M)):
		s = M[i]
		for j in M[i+1:]:
			s += j
			if s >= nmax: break
			t = str(s)
			if t == t[::-1]: L.append(s)
			
	L = set(L)
	return sum(L), len(L)
	
if __name__=="__main__":
	nmax = 10**8
	s, k = f(nmax)
	print "値n ＜", nmax, "の場合：合計 =", s, "、個数 =", k

平方数の和で表せる数を計算し、それが回文数ならためるようにします。

１．関数f(nmax)
・値nの最大値を受け取り、平方数の和で表せる回文数の合計値と個数を返します。

・M = [i*i for i in xrange(1, int(nmax ** 0.5)+1)]
　Mは、必要な平方数の二乗値のリストです。
　二乗値がnmax以下なので、二乗する値iはnmaxの平方根の整数部分までです。
　forループ上の終端値はこの値を +1 した値となります。

・for i in xrange(len(M)):
　ループ変数iは、二乗値リストMの要素のうち、和の計算で使用する最初の値のインデックス値です。

・s = M[i]
　sは二乗値の和です。初期値は二乗値リストMのi番目の値です。

・for j in M[i+1:]:
　　s += j
　ループ変数jは、二乗値リストMのインデックスi番目より後の値です。
　sにjを累積していきます。

・if s >= nmax: break
　二乗値の和sの最大値チェックです。nmax以上になったら処理終了です。

・t = str(s)
　if t == t[::-1]: L.append(s)
　二乗値の和sの回文数チェックです。
　二乗値の和sを文字型に変換してtとし、各桁を逆順に並べた文字列と一致するかを判定します。この回文数判定は問３６のときと同じです。
　回文数の場合、リストLにためます。

・L = set(L)
　リストLをset文で集合型にすることで、その要素の値をユニークにします。

・return sum(L), len(L)
　リストLの合計値と個数を返却します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
値n ＜ 100000000 の場合：合計 = 2906969179 、個数 = 166

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

2017-03-18T21:08:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１２４「順序付き根基」
n の"根基"(radical)は, rad(n) で表し, n の素因数の積を意味する.
例えば 504 = 23 × 32 × 7 であるから, rad(504) = 2 × 3 × 7 = 42 である.
1 ≦ n ≦ 10 に対して rad(n) を計算し, rad(n) を対象にソートし, rad(n) が同じ場合は n を対象にソートすると以下のようになる.

未ソート　ソート済み
n rad(n) n rad(n) k
1 1     1 1     1
2 2     2 2     2
3 3     4 2     3
4 2     8 2     4
5 5     3 3     5
6 6     9 3     6
7 7     5 5     7
8 2     6 6     8
9 3     7 7     9
10 10    10 10    10

E(k) をソートした表の n の列の k 番目の要素とする.
例えば, E(4) = 8, E(6) = 9 である.

rad(n) を 1 ≦ n ≦ 100000 でソートした場合, E(10000) を求めよ.

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

私の回答例は以下の通りです。

def f(nmin, nmax, k):
	P = p(nmax)
	E = []
	for n in xrange(nmin, nmax + 1):
		if n < 1: continue
		L = [1]
		m = n
		for i in P:
			if m % i == 0:
				L.append(i)
				while m % i == 0: m //= i
			if m == 1: break
			
		r = mul(L)
		E.append((r, n, L[1:]))
		
	Es = sorted(E)
	return Es[k-1]

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 mul(L): return reduce(lambda x,y:x*y, L)

if __name__=="__main__":
	nmin, nmax, k = 1, 100000, 10000
	r, n, L = f(nmin, nmax, k)
	print nmin, "≦ n ≦", nmax, "のとき、E(", k, ") =", n
	print "rad(", n, ") =", " x ".join([str(i) for i in L]), "=", r

１．関数f(nmin, nmax, k)
・nの最小値と最大値、問題で求めるk番目として指定するkを受け取り、
　E(k)をソートした表の、k番目の(根基r, n, nの素数リスト)のタプルを返します。

・P = p(nmax)
　Pは必要な素数のリストです。nmax以下の素数が小さい順に入っています。

・for n in xrange(nmin, nmax + 1):
　ループ変数nは、nmimからnmaxまで１つずつ大きくしながら処理します。

・if n < 1: continue
　nが1未満は処理対象外なので処理せず次のnへ進みます。

・L = [1]
　Lはnを構成する素因数リストです。
　根基の計算の掛け算のため、1を設定して初期化しておきます

・m = n
　mはnを素因数で割った商です。素因数が判明する都度、値が変化します。

・for i in P:
　ループ変数iは素因数リストPから小さい順に取り出した値です。

・if m % i == 0:
　　L.append(i)
　　while m % i == 0: m //= i
　mが素数iで割り切れる場合、素因数リストLに追加し、mを素因数iで割れるだけ割り込んでおきます。

・if m == 1: break
　mが1になれば素因数分解の終了で、素数iのループを終了します。

・r = mul(L)
　rはnの根基です。関数mulで素数リストLの全要素の積を求めます。

・E.append((r, n, L[1:]))
　Eは、(nの根基r, n, nの素因数リストL)のタプルをためるリストです。

・Es = sorted(E)
　Esは上記Eに求める範囲のタプルをため終わったところで、ソートします。
　ソートキーは、指定しない場合は先頭からになるので、
　この場合、根基r、nの順にソートキーとして採用されます

・return Es[k-1]
　求めるk番目の値は、ソート済リストEsのインデックスk-1番目の値です。

２．関数P(n)
・n以下の素数を小さい順にもつリストを返します。問３７で作成した関数を流用しました。

３．関数mul(L)
・リストLの全要素の積を返します。問１１０で作成した関数を流用しました。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
1 ≦ n ≦ 100000 のとき、E( 10000 ) = 21417
rad( 21417 ) = 3 x 11 x 59 = 1947

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

2017-03-16T20:57:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１２３「素数の自乗で割った余り」
p_n を n 番目の素数とする. (p1 = 2, p2 = 3, ...)
r を (p_n - 1)ⁿ + (p_n + 1)ⁿ を p_n² で割った余りとする.

例えば, n = 3 のとき, p₃ = 5 であり, 43 + 63 = 280 ≡ 5 mod 25.
余り r が 10⁹ より大きくなる n の最小値は 7037 である.
余り r が 10¹⁰ より大きくなる最初の n を求めよ.

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

私の回答例は以下の通りです。

def f(rmin):
	for i, p in enumerate(P()):
		n = i + 1
		if n % 2:
			r = (2*n*p) % (p*p)
			if r > rmin: return n, p, r
		
def P():
	L, i = [2], 1
	yield 2
	while True:
		i += 2
		for j in L:
			if not i%j: break
		else:
			L.append(i)
			yield i
			
if __name__=="__main__":
	rmin = 10**10
	n, p, r = f(rmin)
	print "n =", n, "(素数p =", p, ", 余りr =", r, ")"

１．関数f(rmin)
・最小の余りrminを受け取り、問題に合うn番目の素数pとそのときの余りrについて、n,p,rを返します。

・この問題は問１２０の続きの問題です。
　問１２０では、
(a - 1)ⁿ + (a + 1)ⁿ を n² で割った余りをrとしていましたが、
　本問では、
(p_n - 1)ⁿ + (P_n + 1)ⁿ を p_n²で割った余りをrとしています。

・問１２０の式に、a=p_nを代入すると以下のことがわかります。
　余りrは、nが偶数か奇数かでパターンが異なります。
　nが偶数の場合、余りrはaに関わらず 2 です。
　nが奇数の場合、余りrは 2np_n をp_n²で割った余りです。
　
・pは素数なので、2以外はすべて奇数です。
　題意から答えは明らかに2よりも大きく、必ず奇数です。
　このため、nが偶数のときは処理せず飛ばします。

２．関数P()
・素数を小さい方から昇順に返すジェネレーターです。呼び出しの都度、次の素数を返却します。
・問１０８で作成した関数を改良しました

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
n = 21035 (素数p = 237737 , 余りr = 10001595590 )

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

2017-03-12T09:08:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１２２「効率的なべき乗計算」
n15を求めるのに最も単純な方法では 14 回の掛け算が必要である.

n × n × ... × n = n¹⁵
しかし2進法を用いれば, 6 回の掛け算で計算できる.

n × n = n²
n² × n² = n⁴
n⁴ × n⁴ = n⁸
n⁸ × n⁴ = n¹²
n¹² × n² = n¹⁴
n¹⁴ × n = n¹⁵
ところがたった 5 回の掛け算のみでも計算できる.

n × n = n²
n² × n = n³
n³ × n³ = n⁶
n⁶ × n⁶ = n¹²
n¹² × n³ = n¹⁵
m(k)を n^k を求めるのに必要最低限な掛け算の回数と定義する.
たとえば m(15)=5 である.

1 ≦ k ≦ 200 に対し, Σ m(k) を求めよ.

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

私の回答例は以下の通りです。

def f(n1, n2):
	L = [[] for i in xrange(n2 + 1)]
	M = [0 for i in xrange(n2 + 1)]
	L[1].append([])
	
	for i in xrange(1, n2):
		for m in L[i]:
			s = m + [i]
			t = len(s)
			for j in s[::-1]:
				for k in s[::-1]:
					u = j + k
					if not (i < u  <= n2): break
					if 0 < M[u] < t: continue
					if s in L[u]: continue
					L[u].append(s)
					M[u] = t
	return sum(M[n1:])
	
if __name__=="__main__":
	print f(1, 200)

掛け算するときの掛ける数の指数を足していき、指定数に達するまでの最小回数を求めます。
１度掛け算して作成した累乗値の指数は再利用できます。

掛け算で使用した指数値のユニークな配列を作成し、
この要素と掛け算で到達したその指数値自身から、
値を２つ取り出し、その和の累乗値の配列として順に計算していきます。
このとき、指数値のユニークな値の配列は複数パターンできることがあり、いずれも必要です。
例えば、n=5の場合、到達するパターンは[1,2,3]と[1,2,4]の２つあり、
これを元にさらに大きな指数値について計算していくとき、
どちらの系統を使った方が最小回数になるか、この段階では判断つかないためです。

また、掛け算を実施した回数を別のリストに保存しておき、最後にその合計を求めます。

１．関数f(n1, n2)
・題意にあるm(k)について、n1≦k≦n2のときのm(k)の和を返します。

・L = [[] for i in xrange(n2 + 1)]
　M = [0 for i in xrange(n2 + 1)]
　Lは、そのインデックス位置の値の累積値を求めるときの「掛け合わせた指数値のユニークリスト」のリストです。
　Mは、そのインデックス位置の値の累積値を求めるときの最小掛け算回数のリストです。
　例えば、n=5の場合、L[5]=[[1, 2, 3], [1, 2, 4]]、M[5]=3　です。

・L[1].append([])
　初期値です。これでn**1の場合に、この指数値までに使用した指数値のリストは無いが、この指数値そのもの（つまり、1）を使用して累乗していくことが可能になります。

・for i in xrange(1, n2):
　ループ変数iは、1からn2に至るインデックスです。累乗値計算の範囲です。

・for m in L[i]:
　ループ変数mは「掛け合わせた指数値のユニークリスト」です。

・s = m + [i]
　sは「掛け合わせた指数値のユニークリスト」に、それより到達した指数値iそのものを追加したリストです。
　次の累乗値計算の元になる指数値のリストです。

・t = len(s)
　tは、リストsの次の累乗で生成できる累乗値までの掛け算回数の候補です。

・for j in s[::-1]:
　for k in s[::-1]:
　ループ変数jとループ変数kは、リストsから取り出した２つの要素です。
　大きい値から順に、次の値を計算していきます。

・u = j + k
　uは、次の掛け算で到達できる累乗値の指数です。

・if not (i < u <= n2): break
　i < u < n2 なら書き換え対象です。
　そうでない場合は、kはそれ以下の値しかないので、条件は満たせずループは終了です。

・if 0 < M[u] < t: continue
　0 < M[u] < tの場合、今までの結果よりも掛け算回数が少ないパターンなので、次のパターンを考えます。
　そうでない場合、ここまでの処理結果よりも同じか長い掛け算回数のパターンなので処理続行です。

・if s in L[u]: continue
　リストsは指数値uのときの「掛け合わせた指数値のユニークリスト」に既にあれば、次のパターンを考えます。

・L[u].append(s)
　M[u] = t
　ここまでくれば題意の満たす初めての「掛け合わせた指数値のユニークリスト」になので、掛け算回数tとともに保存します。

・return sum(M[n1:])
　iのループが終了したところで、n1以上の掛け算回数の和を返却します。

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

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

2017-03-10T21:27:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１２１「円盤ゲームの賞金額」
袋の中に赤い円盤 1 枚と青い円盤 1 枚が入っている.
ある賭けゲームにおいて, プレイヤーは円盤を 1 枚ランダムに取り出しその色を記録する.
各ターンの終わりに円盤は袋に戻され, 追加の赤い円盤 1 枚が袋に足され, そして次の円盤がランダムに取り出される.
プレイヤーはゲームをプレイするのに 1 ポンドを支払い, ゲーム終了時に青い円盤を赤い円盤より多く取り出していれば勝利する.
ゲームが 4 ターンプレイされたとすると, プレイヤーが勝利する確率はちょうど11/120 となる.
したがって, 胴元が赤字の見込みになるまでにこのゲームで勝ちに対して割り当てるべき賞金の最大は 10 ポンドとなるであろう.
支払いはすべてポンドの整数倍であり,
またゲームをプレイするのに支払われたもともとの 1 ポンドを含んでいるため,
与えられた例では実際にはプレイヤーは 9 ポンドを獲得することに注意しよう.
15 ターンがプレイされるゲーム 1 回に割り当てられるべき賞金の最大を求めよ.

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

私の回答例は以下の通りです。

def mul(L): return reduce(lambda x,y: x*y, L)

def f(n):
	import itertools
	m = n//2 + 1
	c = 0
	L = [i+2 for i in xrange(n)]
	Ls = set(L)
	
	for i in xrange(m, n+1):
		for t in itertools.combinations(L, i):
			u = Ls - set(t)
			if u: c += mul([s-1 for s in u])
			else: c += 1
			
	s = mul(L)//c
	return s
	
if __name__=="__main__":
	print f(15)

１．関数f(n)
・n回のターンで得られる賞金の最大値を求めます。

・m = n//2 + 1
　mは勝利に必要な勝ち数です。n回のターンのうち半分以上で勝ちです。

・L = [i+2 for i in xrange(n)]
　Lは各ターンごとの全円盤数のリストです。
　リストLのi番目の要素は、iターン目に円盤を取り出す確率の分母でもあります。

・Ls = set(L)
　Lsは全円盤数リストLを集合型にしたものです。後で集合演算で使います。

・for i in xrange(m, n+1):
　ループ変数iは勝ち数です。
　必要な最低勝ち数mから全勝の場合のnまでの値を取ります。

・for t in itertools.combinations(L, i):
　ループ変数tは勝ち数iの場合に青円盤を取り出すターンでの全円盤数、の組み合わせです。
　つまり、青円盤を取り出すターンごとのそれぞれの確率の分母の組み合わせでもあり、
　各ターンごとの全円盤数リストLから、勝ち数i個の要素を取り出した組み合わせです。

・u = Ls - set(t)
　uは全円盤数リストLsからループ変数tの要素を集合演算で差し引いたリストです。
　つまり、赤円盤を取り出すターンでの全円盤数、の組み合わせです。
　これは、青円盤を取り出す１つのパターンの中で、異なる赤円盤を取り出す。場合の数です。
　なので、uの要素を全部掛け合わせると、青円盤を取り出す１つのパターンの。場合の数になります。

・if u: c += mul([s-1 for s in u])
　else: c += 1
　cは青円盤を取り出す１つのパターンの、場合の数の累積値です。
　青円盤を取り出す1つのパターンの場合の数は、uの要素を全部掛け合わせた値なので
　これを累積します。
　ただし、全部青円盤、つまり全ターンで勝つ場合、赤円盤が出ないためリストuが空で
積として計算できないので固定で１パターン分を累積します。

・s = mul(L)//c
　return s
　求める値sは１ゲーム当たりの最大賞金で、勝率の逆数です。
　全部のパターン数を、勝ちパターン数で割った値の小数点以下切り捨て値です。
　問題中の例の４ターンの場合、勝率11/120なので、最大賞金は120/11 = 10.9 ...で10です。
　全部の場合の数は、各ターンごとの全円盤数の積です。
　これを勝つパターン数cで割った値の整数値が、求める最大賞金です。

２．関数mul(L)
・リストLの全要素の積です。問１１０で作成した関数を流用しました。

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

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

2017-03-06T21:15:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１２０「自乗で割った余り」
(a-1)ⁿ + (a+1)ⁿ を a² で割った余りを r と定義する.
例えば, a=7, n=3 の時, r=42 である: 6³ + 8³ = 728 ≡ 42 mod 49.
n が変われば r も変わるが, a=7 の時 r の最大値 rmax は 42 であることがわかる.
3 ≦ a ≦ 1000 において, Σ rmax を求めよ.

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

私の回答例は以下の通りです。

def f(s, e): return sum([a*(a - (2- a%2)) for a in xrange(s, e+1)])
start, end = 3, 1000
print f(start, end)

まず、(a+1)ⁿ + (a-1)ⁿ　を展開してみます。
(a+1)ⁿ + (a-1)ⁿ ÷ a² の余りについて、手計算して様子を見てみます。

n=2のとき
(a+1)² + (a-1)²
= (a² + 2*a + 1) + (a² - 2*a + 1)
= 2(a² + 1)
なので、a²で割った余りは、2です。

n=3のとき
(a+1)³ + (a-1)³
= (a³ + 3*a² + 3*a + 1) + (a³ - 3*a² + 3*a - 1)
= 2(a³ + 3*a)
= 2(aⁿ * n*a)
なので、a²で割った余りは、2*n*aのa²での余り、2*n*a÷a²の余りです。

n=4のとき
(a+1)⁴ + (a-1)⁴
= (a⁴ + 4*a³ + 6*a² + 4*a + 1) + (a⁴ - 4*a³ + 6*a² - 4*a + 1)
= 2(a⁴ + 6*a²) + 2
なので、a²での余りは、2です。

上記より、展開式をaの乗数の多い項から順に並べたとき、
・aの係数は二項係数でパスカルの三角形のそれぞれの値です。
・(a+1)と(a-1)のn乗同士をたすことで、偶数番目の項は互いに打ち消し合います。
・題意からn≧3なので、aの2乗以上の項は全部割り切れ、余りはでません。
なので、
nが奇数の場合、余りはa¹の項だけみればよく、2*n*a÷(a²)の余りです。
nが偶数の場合、余りはa⁰の項だけみればよく、2です。
なので、nが奇数の場合だけ考えれば十分です。
割り算の余りは「割られる数」＝「割る数の倍数」のときに0になり、
割られる数がこの値よりも小さいができるだけ大きな値というのが求める値です。
また、「割られる数」が「割る数」を超えると、
それまでに出現した余りが再度循環して出現するので、
「割られる数」が「割る数」以下の場合だけ考えれば十分です。
特に、「割られる数」＝「割る数」の場合、商が1で余り0。
「割られる数」がこの値よりも小さいができるだけ大きな値の場合、
商が0で残りが余りになり、「割られる数」＝「余り」になります。
そこでまず、「割られる数」＝「余り」の場合のnを計算します。
2an = a²
n = a/2
nがこの値よりも小さくできるだけ大きな値のとき、余りが最大になります。
ところで、題意からnもaも整数なので、aが奇数か偶数かで場合分けが必要です。
(1)aが奇数の場合
n = a/2よりも小さくできるだけ大きな値は、n = (a-1)/2 です。
このときの求める値は、2an = 2a(a-1)/2 = a(a-1) です。
(2)aが偶数の場合
n = a/2よりも小さくできるだけ大きな値は、n = (a-2)/2 です。
このときの求める値は、2an = 2a(a-2)/2 = a(a-2) です。
aを奇数か偶数かで場合分けして上記の値を累計すればいいことになります。

１．関数f(s, e)
s以上e以下の値について、問題文にある最大値を返します。
・sum([a*(a - (2- a%2)) for a in xrange(s, e+1)])
　%演算子は余りなので、
　「a%2」は、aが奇数なら1、偶数なら0です。
　「2 - a%2」は、aが奇数なら1、偶数なら2です。
　「a*(a - (2- a%2))」は、aが奇数ならa(a-1)、aが偶数ならa(a-2)　です。
　sからeまで順にaのforループで上記の計算結果を配列に入れて、sum関数で合計します。
　ループは内包表記をしています。

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

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

2016-02-29T22:30:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１１９「数字べき乗和」
512 という数は興味深い数である.
というのも, 各桁の和を何乗かしたものに等しくなっているからである:
5 + 1 + 2 = 8, 8³ = 512 である.
この特性を持つ他の数は例えば 614656 = 28⁴である.
この数列の第 n 項を a_n と定義し, また 2 桁以上であるとしよう.
a₂ = 512, a₁₀ = 614656 となる.
a₃₀ を求めよ.

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

私の回答例は以下の通りです。

def f(n):
 c = 0
 for d in xrange(2, n+2):
  for i in xrange(d, 9*d+1):
   for j in xrange(2, d+1):
    a = i**j
    t = [int(k) for k in str(a)]
    if d==len(t) and i==sum(t):
     c += 1
     if c==n: return a, i, j
    
n = 30
s, i, j = f(n)
print s,"( =", i, "**", j, ")"

小さい数値から順に各桁を和を累乗して元の数になるかチェックすると、
とても１分ルールに間に合いません。
そこで、べき乗した数値を順に用意して元の数との桁数一致と各桁和をチェックします。

１．関数f(n)
・問題の数列の第n項の値を返します。
　数列aの第1項から順にチェックして第n項を検出したときに処理を終了します。

・for d in xrange(2, n+2):
　ループ変数dは求める値の桁数です。
　取り得る値の範囲は、2桁以上で、第n項ではたかだかn+1桁です。

・for i in xrange(d, 9*d+1):
　ループ変数iは、求める値a=i**jのときのiであり、また題意によりaの桁数和でもあります。
　取り得る値の範囲はaが全桁1の数値ならばd、全桁9の数値ならば9*dなのでこの間です。

・for j in xrange(2, d+1):
　ループ変数jは求める値a=i**jのときのj、べき乗です。
　取り得る値の範囲は2乗以上なので最低2、べき乗数はたかだかaの全体桁数以内です。

・a = i**j
　t = [int(k) for k in str(a)]
　aは候補の値で、tは候補aの各桁の値リスト

・if d==len(t) and i==sum(t):
　桁数一致、かつ元の数字＝数字のべき乗の桁数和が一致するかをチェックし、
　成り立てば件数カウンタcを+1し、その件数が限度nになれば終了です。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
248155780267521 ( = 63 ** 8 )

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

2016-01-30T14:05:00.001+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１１８「パンデジタル素数集合」
1 から 9 の全ての数字を使い, 自由につなげることで 10 進数の数字を作り,複数の集合を作ることができる.
集合 {2,5,47,89,631} は面白いことに全ての要素が素数である.
1 から 9 の数字をちょうど 1 個ずつ含み, 素数の要素しか含まない集合はいくつあるか?

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

私の回答例は以下の通りです。

def h(n):
 if n<2: return 0
 if n<4: return n
 if (not n%2): return 0
 for i in xrange(3, int(n**.5)+1, 2):
  if not n%i: return 0
 return n

def f(L, Lc=[], d=0, cnt=0):
 if d==9:
  return [], cnt+1
 bk = Lc[:]
 for i in xrange(len(L)):
  Lc = bk[:]
  s = 0
  for j in L[i:]: s = s*10 + j

  if Lc and Lc[0]<s: continue
  if h(s):
   Lc.insert(0, s)
   Lc, cnt = f(L[:i], Lc, d+len(L)-i, cnt)
  return Lc, cnt

import itertools
L0 = [i for i in xrange(1, 10)]
v = 0
for t in itertools.permutations(L0):
 L, c = f(t)
 v += c
print "cnt:", v

1から9までの数字の順列を発生させ、その１つひとつについて、素数だけの要素に分解していきます。
ただし、その分解できた要素の順番が異なっていても１つとして数えるため、要素が昇順に並んでいるパターンだけの件数を数えます。
総当たりですが１分ルールは守れるのでよしとします。

１．関数f(n)
・リストLの要素を左から素数で区切り、累積用リストLcに格納していきます。
　dは確定した全要素の合計桁数で、cntは全素数要素のパターン数です。
　最終的に必要な値は件数だけですが、この関数を回帰呼び出しで使えるようにするために、戻り値は累積用リストLcと求める件数とします。

・回帰呼び出しなので、最初は終了条件の記述が鉄則です。
　確定した全要素の合計桁数が9ならば、1～9の数字の全部を使い切っていて、累積用リストLcに求めるパターンが格納されているので、空の累積用リストとカウンタcntを+1して戻ります。

・累積用リストLcのバックアップを取ります。
　左から1桁ずつ区切って要素を確定していく中で、区切り方が条件に合わない場合に直前状態に戻すためです。

・for j in L[i:]: s = s*10 + j
　位置iから右側を切り取り L[i:]とし、
　jのforループ中で、1けたずつ取り出して10倍しながら足していき数値化しsとします。

・if Lc and Lc[0]<s: continue
　重複を避けるため、全要素が昇順になる場合だけ採用し、それ以外は次へ。

・if h(s):
　　Lc.insert(0, s)
　　Lc, cnt = f(L[:i], Lc, d+len(L)-i, cnt)
　関数hで数値sの素数判定します。
　素数ならば、累積用リストLcに右から追加します。
　そしてリストLの位置iから左側L[:i]について、当関数fを再起呼び出しして、さらに素数の要素があるか探索します。
　
２．関数h(n)・問１１１の素数判定を改良しました。
　2未満に素数は無く、2と3は素数。ここまではif文で直接判定します。
　その後は偶数を外し、3から先の奇数の倍数を外します。

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

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

2015-11-14T09:32:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１１７「赤タイル, 緑タイル, そして青タイル」
黒い正方形のタイルと,
2 ユニットの長さの赤のタイル,
3 ユニットの長さの緑のタイル,
4 ユニットの長さの青のタイルから選んで組み合わせて,
5 ユニットの長さの 1 列をタイルで敷く方法はちょうど 15 通りある.

長さ 50 ユニットの 1 列をタイルで敷く方法は何通りあるか.

注: この問題は Problem 116 に関連する

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

私の回答例は以下の通りです。

def e(n, m, d):
	if n not in d:
		d[n] = sum([e(n-i, m, d) for i in xrange(1, m+1)])
	return d[n]

def f(n, m):
	d = {0:0}
	for i in xrange(1, m+1): d[i] = e(i, i-1, d)+1
	return e(n, m, d)

n = 50
m = 4
s = f(n, m)
print s

4個以下の長さのブロック4種類を使って一列にタイルを敷きます。
パターン数辞書dに使うタイルの分の初期化をして求めます。

１．関数e(n, m, d):
・全体がn個で、m個以下のブロックからできているパターン数を返します。
・dは全体がn個の場合のパターン数の辞書（連想配列）です。
　1度計算した値はこの辞書に格納して重複して計算しないようにします。
・全体がn個になる場合のパターン数は、
　ループ変数iが1からmまで１つずつ変化しながら、全体がn-i個の状態の直後にi個ブロックを1つ置く場合のパターン数の累積値です。

２．関数f(n, m)
・全体がn個で、m個以下のブロックからできているパターン数を返します。
・まず、パターン数辞書の初期状態を準備します。
　キー=0の場合、パターン数は0です。
・d[n] = e(i, i-1, d)+1
　0<キーi<mの場合、パターン数は全体がi個で、i-1個以下の長さのブロックからできているパターン数とi個ブロック1つだけ置くパターン数1の和です。
・ここまででパターン数辞書の初期状態が準備できたら、
　関数e(n, m, d)が求める値なので、これを求めて返します。

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

プロジェクトオイラー　問１１６（別解）

2015-10-11T20:24:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１１６「赤タイル, 緑タイル, あるいは青タイル」
5 個の黒い正方形のタイルの列を, 赤(長さ 2), 緑(長さ 3), 青(長さ 4)から選んで,この色のついた長方形のタイルでいくつか置き換える.

もし赤のタイルを選んだ場合は, ちょうど 7 通りの方法がある.

もし緑のタイルを選んだ場合は, 3 通りである.

もし青のタイルを選んだ場合は, 2 通りである.

複数の色を混ぜられない場合は, 5 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は 7 + 3 + 2 = 12 通りある.

50 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は何通りあるか.
ただし複数の色を混ぜることはできず, 少なくとも 1 個は色のついたタイルを使うこと.

注: この問題は Problem 117 に関連する

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

私の回答例は以下の通りです。

def e(m, n, d):
	if n not in d:
		d[n] = e(m, n-1, d)+e(m, n-m, d)
	return d[n]

def dd(n):
	d = {0:0, n:2}
	for i in xrange(1, n): d[i] = 1
	return d

def f(n, t):
	s = 0
	for m in t:
		d = dd(m)
		s += e(m, n, d) -1
	return s

n = 50
t = 2,3,4
s = f(n, t)
print s

前回の解法は、問１１４、１１５を参考に続けて考えたため、終端のブロックが1個かm個かによって関数end1()とendm()として関数を分けていましたが、1個ブロックもm個ブロックもその後にどちらを置いてもいいので本質的に違いはありません。
そこで、
関数end1()とendm()を統合して、終端のブロック数に関係しない関数e()として別解を作成しました。

１．関数e(m, n, d)
・全体がn個で、1個とm個のブロックからできているパターン数を返します。
・dは全体がn個の場合のパターン数の辞書（連想配列）です。
　1度計算した値はこの辞書に格納して重複して計算しないようにします。
・全体がn個になる場合のパターン数は、
　全体がn-1個の後に1個ブロックを1つ置く場合と
　全体がn-m個の後にm個ブロックを1つ置く場合の２系統あるので、この和になります。

２．関数dd(n)
・n個ブロックを使用する場合のパターン数辞書の初期状態を返します。
　1個ブロックとn個ブロックの両方があることを考慮します。
・具体的には以下のとおりです。
　キー=nの場合、1個ブロックn個連続またはm個ブロック1個の場合なのでパターン数は2、
　0<キー<nの場合、1ブロックが連続しているパターンだけなのでパターン数は1、
　キー=0の場合、パターン数は0となります。

３．関数f(n, t)
・全体のブロック数nのときの求めるパターン数を返します。
　ただし、引数tは1個ブロックとともに使用するm個ブロックのmに相当する数のタプルです。
　本問では赤(長さ 2), 緑(長さ 3), 青(長さ 4)を使用するので、t=2,3,4となります。
・ループ変数mとして引数tから値を１つずつ取り出します。
・パターン数辞書をdとして、関数dd()で初期化した状態で準備します。
・mの値ごとに関数e()でパターン数を求め、
　全部1個ブロックの場合は数えないのでそのパターン数1を引きます。
・上記を使用するm個ブロックの分だけ累積します。

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

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

2015-09-13T21:08:00.000+09:00

もし緑のタイルを選んだ場合は, 3 通りである.

もし青のタイルを選んだ場合は, 2 通りである.

def end1(m, n, d1, dm):
	if n not in d1:
		d1[n] = end1(m, n-1, d1, dm)+endm(m, n-1, d1, dm)
	return d1[n]

def endm(m, n, d1, dm):
	if n not in dm:
		dm[n] = end1(m, n-m, d1, dm)+endm(m, n-m, d1, dm)
	return dm[n]

def dd(n):
	d = {n:1}
	for i in xrange(n): d[i] = 0
	return d

def f(n, t):
	s = 0
	for m in t:
		d1, dm = dd(1), dd(m)
		s += end1(m, n, d1, dm) + endm(m, n, d1, dm) -1
	return s

n = 50
t = 2,3,4
s = f(n, t)
print s

問１１４、１１５との違いは以下です。
a.m個ブロックも1個ブロックと同様に連続してよい。
b.最低1つは色ブロックが必要。つまり、全部黒1個のパターンは数えない。
c.黒1個ブロックの他に3色あり、3色は混ぜられない。

そこで、問１１５で作成した、
全体がn個で終端が黒ブロックのパターン数の関数endb()と
同終端が赤ブロックの関数endr()に基づいて、それぞれ、
全体がn個で終端が1個ブロックのパターン数を関数end1()と
同終端がm個ブロックの関数endm()として調整します。

上記aの対応で、endm()は全体個数がn-m個のときのend1()とendm()の和になります。
上記bの対応で、f()では全部が1個ブロックの場合の1パターン分、減らします。
上記cの対応で、3色別々に計算し、合計します。

１．関数end1(m, n, d1, dm)
・全体がn個で、1個とm個のブロックからできていて末尾が1個ブロックのパターン数を返します。
・問１１５の関数endb()の変数名を変更しただけでまったく同じ関数です。
・d1は終端が1個ブロックで全体がn個の場合のパターン数の辞書（連想配列）です。
　dmは終端がm個ブロックで全体がn個の場合のパターン数の辞書（連想配列）です。
　いずれも1度計算した値はこれらの辞書に格納して重複して計算しないようにします。
・終端に1個ブロックを置いて全体がn個になる場合のパターン数は、
　全体がn-1個で終端が1個ブロック、m個ブロックのときのパターン数の和になります。

２．関数endm(m, n, d1, dm)
・全体がn個で、1個とm個のブロックからできていて末尾がm個ブロックのパターン数を返します。
・d1、dmは関数end1のときと同様です。
・終端にm個ブロックを置いて全体がn個になる場合のパターン数は、
　全体がn-m個で終端が1個ブロック、m個ブロックのときのパターン数の和になります。

３．関数dd(n)
・n個ブロックを使用する場合のパターン数辞書の初期状態を返します。
　具体的には、キー=nの値が1で、キー<nの値が0である辞書（連想配列）を返します。

４．関数f(n, t)
・全体のブロック数nのときの求めるパターン数を返します。
　ただし、引数tは1個ブロックとともに使用するm個ブロックのmに相当する数のタプルです。
　本問では赤(長さ 2), 緑(長さ 3), 青(長さ 4)を使用するので、t=2,3,4となります。
・ループ変数mとして引数tから値を１つずつ取り出します。
・d1、dmとして、終端が1個ブロックとm個ブロックのパターン数辞書を
　関数dd()で初期化した状態で準備します。
・mの値ごとに、終端が1個ブロックの場合と終端がm個ブロックの場合の、
　それぞれのパターン数を関数end1()、関数endm()で求めて合計し、
　全部1個ブロックの場合は数えないのでそのパターン数1を引きます。
・上記を使用するm個ブロックの分だけ累積します。

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

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

2015-08-23T14:17:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１１５「ブロックの組み合わせ方の数え上げその2」
注意: これは Problem 114 をより難しくした問題である.

長さ n ユニットからなる 1 列上に, 最低 m ユニットの長さを持つ赤ブロックが置かれている.
ただしどの赤ブロック同士も, 少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい).

敷き詰め計数関数 F(m, n) は 1 列に敷き詰める方法が何通りかを表すとする.
例えば, F(3, 29) = 673135 であり, F(3, 30) = 1089155 である.
m = 3 の時, n = 30 がこの敷き詰め計数関数が初めて 1,000,000 を超える最小の値であることがわかる.
同様に, m = 10 では F(10, 56) = 880711, F(10, 57) = 1148904 であることがわかり, つまり n = 57 がこの敷き詰め計数関数が初めて 1,000,000 を超える最小の値であることがわかる.
m = 50 のとき, この敷き詰め計数関数が初めて 1,000,000 を超える最小の n の値を求めよ.

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

私の回答例は以下の通りです。

def endb(m, n, bd, rd):
	if n not in bd:
		bd[n] = endb(m, n-1, bd, rd) + endr(m, n-1, bd, rd)
	return bd[n]

def endr(m, n, bd, rd):
	if n not in rd:
		rd[n] = 1 + sum([endb(m, i,bd,rd) for i in xrange(n-m+1)])
	return rd[n]

def f(m, k):
	bd = {0:0, 1:1}
	rd = {m:1}
	for i in xrange(m): rd[i] = 0

	n = 0
	while endb(m, n, bd, rd)+endr(m, n, bd, rd)<=k: n += 1
	return n


m=50
k = 1000000
n = f(m, k)
print n

問１１４との違いは、以下の２点です。
a.赤ブロックの最小個数が3個固定だったのがm個になったこと。
b.全体の長さを固定にしてパターン数を求めていたことに対して
　パターン数の下限値から全体の長さの最小値を求めること。

そこで、問１１４で作成した、
全体がn個で終端が黒ブロックのパターン数の関数endb()、
同赤ブロックの関数endr()を上記aに対応できるように改良し、
求める値を返すf()も上記bに合わせて改良します。

１．関数endb(m, n, bd, rd)
・赤ブロックが最小m個、全体がn個で終端が黒ブロックのパターン数を返します。
・問１１４の関数endb()に引数mを追加し、呼び出す関数endr()も問１１４のものに引数mを追加するので、それに合わせました。
・bdは終端が黒で全体がn個の場合のパターン数の辞書（連想配列）です。
　rdは終端が赤で全体がn個の場合のパターン数の辞書（連想配列）です。
　いずれも1度計算した値はこれらの辞書に格納して重複して計算しないようにします。
・終端に黒ブロックを置いて全体がn個になる場合、
　全体がn-1個で終端が赤でも黒でも置けるので、これらのパターン数の和になります。

２．関数endr(m, n, bd, rd)
・赤ブロックが最小m個、全体がn個で終端が赤ブロックのパターン数を返します。
・問１１４の関数endb()に引数mを追加し、固定値2の部分をm-1に改良しました。
・bd、rdは関数endbのときと同様です。
・終端に赤ブロックを置いて全体がn個になる場合は以下の２つの場合があります。
　a.まだ何も置いていなくて長さn個の赤ブロックを置く場合
　b.端が黒でn個まで2個以上のすきまがあり、すきまの長さ+1個の赤ブロックを置く場合
　　この場合、置く直前のブロックは黒ブロックの場合だけなのでendb関数を呼び出します。

　aの場合は1パターンなので赤辞書rdのキーnの初期値に1として設定します。
　bの場合はループ変数iを0からnのm個手前まで回して、長さiの黒ブロックで終わって長さn-iの赤ブロックを1つ置くパターン数を足します。

３．関数f(m, k)
・赤ブロックの最小個数mで問題の条件に合うパターン数が下限値k個を超える、全体の長さの最小値を返します。
・bd、rdは関数endbのときと同様です。
　最小の長さが、黒は1個で、赤はm個なので、黒赤それぞれでその値未満のパターン数は0で、その値で1パターンが初期値になります。
　なお、辞書rdには、キーmのとき1を固定で設定し、m未満のキーのときはfor文で回して0を設定します。
・黒赤それぞれのが終端となるパターン数の和が全パターン数です。
　全体の長さnは0から始めて1ずつ増加させながら全パターン数を計算していき、
　この全パターン数が下限値kを超えたら、そのときのnを返します。

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

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

2015-08-20T16:30:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１１４「ブロックの組み合わせ方の数え上げその1」
長さ 7 ユニットからなる 1 列上に, 最低 3 ユニットの長さを持つ赤ブロックが置かれている.
ただしどの赤ブロック同士も, 少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい).
これを敷き詰める方法は, ちょうど 17 通りある.

50 ユニットの長さの 1 列を敷き詰める方法は何通りあるか.

注意: 上の例では起こりえないが, 通常はブロックの大きさが複数混ざっていてもよい.
例えば, 8 ユニットの長さの 1 列では, 赤(3), 黒(1), 赤(4) を使うことができる.

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

私の回答例は以下の通りです。

def endb(n, bd, rd):
	if n not in bd:
		bd[n] = endb(n-1, bd, rd) + endr(n-1, bd, rd)
	return bd[n]

def endr(n, bd, rd):
	if n not in rd:
		rd[n] = 1 + sum([endb(i,bd,rd) for i in xrange(n-2)])
	return rd[n]

def f(n):
	bd, rd = {0:0, 1:1}, {0:0, 1:0, 2:0, 3:1}
	return endb(n, bd, rd) + endr(n, bd, rd)

n=50
s = f(n)
print s

黒ブロック（長さ１個）または赤ブロック（長さ３個以上）を１つずつ置いていって個数を数えます。
ただし、赤ブロックは連続では置けないので、
順番に並べていく中で終端が赤か黒かで別々の関数にします。

１．関数endb(n, bd, rd)
・全体がn個で終端が黒ブロックのパターン数を返します。
・bdは終端が黒で全体がn個の場合のパターン数の辞書（連想配列）です。
　rdは終端が赤で全体がn個の場合のパターン数の辞書（連想配列）です。
　いずれも1度計算した値はこれらの辞書に格納して重複して計算しないようにします。
・終端に黒ブロックを置いて全体がn個になる場合、
　全体がn-1個で終端が赤でも黒でも置けるので、これらのパターン数の和になります。

２．関数endr(n, bd, rd)
・全体がn個で終端が黒ブロックのパターン数を返します。
・bd、rdは関数endbのときと同様です。
・終端に赤ブロックを置いて全体がn個になる場合は以下の２つの場合があります。
　a.まだ何も置いていなくて長さn個の赤ブロックを置く場合
　b.端が黒でn個まで2個以上のすきまがあり、すきまの長さ+1個の赤ブロックを置く場合
　　この場合、置く直前のブロックは黒ブロックの場合だけなのでendb関数を呼び出します。

　aの場合は1パターンなので赤辞書rdのキーnの初期値に1として設定します。
　bの場合はループ変数iを0からnの3つ手前まで回して、長さiの黒ブロックで終わって長さn-iの赤ブロックを1つ置くパターン数を足します。

３．関数f(n)
・問題の条件で長さnで1列を敷き詰めるパターン数を返します。
・bd、rdは関数endbのときと同様です。
　最小の長さは黒が1個で赤が3個なので、黒赤それぞれでこの値未満のパターン数は0で、その値で1パターンというのが初期値になります。
・黒赤それぞれのが終端となるパターン数の和が、求めるパターン数です。

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

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

2015-08-17T09:21:00.001+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１１３「非はずみ数」
ある数の桁を左から右へと順に見たとき, 任意の桁の数が自身の左にある桁の数以上であるとき, その数を増加数 (increasing number) と呼ぶ; 例えば134468は増加数である.
同様に, 任意の桁の数が自身の右にある桁の数以上であるとき, その数を減少数 (decreasing number) と呼ぶ; 例えば66420がそうである.
増加数でも減少数でもない数を "はずみ"数 ("bouncy" number) と呼ぶ; 155349がそうである.
nが大きくなるにつれ, n以下のはずみ数の割合は大きくなる. 例えば, 100万未満では, はずみ数でない数は12951個しかない. 同様に, 10¹⁰未満では277032個しかない.
googol数 (10¹⁰⁰) 未満ではずみ数でないものの数を答えよ.

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

私の回答例は以下の通りです。

def g(n):
	if n<2: return 1
	else: return n*g(n-1)

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

def H(n, m): return C(n+m-1, m)

def f(n):
	c = H(10, n)-H(10, 0)
	for i in xrange(1, n+1): c += H(10,i)
	c -= 10*n
	return c

n=100
s = f(n)
print s

与えられた数が大きすぎるので桁数ごとに個数を計算して合計することにします。

まず増加数です。
これは0から9までの数字10種類からi個を選ぶ重複組合せです。
重複組合せの個数は公式から以下の通りです。
　₁₀H_i ...(A)

図にすると、i桁の数字が以下のように表せます。「｜」は仕切り棒です。
連続する0｜連続する1|・・・｜連続する9
つまり、i個の要素を連続する0から連続する9までの10個の部分に分けることと同じです。
重複組合せでは、仕切り棒の本数も含めた格納場所に仕切り棒を入れることを考えます
10個の部分に分けるので必要な仕切り棒は10-1で9本必要です。
つまり、i+9個の格納場所に9本の仕切り棒を格納し、仕切り棒の間には連続する数字を格納することと同じです。
なお仕切り棒が隣合う場合、その間の連続する数字は１つも無いことになります。
重複組合せの個数の式と、重複を許さない組合せの個数の式との関係は以下の通りです。
　_nH_m = _n+m-1C_m ...(B)
m-1は、仕切り棒の本数です。

それから、最上位が0の場合、桁数がiではなくなってしまいますが、
その個数は最上位1桁だけ0固定で他のi-1桁分は重複組合せなので、
　₁₀H_i-1
この分を差し引くと
　₁₀H_i - ₁₀H_i-1
これを全桁分、つまり桁数iを1からnまで動かして和をとると、
ほとんどの項が打ち消しあって以下だけが残ります。
　₁₀H_n - ₁₀H₀ ...(C)

次に減少数です。
減少数と同じように図にすると、i桁の数字が以下のように表せます。
連続する9｜連続する8|・・・｜連続する0
この重複組合せの個数は上記(A)と同じです。

さらに、増加数と減少数で重複して数えている分を差し引きます。
増加数でも減少数でもカウントしている値は、全桁同じ数字の場合なので、
各桁数ごとに10個あり、n桁以下の範囲では、
10*n ...(D)
です。

１．g(n)
・階乗n!を返します。
・問２０のものを流用しました。

２．関数C(n, m)
・n個の中からm個を選ぶ組合せの個数を返します。
・公式から、n!/（m!・(n-m)!）　です。

３．関数H(n, m)
・n個の中からm個を選ぶ重複組合せの個数を返します。
・上記(B)をそのまま実装しました。

４．関数f(n)
・10ⁿ未満、つまりn桁以下で、はずみ数以外の数の個数を返します。

・c = H(10, n)-H(10, 0)
　増加数の個数です。上記(C)をそのまま実装しました。

・for i in xrange(1, n+1): c += H(10,i)
　減少数の個数です。
　n桁の減少数である上記(A)をそのまま実装し、1桁からn桁の分の和を計算しました。

・c -= 10*n
　増加数と減少数の重複分を差し引きます。
　上記(D)をそのまま実装しました。

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

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

2015-07-05T14:40:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１１２「はずみ数」
左から右までどの桁もその左の桁を下回らない数を増加数と呼ぶ. 例えば, 134468.
同様に, どの桁もその右の桁を下回らない数を減少数と呼ぶ. 例えば, 66420.
増加数でも減少数でもない正の整数をはずみ数と呼ぶことにする. 例えば, 155349.

100以下にはずみ数が無いのは明らかだが, 1000未満では半数を少し上回る525個がはずみ数である.
実際, はずみ数の割合が50%に達する最少の数は538である.
驚くべきことに, はずみ数はますます一般的になり, 21780でははずみ数の割合は90%に達する.
はずみ数の割合がちょうど99%になる最小の数を求めよ.

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

私の回答例は以下の通りです。

def f(n):
	i, b, c, r = 0, 0.0, 0.0, n/100.0
	while True:
		i += 1
		s = str(i)
		t = "".join([j for j in sorted(s)])
		u = "".join([j for j in sorted(s, reverse=True)])
		if t<s<u: b += 1
		else: c += 1
		if r<=b/(b+c): break

	return i

n=99
s = f(n)
print s

小さい数から順に各桁を昇順降順にソートした値と比較することではずみ数か判定し、件数カウントしその割合を計算しました。

１．関数f(n)
・はずみ数の割合がちょうどn％になる最小の数を返します。
・変数iは候補値、変数bははずみ数の個数、変数cははずみ数以外の個数、変数rは割合です。
・変数sで候補値を文字列にします。
ループ変数jでひと桁ずつ取り出し、sorted関数で昇順にして再度連結した値を変数tとし、sorted関数のreverse引数をTrueにすることで降順にして再度連結した値を変数uとします。
・変数tとuはそれぞれ増加数と減少数なので、変数sがこれらの間の値であれば、はずみ数と判定します。

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

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

2015-06-21T15:54:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１１１「重複桁を持つ素数」
重複した桁を含む 4 桁の素数を考える.

全てが同じにならないのは明らかである:
1111 は 11 で割り切れ, 2222 は 22 で割り切れ, 以下同様だからである.

しかし 3 個の 1 を含む 4 桁の素数は 9 つある:
1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111

n 桁の素数に対する重複した桁の最大個数を M(n, d) と表すことにしよう.
ここで d は重複した桁とする.
またそのような素数の個数を N(n, d) と表し, これらの素数の和を S(n, d) と表す.
よって M(4, 1) = 3 は, 重複した桁を 1 としたときの,
4 桁の素数に対する重複した桁の最大個数である.
そのような素数は N(4, 1) = 9 個あり, これらの素数の和は S(4, 1) = 22275 である.
d = 0 に対しては, 重複した桁は M(4, 0) = 2 個だけ可能であることが分かるが,そのような場合は N(4, 0) = 13 個ある.

同じようにして 4 桁の素数に対して次の結果を得る.

Digit, d	M(4, d)	N(4, d)	S(4, d)
0	2	13	67061
1	3	9	22275
2	3	1	2221
3	3	12	46214
4	3	2	8888
5	3	1	5557
6	3	1	6661
7	3	9	57863
8	3	1	8887
9	3	7	48073

d = 0 から 9 に対して, S(4, d) の総和は 273700 である.

S(10, d) の総和を求めよ.

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

私の回答例は以下の通りです。

def h(n):
	import itertools
	if n==2: return True
	if n<2 or (not n%2): return 0
	for i in itertools.islice(itertools.count(3, 2), None):
		if i*i>n: break
		if not n%i: return 0
	return n

def g(M, w):
	L = []
	for s in M:
		if s[0]=="0":
			for t in w:
				L.append(t+s)
		else:
			for i in xrange(len(s)+1):
				for t in w:
					if i==0 and t=="0": continue
					L.append(s[:i]+t+s[i:])
				
	return L

def f(n):
	SS = 0
	for d in xrange(10):
		w = [str(i) for i in xrange(10) if i!=d]
		S, M = 0, n
		while S==0:
			M -= 1
			L = [str(d)*M]
			for i in xrange(n-M): L = g(L, w)
			L = set(L)
			for t in L: S += h(int("".join(t)))
			
		SS += S
		
	return SS

n=10
s = f(n)
print s

素数を発生させて重複桁があるかチェックする方式でやってみたところ、チェック以前に10桁分の素数の発生がとても1分で終わらないことが判明しました。
そこで、やり方を逆にして、まず重複桁の値を決め、その他の値を重複桁の間や両側に付加して候補値を作り、素数チェックをするようにしました。

１．関数h(n)
・素数ならｎ、素数以外なら0を返します。
・問５８の素数判定関数を改良しました。

・forループではxrange関数で数値を発生させていましたが、
10桁の整数の途中からオーバーフローになるので
itertoolsモジュールのislice関数を使うように改良しました。

２．関数g(M, w)
・リストMの全要素の両端や文字間に、リストwから取り出した１文字を付加した値を作りリストにまとめて返します。
但し、後で数値化したときに桁数が減ってしまうことを避けるために、
リストMの各要素の先頭が0の場合は左端にだけ付加し、
付加する文字が0の場合は左端以外にだけ付加します。

３．関数f(n)
・n桁の素数について問題文のSの合計を返します。
・ループ変数dは重複する桁の値で、0から9の値をとります。
・リストwは重複しない桁の値で、0から9のうち、dと異なる値を持ちます。
・変数Sは、dが重複するn桁の素数の和です。
・変数Mは、重複する桁dの個数です。
・while文では変数Mを１つずつ減らしながらSを計算し0以外になれば終了します。
・変数iは、全体n桁のうちd以外の値の個数です。
・リストLは、関数gでd以外の値をi個付加した候補値のリストです。
リストLの要素を１つずつ取り出し、連結して数値化し、関数hで素数判定します。
素数ならば、変数Sに累積していきます。
・whileループを抜けたら、SをSSに累積して、次のdでの処理に続きます。

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

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

2015-05-23T14:12:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１１０「ディオファントス逆数その2」
次の等式で x, y, n は正の整数である.

1/x + 1/y = 1/n

n = 1260 では 113 の異なる解があり, この n が解の個数が 100 を超える最小の値である.

解の数が 4,000,000 を超える最小の n を求めよ.

注: この問題は Problem 108 を非常に難しくしたケースである. 総当り法で解ける範囲を超えているので, 賢い解き方が求められる.

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

私の回答例は以下の通りです。

def P(n):
	L, i = [], 1
	if n>0:
		L.append(2)
		while len(L)<n:
			i += 2
			for j in L:
				if not i%j: break
			else:
				L.append(i)
	return L

def mul(L): return reduce(lambda x,y:x*y, L)

def f(m):
	import math
	tmax = int(math.log(m*2, 3))
	p = P(tmax+1)
	nb, kb, Lb, L = 0, 0, [], []
	while len(L)<=tmax:
		L = [1]*(len(L)+1)
		M = [i*2+1 for i in L]
		k = (mul(M)+1)//2
		while k<=m:
			for i in xrange(len(L)):
				if tmax<=1 or (i<len(L)-1 and L[i]==L[i+1]):
					L[i] += 1
					for j in xrange(i):
						if L[j]>L[i]: L[j] = L[i]
					break
			else:
				L = [1]*(len(L)+1)

			M = [i*2+1 for i in L]
			k = (mul(M)+1)//2

		N = [p[i]**j for i,j in enumerate(L)]
		n = mul(N)
		if nb==0 or n<=nb: nb, kb, Lb = n, k, L
	return nb, kb, Lb

m=4000000
n, k, L = f(m)
print "n :", n
print "k :", k
print "L :", L

問１０８ではnを１つずつ増やしながら解の個数kを求めてkが閾値を超えたら終了というロジックで解きましたが、解の個数kが巨大な数になると、素因数分解の処理が重くて処理が終わりません。

まず、問１０８からわかっていることは以下のとおりです。
・解の個数kは、n²を２つの約数の積で表したパターンの個数に等しい。

・n²の約数の個数iについて、n²を素因数分解した結果に含まれる各素因数に対して、採用0個の場合も含めたパターン数は各要素数+1であり、これを全素因数の分だけ掛け合わせた積が、約数の個数iということになります。
　例：72の約数の個数は、72=2³＋3², べき乗の値から、(3+1)x(2+1)=12

・n²の約数の個数iとして、２つの約数の積でn²になる組合せの個数kとして、
　k = (i+1)//2 （小数以下切捨て）です。

上記からnと解の個数kの関係を、例にあるn=1260, k=113の場合を手で計算してみると以下の通りです。

n = 1260
↑積　　↓因数分解
素数とべきリスト値の累乗リストN = [2², 3², 5¹, 7¹] = [4, 9, 5, 7]
↑小さい順の素数にべきリストLの値で累乗
べきリストL = [2, 2, 1, 1]
↓各要素の２乗
べき２乗リスト = [4, 4, 2, 2]
↓各要素に+1する
約数の個数リストM = [5, 5, 3, 3]
↓各要素の積
約数の個数 = 5*5*3*3 = 225
↓
解の個数k = (225+1)//2 = 113

問108ではnから出発して１つずつ因数分解をしていましたが、
一見して明らかに一番取り扱い易そうなのは、上記のべきリストLです。
べきリストLを調整しつつ、kを算出してしきい値判定して、nを特定する方法でいきます。

しきい値mとして、m<kである最小のnを求めるので、
m<kを満たすkが特定されたときにnが最小であるためには、
べきリストLは、左の要素≧右の要素 ...(a)

べきリストLの要素数をtに固定すると、
nが最小になるのは、全要素が1のとき。例　[1,1, ... ,1]　1がt個ある。
べきリストLの要素数tの最大値tmaxは、全要素が1でm=kのときのtの値です。
このとき約数の個数リストMは1*2+1=3だけがtmax個ある状態で、
解の個数k = (3^tmax)//2 = m（しきい値）となります。
3^tmax = m*2
両辺の対数をとって、
tmax * log3 =log(m*2)
tmax = log(m*2)/log3 = log₃(m*2) （小数以下切捨て）...(b)

１．関数P(n)
・小さい方からn個の素数リストを返します。
・Problem108で作成した関数を流用します。詳しくはProblem108を参照。

２．関数mul(L)
・リストLの全要素の積を返します。
・reduce文で、第１引数の関数f、第２引数にリストLを設定しています。
・関数fは「lambda x,y:x*y」です。
　無名関数lambdaを使って、引数１と引数２の積を計算します。
・reduce文では関数fの第２引数にリストLの要素を順に渡し、
　関数fの第１引数に関数処理結果を設定します。
　このため、関数fでfの第１引数と第２引数を元に計算することで、累積的な処理が記述できます。
　reduce文は、累積的は処理を短く記述できますが、少しややこしい構文です。

３．関数f(m)
・1/x + 1/y = 1/n（x,y,nは正の整数）となる解の個数kが引数mを超える最小値を求め、n、k、べきリストLを返します。
・べきリストLの要素数の最大値tmaxは、上記(b)をそのまま実装します。
・素数リストpは、関数Pでtmax個の素数を準備します。

・外側のwhileループでは、べきリストの要素数がtmax以下の場合にべきリストを調整して解の候補を探します。
・べきリストLの初期値は全要素1で要素数をループの都度１つずつ増やします。

・内側のwhileループでは、解の個数kがそのしきい値m以下の場合にべきリストを調整して解の候補を探します。

・現在のべきリストに基づいて次のべきリストを調整します。
・iのforループで、べきリストの要素を右から順に見ていきます。
　まず、べきリストの最大要素数が1以下、または「右隣と同じ値」である最初の要素を+1します。
　例：[1] → [2]
　例：[4, 3, 2, 2, 1, 1] → [4, 3, 3, 2, 1, 1]
　さらに、+1した要素の左側は、L[i]にクリアします。
　例：[4, 3, 3, 2, 1, 1] → [3, 3, 3, 2, 1, 1]
　-1する前のリストは当ループが進めばまた出てきます。
　
・forループが最後まで終了したら、べきリストLの要素数を１つ増やして全要素1にクリアします。
　for文のelse句は、for文のループがbreakで途中で抜けずに最後まで終了した直後に実行する処理を記述します。
　例：[3, 2, 1] → [1, 1, 1, 1]

・このようにしてべきリストLを作成したら、チェックします。
　約数の個数リストM、解の個数kを計算します。

・解の個数kがしきい値を超えて内側のwhileループが終了したら、素数とべきリスト値の累乗リストN、そして求める値nを計算し、バックアップしてある値と比較して、最小のnの場合にバックアップするようにします。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
n : 9350130049860600
k : 4018613
L : [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1]

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

2015-05-03T17:14:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１０９「ダーツ」
ダーツゲームでは, プレイヤーは 20 等分に分けられたダーツボードに 3 本のダーツを投げる.
ダーツボードは 1 から 20 の番号がふられている.

ダーツの点数は, ダーツが刺さった領域の番号によって決まる.
外側の赤緑の輪の外に刺さったダーツは 0 点である.
この輪の内側の黒と白の領域はシングル (1 倍) の点数を表している.
しかし, 外側と内側の赤緑の輪はそれぞれダブル (2 倍) とトリプル (3 倍) の点数である.

ボードの中央の 2 つの同心円はブルやブルズアイと呼ばれる.
外側のブルは 25 点, 内側のブルはダブルの 50 点である.

ルールには多くのバリエーションがあるが, 最もポピュラーなゲームでは,
プレイヤーは 301 または 501 点から始まり, 最も早く現在の得点を 0 点に減らしたプレイヤーが勝者となる.
しかし, 普通は「ダブルアウト」方式でプレイをする.
この方式では, プレイヤーは勝利するために,
最後のダーツをダブル (ボードの中央のダブルのブルズアイを含む) に刺さなければならない.
それ以外で現在の得点を 1 点以下に減らした場合,
3 本のダーツに対する得点は「バースト(無効)」になる.

プレイヤーが現在の得点で終了できる場合を「チェックアウト」と呼ぶ.
最も高いチェックアウトは 170: T20 T20 D25 (トリプルの 20 を 2 回とダブルのブル) である.

得点が 6 でチェックアウトする異なるやり方はちょうど 11 通りある.

D3
D1 D2
S2 D2
D2 D1
S4 D1
S1 S1 D2
S1 T1 D1
S1 S3 D1
D1 D1 D1
D1 S2 D1
S2 S2 D1

D1 D2 と D2 D1 は, 異なるダブルで終了しているので異なるとみなすことに注意しよう.
しかし S1 T1 D1 の組み合わせは T1 S1 D1 と同じとみなす.

さらに, 組み合わせを考える上でミスは含まないこととする;
たとえば, D3 は 0 D3 や 0 0 D3 と同じである.

信じられないことに, 異なるチェックアウトは全部で 42336 通りある.
得点が 100 未満の異なるチェックアウトは何通りあるか.

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

私の回答例は以下の通りです。

def f(n):
	Ls = [i+1 for i in xrange(20)]+[25]
	Ld = [(i+1)*2 for i in xrange(20)]+[50]
	Lt = [(i+1)*3 for i in xrange(20)]
	La = Ls+Ld+Lt
	c = 0

	for i in Ld:
		if i<n: c += 1

	for i in La:
		for j in Ld:
			if i+j<n: c += 1

	for m, i in enumerate(La):
		for j in La[m:]:
			for k in Ld:
				if i+j+k<n: c += 1

	return c

n=100
c = f(n)
print c

何投目で終了するかの別に分けてカウントします。

１．関数f(n)
・n点未満でチェックアウトするときの、場合の数を返します。
・リストLsはシングルの得点リストです。要素は1から20までの整数と25です。
・リストLdはダブルの得点リストです。要素は1から20までの偶数と50です。
・リストLtはトリプルの得点リストです。要素は1から20までの3の倍数です。
・リストLaは全面の得点リストです。
　シングル、ダブル、トリプルのリストを単純に結合したものです。

・１投終了の場合、ダブルのリストLdです。
　この中から得点合計がn未満の場合をカウントします。

・２投終了の場合、１投目は前面リストLa、２投目はダブルのリストLdです。
　二重ループで状況を再現し、得点合計がn未満の場合をカウントします。

・３投終了の場合、
　１投目は前面リストLa、
　２投目は前面リストLaのうち１投目としてカウントしてないもの、
　つまり、リストLaから１投目で採用した位置よりも後の位置で採用します。
　３投目はダブルのリストLdです。
　三重ループで状況を再現し、得点合計がn未満の場合をカウントします。

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

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

2015-04-04T18:55:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１０８「ディオファントス逆数その1」
次の等式で x, y, n は正の整数である.

1/x + 1/y = 1/n

n = 4 では 3 つの異なる解がある.
1/5 + 1/20 = 1/4
1/6 + 1/12 = 1/4
1/8 + 1/8 = 1/4

解の数が 1000 を超える最小の n を求めよ.

注: この問題は Problem 110 の易しいケースである. こちらを先に解く事を強く勧める.

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

私の回答例は以下の通りです。

def P(n):
	L, i = [], 1
	if n>0:
		L.append(2)
		while len(L)<n:
			i += 2
			for j in L:
				if not i%j: break
			else:
				L.append(i)
	return L

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(m):
	import math
	i = int(math.log(2*m-1, 2))
	n, k, p = 1, 1, P(i)
	while k<=m:
		n += 1
		d = g(n*n, p)
		i = 1
		for j in d.values(): i *= j+1
		k = (i+1)//2
	return n, k

m=1000
n, k = f(m)
print "n :", n
print "k :", k

問題の式を変形してみます。
1/x + 1/y = 1/n
両辺にnxyを掛けて
ny + nx = xy
xy - nx - ny = 0 ...a

式aを２つの数の積で表して差分調整することにします。
xy, nx, nyを展開式の項として持つ式で最も簡単な式は以下の通り。
(x-n)(y-n) = xy - nx - ny + n² ...b

式bに式aを代入して、
(x-n)(y-n) = n² ...c

n²を２つの正の整数の積で表し、それぞれ+nすればxとyになります。
つまり、当問題でチェックすべき「解の数」は、
n²を２つの約数の積で表したパターンの個数です。

また、２つの約数の積が元の数になる組合せは、
約数を順に並べて小さい方からと大きい方からそれぞれ１つずつ採用し、
中央値がある場合は中央値を２つ採用した組合せです。
なので、n²の約数の個数i、該当する約数の組合せの個数kとして、以下の通りです。
k = (i+1)/2 （小数点以下切捨て）...d

また、約数の個数iは素因数分解した素因数ごとの採用パターン数の積です。
n²を素因数分解した結果の素因数ごとの要素数jとして、
その採用0個の場合も含めたパターン数j+1について、
全ての素因数の分の積を計算します。
この約数の個数iから、約数ペアの個数kを求め、指定値mを超えるまで処理を繰り返します。

また、素因数分解にあたり素数をいくつまで用意したらいいか検討します。
素因数分解で使用する素数の個数の上限値tについて、
この分だけ最小素数2を累乗しても約数の個数i以上となるので、
2^t ≧ i
両辺の対数を取って、
tlog2 ≧ log(i)
t ≧ log(i)/log2 = log₂i
式dを代入して、
t ≧ log₂(2k-1)
t = log₂(2k-1) （小数点以下切り捨て）...e

素因数分解の準備として、素因数分解で使用する素数の個数の上限値tの分だけ素数を用意しておきます。

１．関数P(n)
・小さい方からn個の素数リストを返します。
・リストLは素数リスト、変数iは素数候補です。
・リストLに最初の素数2を設定します。
・3以上の奇数を素数候補として、リストLにある素数で順に割り算します。
　割り算の余りが無い時点で素数候補iは素数ではないので、
　forループをbreakして次の素数候補へ処理がすすみ、
　リストLのすべての素数で割り算の余りがあれば、forループが最後まで回るのでelse句へ進んで素数リストLに素数候補iを追加します。
・上記を指定した素数の個数になるまで続けます。

２．関数g(n, P)
・Problem47で作成した関数を流用します。詳しくはProblem47を参照。
・引数nを素数リストPを使って素因数分解し、
　素数をキー、キーごとの分解した個数を値とする辞書（連想配列）を返します。

３．関数f(m)
・1/x + 1/y = 1/n（x,y,nは正の整数）となる解の個数kがmを超える最小値を求め、nとkを返します。
・対数関数を使う準備としてmathモジュールをインポートし式eを実装します。
　math.log関数の引数は、真数、底の順に設定します。
　変数nは問題文の右辺1/nのn、変数kはチェック対象の解の個数です。
・whileループで、解の個数kが指定値mを超えるまで処理を繰り返します。
・変数dは関数gによるn²に対して素数リストpを使用して因数分解した結果の辞書（連想配列）です。
・ループ関数jで因数分解辞書dから、素因数の値に関係なく、素因数ごとの要素数を設定します。
　変数iに、該当する素因数の個数j個に0個採用のケースも含めたj+1を掛けてためます。
・変数kとして、式dを実装します。//関数は割り算の商（整数値）です。

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

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

2015-03-01T20:53:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１０７「最短ネットワーク」
以下の無向ネットワークは7つの頂点と重み付きの12個の辺からなり, 重みの総和は243である.

このネットワークを以下の行列で表現することができる.

	A	B	C	D	E	F	G
A	-	16	12	21	-	-	-
B	16	-	-	17	20	-	-
C	12	-	-	28	-	31	-
D	21	17	28	-	18	19	23
E	-	20	-	18	-	-	11
F	-	-	31	19	-	-	27
G	-	-	-	23	11	27	-

しかし, このネットワークを, 全ての頂点が連結であるように適当な辺を除いた上で最適化することが出来る. 節約される量が最大化されるように取り除いたネットワークが以下の画像である. この場合, 辺の重みの総和は93であり, 元のネットワークからの節約量は 243 - 93 = 150 である.

6Kバイトのテキストファイル network.txt (右クリックして保存すること) には40頂点のネットワークを行列表示したものが記されている. ネットワーク全体が連結であるが冗長な辺を取り除いたときの節約量を最大にするようにした場合の節約量を答えよ.

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

私の回答例は以下の通りです。

def f(sIn):
	pIn = open(sIn)
	L0 = pIn.read().replace("\n", ",").split(",")
	pIn.close()
	pIn = None
	n = int(len(L0)**.5)
	L1, a = [], 0
	for i, w in enumerate(L0):
		if not w.isdigit(): continue
		w, (y, x) = int(w), divmod(i, n)
		if x<y:
			L1.append((w, (x, y)))
			a += w

	c, V, E = 0, [i for i in xrange(n)], []
	for w, (v1, v2) in sorted(L1):
		if V[v1]!=V[v2]:
			c += w
			E.append(((v1, v2),w))
			minv, maxv = min(V[v1], V[v2]), max(V[v1], V[v2])
			for i,s in enumerate(V):
				if s==maxv: V[i] = minv
			if not sum(V): break
	return a-c, a, c, E

s = "p107_network.csv"
sIn = os.path.join(os.path.dirname(__file__), s)
s, a, c, E = f(sIn)
print "saving:", s
print "all :", a
print "cut :", c
print "edge:", E

　問題文では「冗長な辺を取り除いて」とありますが、重い辺を順に除外していくと、重い辺の代わりに軽い辺を複数除外する方が全体として軽くなる場合に、重い辺の除外を解除しなくてはいけなくなり、ロジックが複雑になります。
そこで、軽い辺を順に採用していくことにします。
ただし、辺を１つ採用するごとに新しくつながる頂点または頂点群が増えることが条件です。
これを全頂点を網羅するまで続けます。

　頂点または頂点群が増えるかどうかの判定は、各頂点ごとにつながっている最小頂点番号で判定します。
最初は自分だけなので、各頂点とも最小頂点番号に自分自身の頂点番号を設定します。
　そして、重みの軽い辺から順にその両端点の最小頂点番号が異なる場合に採用し、両端点の最小頂点番号も洗い直しておきます。
すべての頂点の最小頂点番号が0になれば終了です。
最大頂点番号でも同様のことが可能ですが、終了判定がわかりやすいので最小頂点番号を使用します。

また、辺には向きが無いので、頂点番号の小さい方から大きい方への辺のみ使用します。

１．関数f(sIn)
ネットワーク情報のcsvファイルを入力し、
重みの節約数、重みの合計、カット後の重み合計、採用する辺のリストを返します。

・L0は:入力ファイルのcsv区切りのリストです。
　改行文字と半角カンマで区切ってリストにします。
・変数nは頂点数です。
　リストL0は各頂点を行列表示しているので、頂点数nはリストL0の平方根になります。
・リストL1は辺のリストです。
　(重み、（頂点番号１、頂点番号２）)のタプルをためます。
　ただし、重みは数値で、頂点番号１＜頂点番号２の場合に限ります。
・aは重みの総合計です。
・wは重み、xは列番号、yは行番号です。
　リストL0は行列表示を一次配列にしているので、
　その通し番号iを頂点数nで割った商が行番号y、余りが列番号xになります。
　divmod関数で商と余りを一度に求めています。

・リストVは最小頂点番号のリストです。
　V[i]は頂点iがつながっている最小頂点番号です。
　初期値は各頂点の自分自身の頂点番号です。
・リストEは採用した辺のリストです。
・辺のリストL1をソートして１つずつ処理します。
　ソートキーは未指定の場合は最初の要素なので、この場合、重みに軽い順になります。
・v1、v2は辺の両端の頂点番号です。
　このそれぞれのつながっている最小頂点番号が異なる場合、
　まだつながっていない頂点または頂点群なので、辺を採用します。
・minv, maxvは、採用した辺の両端点がそれぞれつながっている最小頂点番号の
　小さい方と大きい方です。
　最小頂点番号リストVで、値がこの小さい方の場合、大きい方の値に洗いなおします。
・最後に、最小頂点番号リストVの全要素の和をチェックし、この和が0ならば全頂点から0番目の頂点につながったということになるので処理終了です。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
saving: 259679
all : 261832
cut : 2153
edge: [((21, 36), 1), ((27, 34), 6), ((10, 33), 7), ((28, 34), 9), ((13, 39), 17), ((4, 35), 19), ((9, 29), 25), ((5, 25), 27), ((20, 28), 27), ((3, 9), 32), ((5, 34), 33), ((7, 9), 35), ((8, 15), 36), ((9, 13), 36), ((29, 37), 36), ((11, 17), 41), ((6, 10), 42), ((2, 9), 47), ((28, 37), 48), ((9, 10), 50), ((8, 24), 53), ((10, 19), 53), ((5, 36), 54), ((0, 31), 56), ((5, 23), 66), ((12, 29), 68), ((15, 31), 68), ((16, 18), 73), ((3, 38), 76), ((20, 30), 80), ((22, 28), 83),((14, 26), 89), ((35, 36), 91), ((1, 37), 102), ((26, 32), 102), ((11, 21), 104), ((2, 26), 108), ((1, 16), 122), ((0, 18), 131)]

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

2015-02-01T08:56:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１０６「特殊和集合:メタ検査」
大きさ n の集合 A の要素の和を S(A) で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば, A を特殊和集合と呼ぼう.

i. S(B)≠S(C); つまり, 部分集合の和が等しくてはならない.
ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.

本問題に対しては, 与えられた集合は n 個の単調増加する要素を含み, かつ第二のルールをすでに満たしているものと仮定しよう.

驚くべきことに, n = 4 の集合から得ることができる 25 個の可能な部分集合の対のうち,
1 個の対のみが同一性（第一のルール）をテストされる必要がある.
同様に, n = 7 のときは, 966 個の部分集合の対のうち 70 個のみがテストされる必要がある.

n = 12 に対して, 得られる 261625 個の部分集合の対のうち, 同一性をテストされる必要があるものは何個か.

注意: この問題は Problem 103 と 105 に関連している.！！！

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

私の回答例は以下の通りです。

def f(n):
	import itertools
	c = 0
	for i in xrange(2, n//2+1):
		L = [t for t in itertools.combinations(xrange(n), i)]
		for j, t0 in enumerate(L):
			for t1 in L[:j]:
				for s in t1:
					if s in t0: break
				else:
					for s,t in zip(t0, t1):
						if s<t: c += 1; break
	return c

n = 12
print f(n)

問題文にあるとおり、問１０３の関連問題です。
まず、与えられた集合はn個の単調増加する要素を含むことが前提なので、要素が２つ以上の部分集合が対象です。
また、ルールiiを満たしていることが前提なので、要素数が同じ部分集合同士が対象外です。
以上から、ルールiをチェックする部分集合ペアとして、以下の条件のものの件数を数えます。
・要素数が同じ
・同じ要素を持たない
・同じ項番の値でその大小が混在すること

なお、総当りで試しているので１分ルールに合うのはn=14までです。
当問題はn=12なのでこの方法でよしとします。

１．関数f(n)
・問題にある、同一性をテストされる必要がある部分集合の個数を返します。
　引数nは特殊和集合の要素数です。
・変数cは求める部分集合数です。
・ループ変数iは、比較する部分集合の要素数です。
　要素数が2個からnの半分までです。半分を超えると必ず同じ要素が含まれてしまいます。
・リストLは、0からn-1までのn個の値からi個選ぶ組合せのタプル群です。
・t0,t1が比較する部分集合の候補同士です。どちらもリストLの要素です。
　重複の無駄を避けるため、enumerate関数で0からの連番を発行し、リストL内の組合せ順でt0よりも先に作成される部分集合からt1として取り出します。

・同じ要素がないことの確認方法は以下の通りです。
　部分集合t1から要素を変数sとして順に取り出し、
変数sが１つでも部分集合t0に存在すれば、ループを終了し次のペアの処理へ進みます。
変数sのすべてで部分集合t0に存在しなければ、else句へ進み次のチェックをします。

・同じ項番の値で大小が混在することの確認方法は以下の通りです。
　zip関数でt0とt1の同じ位置の値をそれぞれs, tとして設定します。
　このときt1の方がt0よりも、組合せ順で先に作成されるので、部分集合t0の要素sよりも部分集合t1の要素tの方が小さい値を持つはずで、これと逆にs<tとなるtが１つでもあれば大小混在となり、チェック対象の部分集合数のカウンタcを１つアップして比較操作を抜けます。
　すべてのs,tで大小混在が検出できなければ、次の比較ペアへ処理を進めます。

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

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

2015-01-18T15:33:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１０５「特殊和集合:検査」
大きさ n の集合 A の要素の和を S(A) で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば, A を特殊和集合と呼ぼう.

i. S(B)≠S(C); つまり, 部分集合の和が等しくてはならない.
ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.

たとえば, {81, 88, 75, 42, 87, 84, 86, 65} は,
65 + 87 + 88 = 75 + 81 + 84 であるため特殊和集合ではないが,
{157, 150, 164, 119, 79, 159, 161, 139, 158} は
すべての可能な部分集合の対の組み合わせについて両方のルールを満たしており, また S(A) = 1286 である.

7個から 12個の要素を含む 100 個の集合が記された 4K のテキストファイル sets.txt (右クリックして "名前をつけてリンク先を保存") を用いて (上の二例はファイルの最初の 2 集合である), 特殊和集合 A1, A2, ... , Ak をすべて特定し, S(A1) + S(A2) + ... + S(Ak) を求めよ.

注意: この問題は Problem 103 と 106 に関連している.

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

私の回答例は以下の通りです。

def chk1(L):
	import itertools
	M = []
	for i in xrange(len(L)):
		for j in itertools.combinations(L, i+1):
			s = sum(j)
			if s in M: return False
			M.append(s)
	return True

def chk2(L):
	a, b = (len(L)+1)//2, len(L)//2+1
	return sum(L[:a])>sum(L[b:])

def f(fn):
	c, s = 0, 0
	p = open(fn)
	for t in p.readlines():
		L = sorted([int(u) for u in t.split(",")])
		if chk1(L) and chk2(L): s += sum(L); c += 1
	p.close()
	p = None
	return s, c

t = os.path.join(os.path.dirname(__file__), "p105_sets.txt")
s, c = f(t)
print "sum  :", s
print "count:", c

問題文にあるとおり、問１０３の関連問題です。
特殊和集合のチェックは既に問１０３でやっているので、そのまま流用しました。

１．関数chk1(L)
・リストLが最適特殊和集合の以下の条件、
　i. S(B) ≠ S(C); つまり, 部分集合の和が等しくてはならない.
　を満たしていればTrue、満たしていなければFalseを返します。
・詳細は問１０３を参照。

２．関数chk2(L)
・リストLが最適特殊和集合の以下の条件、
　ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.
　を満たしていればTrue、満たしていなければFalseを返します。
・詳細は問１０３を参照。

３．関数f(fn)
・入力ファイルのフルパスを受け取り、特殊和集合の合計値と個数を返します。
・入力ファイルを１行ずつ読み込み、カンマで分けて数値型の要素にして昇順に並べたリストLについて、特殊和集合の条件２つが成り立てば、変数cにためていきます。

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

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

2015-01-12T17:19:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１０４「両端がパンデジタルなフィボナッチ数」
フィボナッチ数列は再帰的な関係によって定義される:

F_n = F_n-1 + F_n-2
F₅₄₁ (113桁)は, 下9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である.
そして, F₂₇₄₉ (575桁)は, 頭から9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である.

Fkが, 頭から9桁と下9桁のどちらも1から9までの数字をすべて含む初めてのフィボナッチ数とするとき, kを求めよ.

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

私の回答例は以下の通りです。
<pre class="brush:python;collapse:true" title="問１０４">
def f(s):
pl, ps = len(s), sorted(s)
a, b, c, d, k, g, n = 1, 0, 1, 0, 1, 0, pl*2
while sorted(str(a)[:pl])!=ps or sorted(str(c)[-pl:])!=ps:
a, b, c, d, k, m = a+b, a, c+d, c, k+1, len(str(a))-n
if pl<m:
u, v = 10**m, 10**n
a, b, c, d, g = a//u, b//u, c%v, d%v, g+m
g += len(str(a))
return k, g

P = "123456789"
k, t = f(P)
print "k :", k
print "digit:", t
</pre>

問題のまま実装すると、数千桁から数万桁の数値の加算に処理時間がかかり、とても１分では終わりません。
フィボナッチ数の先頭と末尾それぞれの必要な桁数分だけ桁調整して計算します。
なお、桁調整の際に必要な桁を超える桁数は累積しておき、後で全体桁数を把握できるようにします。

１．関数f(s)
・文字列sに含まれる文字が先頭と末尾に順不同で存在するフィボナッチ数での項番と桁数を返します。
・変数plは文字列sの文字列長、変数psは文字列sを1文字ずつ昇順に並べた要素として持つリストです。
・kはフィボナッチ数の項番、
　aはフィボナッチ数F_kの上から必要な桁数分、bはフィボナッチ数F_k-1の上から必要な桁数分、
　cはフィボナッチ数F_kの下から必要な桁数分、dはフィボナッチ数F_n-1の下から必要な桁数分、
　gはフィボナッチ数Fkの桁数です。
・変数nは本問の計算に必要な桁数です。
　大きな値にすると加算処理に時間がかかるので必要な桁数以上でなるべく小さな値とします。
　題意にあう必要なチェックをするために少なくとも引数sの文字数分は必要で、また加算の繰り上がりの影響を吸収するためにさらに引数sの文字数分を考慮しておきます。合わせて、計算に必要な桁数nは、引数sの2倍の値とします。

・whileループ内でのフィボナッチ数計算の継続チェックは以下の通りです。
　先頭と末尾を引数と同じ桁数だけ取り出して昇順に並べて、事前に用意した変数psと比較し、どちらかが不一致ならば処理を継続します。

・whileループ内ではフィボナッチ数の計算をします。
　フィボナッチ数F_k、F_k-1の先頭部分a,bにそれぞれa+b、aを設定します。
　フィボナッチ数F_k、F_k-1の末尾部分c,dにそれぞれc+d、cを設定します。
　項番kを１つ進めます。
　変数mは先頭部分から桁調整で減らす桁数で、フィボナッチ数の先頭部分の計算結果の桁数と計算に必要な桁数nの差です。

・変数mはすぐに正の値になりますが、あまり頻繁に桁調整しなくても処理速度に影響ないので、mがplより大きい場合、先頭と末尾両方の桁調整を行います。
　変数uは先頭部分の末尾から減らす桁数分の10の累乗値で、フィボナッチ数F_k、F_k-1それぞれの先頭部分a,bをuで割った商を新たにa,bとします。
　変数vは末尾部分の先頭から減らす桁数分の10の累乗値で、フィボナッチ数F_k、F_k-1それぞれの末尾部分c,dをvで割った余りを新たにc,dとします。
　桁数gには調整して減らした桁数mを累積していきます。

・フィボナッチ数の計算が終わりwhileループ終了後に、桁数gにはフィボナッチ数の先頭部分aの桁数を足して、全体桁数にしておきます。
　なお、計算中に桁調整をしていなければ変数aはフィボナッチ数そのものです。

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

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

2015-01-11T21:27:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１０３「特殊和集合:最適化」
大きさ n の集合 A の要素の和を S(A) で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば, A を特殊和集合と呼ぼう.

i. S(B) ≠ S(C); つまり, 部分集合の和が等しくてはならない.
ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.

ある n に対し S(A) が最小化されていれば, それを最適特殊和集合と呼ぼう. はじめの 5 つの最適特殊和集合は下に与えられる.

n = 1: {1}
n = 2: {1, 2}
n = 3: {2, 3, 4}
n = 4: {3, 5, 6, 7}
n = 5: {6, 9, 11, 12, 13}

ある最適集合 A = {a1, a2, ... , an} に対し, 次の最適集合は B = {b, a1+b, a2+b, ... ,an+b} となりそうである. ここで b は前列の「中央の」要素である.

この「法則」を用いると n = 6 に対する最適集合は A = {11, 17, 20, 22, 23, 24} で, S(A) = 117 と予期するだろう. しかしこれは, 最適に近い集合を与えるアルゴリズムを用いたにすぎないため, 最適集合とはならない. n = 6 に対する最適集合は A = {11, 18, 19, 20, 22, 25} で, S(A) = 115 である. これに対応する集合の文字列は 111819202225 である.

A を n = 7 に対する最適特殊集合とするとき, その集合の文字列を求めよ.

注意: この問題は Problem 105 と 106 に関連している.

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

私の回答例は以下の通りです。

def chk1(L):
	import itertools
	M = []
	for i in xrange(len(L)):
		for j in itertools.combinations(L, i+1):
			s = sum(j)
			if s in M: return False
			M.append(s)
	return True

def chk2(L):
	a, b = (len(L)+1)//2, len(L)//2+1
	return sum(L[:a])>sum(L[b:])

def g(L):
	if not L: return [1]
	c = L[(len(L)-1)//2]
	for b in xrange(c, c+L[-1]):
		M = [a+b for a in [0]+L]
		if chk1(M) and chk2(M): return M

def f(n):
	M = []
	for i in xrange(n):
		M, N, k = g(M), [[]], i//2
		for j in M:
			L = xrange(max(1, j-k), j+k+1)
			N = [s+[t] for s in N for t in L if (not s) or s[-1]<t]
		for L in N:
			if sum(L)<sum(M) and chk1(L) and chk2(L): M = L
	return "".join([str(s) for s in M]), sum(M)

n = 7
t, s = f(n)
print "str:", t
print "sum:", s

ゼロベースで最適特殊集合を作り出そうとするととても１分で処理が終わりません。
「最適に近い集合」が提示されているので、まずこれを基に各要素ごとにいくらかの幅を設定して候補値を選定します。
そしてこの「各要素ごとの候補値の組合せ」から最適特殊解集合を求めることにしました。

１．関数chk1(L)
・リストLが最適特殊和集合の以下の条件、
　i. S(B) ≠ S(C); つまり, 部分集合の和が等しくてはならない.
　を満たしていればTrue、満たしていなければFalseを返します。
・リストLの部分集合の和を作成し、リストMに無ければためていき、あればFlseで終了します。
・ループ変数iは、リストLから部分集合を作る際に取り出す要素数（0～）です。
・ループ変数jは、組み合わせ関数combinationsを利用して、
　リストLからi+1個の要素を取り出した組み合わせ結果のタプルが設定されます。

２．関数chk2(L)
・リストLが最適特殊和集合の以下の条件、
　ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.
　を満たしていればTrue、満たしていなければFalseを返します。
・この条件を満たすかどうかが一番厳しい部分集合の和同士でチェックします。
・一番厳しい部分集合の和同士は、要素を昇順に並べた集合の中で、
　要素が奇数個の場合、最小値から中央値までの和とそれより後の和同士、
　つまり{1,2,3,4,5}ならば、{1,2,3}と{4,5}の和を比較（この場合False）します。
　要素が偶数個の場合、集合の前半の和と後半の２番目に小さい値以降の和同士、
　つまり{1,2,3,4,5,6}ならば、{1,2,3}と{5,6}の和を比較（この場合False）します。
　
３．関数g(L)
・リストLの次の「最適に近い集合」のリストを返します。
・次の「最適に近い集合」は、問題にあるロジックの通り、中央値と中央値を全要素に足した集合です。
・Lが空集合の場合、要素が1だけのリストを返却します。

４．関数f(n)
・要素数がn個の最適特殊集合の要素連結文字列と和を返します。
・既知の最適特殊集合に基づいて要素数が1つ多い最適特殊集合をもとめていきます。
　要素数が1個から始めてn個になるまで順に最適特殊集合を求めていきます。

・リストMは既知の最適特殊集合で、関数gにより次の「最適に近い集合」を設定します。
・ループ変数iはリストMの要素数です。

・ループ変数jは最適に近い値を１つずつ設定します。
・変数kは候補値の幅です。ここでは「最適に近い集合」の要素数の半分とします。
　要素数が４や５ならば各要素の±２に含まれる値を各要素の候補値とします。
　jのループ中で、各要素ごとの候補値リストLとして持ちます。
・リストNは各要素の候補値の組合せリストです。なお昇順になる組合せのみ採用します。

・候補値組合せリストNのループ内で、リストNの中から最適特殊集合を求めます。
・「最適に近い集合」Mよりも和が小さいこと、最適特殊集合の条件２つに合うかチェックし、最適特殊集合として採用します。
　チェックして合うものが無ければ、「最適に近い集合」Mを最適特殊集合とします。

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

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

2015-01-03T10:42:00.000+09:00

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語でネット検索です。

問１０２「三角形の包含」
3つの異なる点が -1000 ≦ x, y ≦ 1000 かつ三角形となるように, デカルト平面上にランダムに与えられる.

以下の2つの三角形を考える.

A(-340,495), B(-153,-910), C(835,-947)
X(-175,41), Y(-421,-714), Z(574,-645)
三角形ABCが原点を内部に含み, XYZは原点を内部に含まないことが確かめられる.

27Kのテキストファイルtriangles.txt(右クリックしリンク先を保存して欲しい) にランダムな1000個の三角形が適当なフォーマットのもと含まれている. 内部に原点を含む三角形の数を答えよ.

注: ファイル中の最初の二つは三角形ABC, XYZである.

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

私の回答例は以下の通りです。

def f(fn):
	c = 0
	p = open(fn)
	for s in p.readlines():
		t, L, M = s.split(","), [], []
		for i in xrange(0, len(t), 2): L.append((int(t[i]), int(t[i+1]))) 
		L.append(L[0])
		for i in xrange(len(t)//2):
			a, b = L[i], (L[i+1][0]-L[i][0], L[i+1][1]-L[i][1])
			M.append(a[0]*b[1] - a[1]*b[0])
		if abs(sum(M))==sum([abs(u) for u in M]): c += 1
	p.close()
	p = None
	return c

s = "p102_triangles.txt"
t = os.path.join(os.path.dirname(__file__), s)
print f(t)

原点が三角形の各辺の左右同じ側にあるかという位置関係で判定します。
ベクトルの外積を利用します。

対象となる点（当問題では原点）が三角形の内部にあれば、
その点は三角形を一周して常に同じ側にあることになります。
つまり、対象となる点（当問題では原点）から各頂点へのベクトルと、
その頂点から次の頂点へのベクトルの外積の符号がすべて同じになります。
なお、平面上の話なので、外積はベクトルにならずスカラー量です。

aベクトル：原点から三角形のi番目の頂点へのベクトル
bベクトル：i番目の点からi+1番目の点へのベクトル
として、
aベクトルとbベクトルの外積の符号が、
正ならばaベクトルが右側、つまり原点はbベクトルの左側で、
負ならばaベクトルが左側、つまり原点はbベクトルの右側です。
３つの外積がすべて正ならば原点を右回りに一周し、
３つの外積がすべて負ならば原点を左回りに一周することになります。

外積の公式は以下のとおりです。
aベクトル=(A_x, A_y)、bベクトル=(B_x, B_y)とすると、
a×b = A_x*B_y - A_y*B_x

以上を実装しました。

１．関数f(fn)
・入力ファイルのフルパスを受け取り、問題にある内部に原点を含む三角形の数を返します。
・ループ変数sは、入力ファイルの１行分で、６つの数字のcsv文字列です。
・変数tは、６つの数字（まだ文字型）を持つリストです。
・一周して計算する都合上、最初の座標を最後にもう一度追加し
座標を４つ分にしてから外積計算を３回行います。
リストLは、平面座標値（タプル型）を最初３つ持ち、最初の１つを末尾に追加して
計４つの座標値を持ちます。
・変数a,bはそれぞれ上記の説明にあるaベクトルとbベクトルです。
・リストMには外積値をためていきます。
・外積の符号一致判定は、外積値の和の絶対値＝外積値の絶対値の和かどうかで行います。

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

	A	B	C	D	E	F	G
A	-	16	12	21	-	-	-
B	16	-	-	17	20	-	-
C	12	-	-	28	-	31	-
D	21	17	28	-	18	19	23
E	-	20	-	18	-	-	11
F	-	-	31	19	-	-	27
G	-	-	-	23	11	27	-

	A	B	C	D	E	F	G
A	-	16	12	21	-	-	-
B	16	-	-	17	20	-	-
C	12	-	-	28	-	31	-
D	21	17	28	-	18	19	23
E	-	20	-	18	-	-	11
F	-	-	31	19	-	-	27
G	-	-	-	23	11	27	-

漫ろ草 SozoroGusa

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

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

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

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

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

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

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

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

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

プロジェクトオイラー 問１１６（別解）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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