プロジェクトオイラー Problem30

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

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

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

• 1634 = 14 + 64 + 34 + 44
• 8208 = 84 + 24 + 04 + 84
• 9474 = 94 + 44 + 74 + 44

ただし, 1=14は含まないものとする.
この数たちの和は 1634 + 8208 + 9474 = 19316 である.
各桁を5乗した数の和が元の数と一致するような数の総和を求めよ.


私の解答例は以下です。

def g(n):
	i, m = 0, 9**n
	while True:
		i += 1
		if m*i<10**i: break
	return m*i
	
def f(n):
	L = []
	for i in xrange(2, g(n)):
		if i==sum([int(t)**n for t in str(i)]): L.append(i)
	return L
	
L = f(5)
print sum(L),L

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

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

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

・i, m = 0, 9**n
　初期値設定で、桁数iに0、mに9のn乗値を設定します。

・while True:
 i += 1
　9をn乗して桁数分足した値が、その桁数の最小値（10のn乗）にすら達しない桁数が来るまで、無限ループで桁数iを1ずつ増やします。

・　if m*i<10**i: break
　return m*i
　9をn乗して桁数分足した値が、その桁数の最小値（10のn乗）にすら達しない桁数かを判定し、このような桁数に達したら、桁数iのループを終了し、9をn乗して桁数分足した値を返します。
　

２．関数f(n)
・for i in xrange(2, g(n)):
　ループ変数iは、2以上で検討に十分な値（関数g(n)の戻り値）までの整数です。

・if i==sum([int(t)**n for t in str(i)]): L.append(i)
　各桁をn乗した数の和が元の数と一致するような数をリストLに貯めていきます。

・return L
　問題にある数を貯めたリストLを返します。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
443839 [4150, 4151, 54748, 92727, 93084, 194979]

プロジェクトオイラー Problem29

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

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

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

• 22=4, 23=8, 24=16, 25=32
• 32=9, 33=27, 34=81, 35=243
• 42=16, 43=64, 44=256, 45=1024
• 52=25, 53=125, 54=625, 55=3125

これらを小さい順に並べ, 同じ数を除いたとすると, 15個の項を得る:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

2 ≤ a ≤ 100, 2 ≤ b ≤ 100 で同じことをしたときいくつの異なる項が存在するか?


私の解答例は以下です。

def f(m, n):
	L = []
	for a in xrange(m, n+1):
		for b in xrange(m, n+1):
			L.append(a**b)
	return len(set(L))
	
print f(2,100)

１．関数f(m, n)
・m以上n以下のa,bについて、aのb乗の値の異なる項の数を返します。

・for a in xrange(m, n+1):
  for b in xrange(m, n+1):
　ループ変数a, bはそれぞれm以上n以下の値をとる二重ループです。

・L.append(a**b)
　リストLにaのb乗の値を全て設定します。

・return len(set(L))
　set型は、重複するオブジェクトを持たない、順序付けられていない要素の集まりのことです。
　set型へ型変換することでリストLから重複を除きます。
　その後、len関数で要素数を数えて返します。


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

プロジェクトオイラー Problem28

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

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

Problem 28
1から初めて右方向に進み時計回りに数字を増やしていき,
5×5の螺旋が以下のように生成される:
21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

両対角線上の数字の合計は101であることが確かめられる.
1001×1001の螺旋を同じ方法で生成したとき, 対角線上の数字の合計はいくつだろうか?


私の解答例は以下です。

def g(n):
 if n<1 or (not n%2): return 0
 elif n==1: return 1
 s, t = n-1, n-2
 u = t*t+s
 return u+(u+s)+(u+s*2)+(u+s*3)
 
def f(n): return sum([g(i) for i in xrange(1, n+1, 2)])
 
print f(1001)

１．g(n)
・関数g(n)は、一辺がn個の四角形の四隅値の合計値を返します。

・s, t = n-1, n-2
　sは一辺がn個の四角形の隣接する四隅の値の差、
　tは１つ内側の正方形の一辺の個数です。

・u = t*t+s
　uは一辺がn個の四角形の最小の四隅値です。結果として右下隅の数字です。
　まず１つ内側の正方形内の個数は、t*tです。
　そこから１つ右に進み、一辺n個の四角形に出るとその位置は、
　この四角形の右上隅の１つ下なので、右下隅までの長さはn-1です。
　これらの和uが右下隅値になります。
　
・return u+(u+s)+(u+s*2)+(u+s*3)
　あとは、右下隅値を基準に、四隅値の差分sを増しながら、四隅のすべての値を足します。
　
２．f(n)
・関数f(n)は、一辺がn個の四角形の対角線上の値の和を返します。
・sum([g(i) for i in xrange(1, n+1, 2)])
　一辺n個の四角形の一辺は1,3,5,・・・nの奇数です。
　まずxrange関数で1からn以下の奇数を発生させ、ループ変数iに設定します。
　そしてfor文の前に送り、g(i)を順番に計算して配列に貯めていきます。
　その後、その配列をsum関数で合計し、返却します。


（別解）

print sum([4*i*i-6*i+6 for i in xrange(3, n+1, 2)])+1

先ほどの関数g(n)はnの二次式にまとめることができます。
つまり、n>2の条件下で、
s = n-1
t = n-2
u = t*t+s
のときの以下の値を計算しておきます。
  u+(u+s)+(u+s*2)+(u+s*3)
= u*4 + s*6
= (t*t+s)*4 + s*6
= 4*t*t + 10*s
= 4*(n-2)*(n-2) + 10*(n-1)
= 4*(n*n - 4*n + 4) + (10*n - 10)
= 4*n*n - 6*n + 6

以上から、n≧3のとき上記の式で、n=1の対角線値として1を足すことにします。
まず、xrange関数で3からn以下の奇数を発生させ、ループ変数iに設定します。
そしてfor文の前に送り、「4*i*i-6*i+6」を順番に計算して配列に貯めていきます。
その後、その配列をsum関数で合計し、n=1のときの1を足して、返します。

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

プロジェクトオイラー Problem27

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

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

Problem 27
オイラーは以下の二次式を考案している:
n2 + n + 41
この式は, nを0から39までの連続する整数としたときに40個の素数を生成する.
しかし, n = 40のとき402 + 40 + 41 = 40(40 + 1) + 41となり41で割り切れる.
また, n = 41のときは412 + 41 + 41であり明らかに41で割り切れる.

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

さて, |a| < 1000, |b| < 1000 として以下の二次式を考える.
n2 + an + b (ここで|a|は絶対値)
n=0から始めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の,係数a, bの積を答えよ.


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

def p(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(a, b, n, L):
	for i in xrange(n):
		s = i*i+a*i+b
		if s not in L: break
	return i
	
def f(n):
	L, M = p(n), [0, 0, 0]
	for b in L+[-s for s in L]:
		for a in xrange(-999, 1000, 2):
			if abs(1+a+b) not in L: continue
			s = g(a, b, n, L)
			if M[2]<s: M = [a, b, s]
	return M
	
a, b, s = f(1000)
print "ab =",a*b,", n2",a,"n +",b,", the number of prime =", s

－－－－－

総当りするにはa,bの範囲が広すぎるので、範囲を絞り込むために、
f(n) = n^2 + a*n + b
に小さい値を代入して様子を見ます。

・f(0)=b
　bは素数　・・・(A)
　素数は「2かそれ以上の奇数」の集合に含まれるので、
　bは「2かそれ以上の奇数」に含まれる　・・・(B)

・f(1)=1+a+b
　「1+a+b」は素数　・・・(C)
　(C)に(B)を当てはめると、
　aは奇数　・・・(D)

これらをふまえて、

１．関数p(n)
・n未満の素数リストを返します。
・problem 010を改良しました。

２．関数g(a, b, n, L)
・aとbは「n^2 + a*n + b」の係数、nはこの式のnの上限値です。
　Lは範囲内の素数のプラスマイナス両符号分のリストです。

・a,b,nによる計算値が、素数リストLに無い値になったときにループを抜け、
　そのときのインデックス値を返します。
　このインデックス値が、計算値のうち、素数が続いた数になります。

３．関数f(n)
・for b in L+[-s for s in L]:
　bは、上記(A)より、n未満の素数のプラスマイナス両符号分を範囲とします。
　リストは+演算子で、両方の要素を合わせたリストになります。
　
・for a in xrange(-999, 1000, 2):
　aは、上記(D)より、絶対値1000未満の奇数を範囲とします。
　
・if abs(1+a+b) not in L: continue
　範囲を絞ったa,bを総当りして、上記(C)より、「1+a+b」が対象素数リストに無ければ次の候補へ処理と進めます。

・s = g(a, b, n, L)
　対象素数リストにあれば、そのときのa,bは条件を満たすので関数gで、計算値に
　何個素数が続いて現れるかチェックします。、
　
・if M[2]<s: M = [a, b, s]
　連続して出現する素数の個数が最大の場合、リストMにa,bの値とともに素数個数も保存します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
ab = -59231 , n2 -61 n + 971 , the number of prime = 62

プロジェクトオイラー Problem26

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

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

Problem 26
単位分数とは分子が1の分数である。
分母が2から10の単位分数を10進数で表記すると次のようになる。
1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1
0.1(6)は 0.166666... という数字であり、1桁の循環節を持つ。
1/7 の循環節は6桁ある。
d < 1000 なる 1/d の中で循環節が最も長くなるような d を求めよ。


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

def f(n):
	L = [0, 0]
	for d in xrange(1, n):
		a, M = 1, []
		while True:
			a, b = divmod(a, d)
			if not b:
				t = 0
				break
			elif b in M:
				u = M.index(b)
				t = len(M)-u
				break
			else:
				M.append(b)
				a = b*10
		if L[1]<t: L = [d, t]
	return L
	
d, t = f(1000)
print "d =", d, ", digit of recurring cycle =", t

－－－－－

１．関数f(n)
・n未満の正の整数dについて、1/dの小数部の循環桁数が最長であるd、およびそのときの循環桁数をリストにして返却します。
・やり方は割り算の筆算の要領で、余りが0か過去にでた同じ余りの値になるまで、余りの値の右に0を付加（余りの値を10倍）して割り算を続けるという方法です。

・L = [0, 0]
　上記の返却リストの初期化です。0クリアしておきます。
・for d in xrange(1, n):
　ループ変数dは、n未満の正の整数です。
・a, M = 1, []
　筆算の要領で1桁ずつ割り算していきます。
　aはそのときの割られる数、リストMはそのときの余りを貯めます。
　初期値はそれぞれ、1と空のリストです。
・while True:
　無限ループです。1/dは無限小数ではなく、割り切れるか循環小数かが確定するまで、割り算の筆算の要領で処理を続けます。
・a, b = divmod(a, d)
　divmod関数は割り算の商と余りを同時に返します。a÷dの商がaで、余りがbです。

・if not b:
　論理式では0以外はTrueです。Falseということは余りbが0、つまり割り切れたので循環小数桁数は0です。
　ループ終了で次のn未満の正の整数の処理へ進みます。
・elif b in M:
　 u = M.index(b)
　 d = len(M)-u
　余りbが余りリストMにあるので、今後は同じ割り算を繰り返すことになり循環小数の循環部分が一周しました。
　余りbが、余りリストMの何番目かを求めて、uとします。
　u番目よりも前は循環部分より前の固定値なので、ここまでの割り算回数（余りの個数）から差し引いて循環小数桁数を求めます。
　こうしてループ終了で次のn未満の正の整数の処理へ進みます。
・else:
　 M.append(b)
　 a = b*10
　上記の２つのケース以外は、循環小数かどうか未定です。割り算をもう1桁進めます。
　まず、余りbを、余りリストに追加します。
　そして、余りbを10倍して次の割られる数とします。
　割り算の筆算で余りの数字の右に0を書き足して割り算を続けるのと同じです。

・if L[1]<t: L = [d, t]
　循環小数桁数が今までの値を超えたら、分母の数字とその循環小数桁数をリストLに差し替えます。
・指定した範囲の1/nをすべて処理し、結果リストLを戻します。

２．関数の外
・上記の関数fに指定の値1000を渡せば、[解答の分母, その循環桁数]のリストが求められます。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
d = 983 , digit of recurring cycle = 982

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

プロジェクトオイラー Problem25

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

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

Problem 25
フィボナッチ数列は以下の漸化式で定義される:
Fn = Fn-1 + Fn-2, ただし F1 = 1, F2 = 1.
最初の12項は以下である.

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

12番目の項, F12が3桁になる最初の項である.
1000桁になる最初の項の番号を答えよ.


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

def f(n):
	if n<1: return False
	i, a, b = 1, 1, 0
	while len(str(a))<n: i, a, b = i+1, a+b, a
	return i
	
print f(1000)

－－－－－
１．関数f(n)
・n桁になる最初のフィボナッチ数の項の番号を返します。
・if n<1: return False
　定義から、最初に1桁になるのは項の番号=1なので、1未満はFalseを返します。
・i, a, b = 1, 1, 0
　iは項の番号、aはFn-1、bはFn-2　です。
　３つの変数を一度に初期化します。
　項の番号=1のとき、１つ前のF0=1、２つ前は0です。
・while len(str(a))<n:
　フィボナッチ数aを文字型にして文字列数を求め、指定桁n未満ならば処理を続けます。
・ i, a, b = i+1, a+b, a
　フィボナッチ数を1つ進めます。
　項番号iは+1、a（=Fn-1）はa+b、b（=Fn-2）はa（=Fn-1）にします。

２．関数の外
・上記の関数fに、指定桁1000を渡せば求める値になります。


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

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

プロジェクトオイラー Problem24

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

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

Problem 24
順列とはモノの順番付きの並びのことである.
たとえば, 3124は数1, 2, 3, 4の一つの順列である.
すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ.
0と1と2の順列を辞書順に並べると
012 021 102 120 201 210
になる.
0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目を答えよ.


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

def g(n):
	if n<=1: return 1
	else: return n*g(n-1)
	
def f(s, n):
	L0, L1 = sorted([i for i in s]), []
	if n<1 or g(len(s))<n: return False
	for i in xrange(len(s), 0, -1):
		u = g(i)/i
		v = (n-1)/u
		n -= u*v
		L1.append(L0[v])
		L0.pop(v)
	return "".join(L1)
	
print f("0123456789", 1000000)

－－－－－
主要部分の考え方は以下の通りです。
手始めに、例として、リストL=[0,1,2]という3個の要素がある場合を考えます。
辞書順パターン全体は3!=6通りです。
各パターン最初の要素には、3!パターンを3で割った数ずつ、元のリストの要素が使われます。
(3!/3)*0番目～(3!/3)*1番目までは、最初の要素は元の1番目の要素「0」
(3!/3)*1番目～(3!/3)*2番目までは、最初の要素は元の2番目の要素「1」
(3!/3)*2番目～(3!/3)*3番目までは、最初の要素は元の3番目の要素「2」

これをリストLに要素がm個ある場合に拡張すると以下の通りです。
辞書順パターン全体はm!通りです。
各パターン最初の要素には、m!パターンをmで割った数ずつ、元のリストの要素が使われます。
(m!/m)*0番目～(m!/m)*1番目までは、最初の要素は元の1番目の要素
(m!/m)*1番目～(m!/m)*2番目までは、最初の要素は元の2番目の要素
・・・
(m!/m)*(m-1)番目～(m!/m)*m番目までは、最初の要素は元のn番目の要素
上記の考え方をpythonで実装しました。

２つの関数を使用しています。
１．g(n)
・階乗。problem 20から流用しました。
・終了条件を改良して、nが1未満の値でもエラーにならないようにしました。

２．f(s, n)
・文字列sの文字1つひとつを辞書順に並べたときのn番目のパターンを返却します。
・L0, L1 = sorted([i for i in s]), []
　L0は文字1つひとつを要素にしてソートしたリストです。
　L1はn番目の辞書順n番目の状態のリストです。初期状態は空リストです。
・if n<1 or g(len(s))<n: return False
　n番目ということなのでn<1なら処理しません。
　nは要素n個の辞書順パターン数（nの階乗=n!）を超えることはなく、この場合も処理しません。
・for i in xrange(len(s), 0, -1):
　ループ変数iは未使用の要素数です。引数sの文字数から0まで1ずつ減らしていきます。
・u = g(i)/i
　各未使用要素が最上位にくる、パターン数の幅です。（iの階乗値）÷iです。
・v = (n-1)/u
　未使用要素のうち、n番目のパターンにあたる値の、元リストでのindex番号です。
　何番目かの値nを、最上位値が同一であるパターン数の幅uで割ります。
・n -= u*v
　何番目かの値nのうち、要素未定でまだ定まっていない残り分、あといくつ進めばいいかを示します。
・L1.append(L0[v])
　元リストのindex番号vの要素を求めるリストの最後に追加します。
・L0.pop(v)
　求めるリストに追加したので、元リストからindex番号vの要素を削除し、次のループにいきます。
・return "".join(L1)
　ループ終了後、並び終えたリストL1を連結して、文字列に変換して戻り値とします。
　
３．関数の外
・上記の関数fに、文字列"0123456789"と、1000000（番目）を渡せば求める値になります。


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

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