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

プロジェクトオイラー(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 )

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

プロジェクトオイラー(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

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

プロジェクトオイラー(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

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

プロジェクトオイラー(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

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

プロジェクトオイラー(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 )

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

プロジェクトオイラー(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

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

プロジェクトオイラー(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