2012年5月31日木曜日

プロジェクトオイラー Problem17_2

前回のproblem17のソースコードを見て、61mgさんから改良意見をいただきました。
変換した英単語を集める最後のループでカラ回りする記述が冗長とのことで、これを無くしてみました。


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

D1 = {0:"", 1:"one", 2:"two", 3:"three", 4:"four", 
	5:"five", 6:"six", 7:"seven", 8:"eight", 9:"nine"}
	
D10 = {10:"ten", 11:"eleven", 12:"twelve", 13:"thirteen", 
	14:"fourteen", 15:"fifteen", 16:"sixteen", 17:"seventeen", 
	18:"eighteen", 19:"nineteen"}
	
D20 = {20:"twenty", 30:"thirty", 40:"forty", 50:"fifty", 
	60:"sixty", 70:"seventy", 80:"eighty", 90:"ninety"}
	
def f(n):
	t = 0
	for i in xrange(1, n+1):
		L, M = [int(j) for j in str(i).rjust(4, "0")], []
		if L[-4]: M += [D1[i//1000], "thousand"]
		s = i%100
		if L[-3]:
			M += [D1.get(L[-3], ""), "hundred"]
			if s: M += ["and"]
		if s<10: M += [D1.get(s, "")]
		elif s<20: M += [D10.get(s, "")]
		else: M += [D20.get(L[-2]*10, ""), D1.get(L[-1], "")]
		t += sum([len(s.replace(" ","")) for s in M])
	return t
	
print f(1000)
-----

・辞書D1に1桁の数字の部品の英単語を設定しました。同様に、
辞書D10に10代の数字(10~19)、辞書D20に20以上の数字を設定しました。
100と1000は処理中に直書きしています。

・L, M = [int(j) for j in str(i).rjust(4, "0")], []
リストLに変換元の数字を、左0埋めで4桁にしてから1桁ずつを要素に設定します。
リストMは英単語を設定するので初期化しておきます。

・文字列.rjust(桁数, 埋め文字)
文字列を右詰めして指定桁数にします。あいた部分は埋め文字で埋めます。
ここでは、例えば以下のようになります。"1" → "0001"

・if L[-4]: M += [D1[i//1000], "thousand"]
下から4つ目は、千の位の値です。
これが0以外(論理的にTrue)のとき、例えば["one", "thousand"]のように設定します。

・if L[-3]:
   M += [D1.get(L[-3], ""), "hundred"]
   if s: M += ["and"]
下から3つ目は、百の位の値です。
これが0以外(論理的にTrue)のとき、例えば["one", "hundred"]のように設定します。
また、sは100で割った余りで、これが0以外なら"and"も設定します。

・if s<10: M += [D1.get(s, "")]
elif s<20: M += [D10.get(s, "")]
else: M += [D20.get(L[-2]*10, ""), D1.get(L[-1], "")]
下2桁の処理です。
sは100で割った余りで、これが10未満なら1桁、さらに20未満なら10代、その他は20以上の数字と1桁、といった組合せで英単語に変換します。

・t += sum([len(s.replace(" ","")) for s in M])
ここまで組み立ててきた英単語について、replace関数で半角空白を削除し、len関数で文字数を数え、sum関数で合計を取ります。


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



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

2012年5月29日火曜日

プロジェクトオイラー Problem17

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

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

Problem 17
1 から 5 までの数字を英単語で書けば one, two, three, four, five であり、全部で 3 + 3 + 5 + 4 + 4 = 19 の文字が使われている。
では 1 から 1000 (one thousand) までの数字をすべて英単語で書けば、全部で何文字になるか。

: 空白文字やハイフンを数えないこと。
例えば、342 (three hundred and forty-two) は 23 文字、
115 (one hundred and fifteen) は20文字と数える。
なお、"and" を使用するのは英国の慣習。

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

D = {0:"", 1:"one", 2:"two", 3:"three", 4:"four", 
	5:"five", 6:"six", 7:"seven", 8:"eight", 9:"nine", 10:"ten", 
	11:"eleven", 12:"twelve", 13:"thirteen", 14:"fourteen", 
	15:"fifteen", 16:"sixteen", 17:"seventeen", 18:"eighteen", 
	19:"nineteen", 20:"twenty", 30:"thirty", 40:"forty", 50:"fifty", 
	60:"sixty", 70:"seventy", 80:"eighty", 90:"ninety"}

def f2(n): 
	sho, amari = divmod(n, 10)
	return D.get(n, " ".join([D[sho*10], D[amari]]))

def f3(n):
	sho, amari = divmod(n, 100)
	L  = [D[sho], "hundred"]+{0:[]}.get(amari, ["and", f2(amari)]) 
	return " ".join(L)

def f4(n):
	sho, amari = divmod(n, 1000)
	L = [D[sho], "thousand", {True:f3(amari)}.get(amari, "")]
	return " ".join(L)

def f(n):
	L = [f2(i) for i in xrange(1, n+1) if i<100] \
	  + [f3(i) for i in xrange(1, n+1) if 100<=i<1000] \
	  + [f4(i) for i in xrange(1, n+1) if 1000<=i]
	M = [len(s.replace(" ","")) for s in L]
	return sum(M)
 
print f(1000)
-----
・pythonでは連想配列のことを辞書dictionaryと呼びます。
・辞書Dに100未満の数字の部品の英単語を設定しました。
 100と1000は処理中に直書きしています。


1.f2(n)
・2桁以下の数字の英単語を返します。


・sho, amari = divmod(n, 10)
 divmod関数は2つの引数を除算したときの商と余りの組を返します。
 ここでは、10で割った商をsho、余りをamariに設定します。


・" ".join([D[sho*10], D[amari]])
 区切り文字.join(要素)で、要素を区切り文字で連結した文字列を作成します。
 ここではD[sho*10]とD[amari]を半角空白区切りで連結した文字列を作成します。
 例)n=23の場合、D[20]とD[3]の空白区切りで「twenty three」。


・return D.get(n, " ".join([D[sho*10], D[amari]]))
 「D.get(n, 式)」は、辞書Dのキーに値aがあればD[n]を返し、無ければ式の値を返す関数です。
 辞書Dにnの英単語があればそれを返し、無ければ10の位と1の位から英単語を作成して返します。
 

2.f3(n)
・3桁の数字の英単語を返します。


・sho, amari = divmod(n, 100)
 divmod関数は2つの引数を除算したときの商と余りの組を返します。
 ここでは、100で割った商をsho、余りをamariに設定します。


・L  = [D[sho], "hundred"]+{0:[]}.get(amari, ["and", f2(amari)])
 [D[sho], "hundred"]は100の位で、["one",  "hundred"]などとなります。
 {0:[]}.get(amari, ["and", f2(amari)])は、3桁の数字のうち下2桁の処理です。
 amariが0の場合、1,2桁目が0ということで、空リスト[]です。
 amariがある場合、["and", amariの2桁の英単語]です。
 

・return " ".join(L)
 ここまで設定してきた英単語の部品を半角空白区切りで連結して返します。


3.f4(n)
・4桁の数字の英単語を返します。

・上記のf3(n)関数とほとんど同じなので、違う部分のみ書きます。
・L = [D[sho], "thousand", {True:f3(amari)}.get(amari, "")]
 1000の位の数字、"thousand"、amariが論理的にTrue(0以外)ならば3桁数字の英単語、これらをリストに設定し、次の行で半角空白区切りで連結して返します。


4.f(n)
・L = [f2(i) for i in xrange(1, n+1) if i<100] \
   + [f3(i) for i in xrange(1, n+1) if 100<=i<1000] \
   + [f4(i) for i in xrange(1, n+1) if 1000<=i]


 「\」は継続行を示しています。
3つのリストを連結します。それぞれのリストは同じ構造をしています。
for文で1からnまでの値を取り出し、後ろのif文に送り、Trueの場合のみfor文の前の処理をします。
最初のリストは、2桁以下の数字をf2関数で処理した1つひとつの英単語リスト
次のリストは、3桁の数字をf3関数で処理した1つひとつの英単語リスト
最後のリストは、4桁の数字をf4関数で処理した1つひとつの英単語リスト

・M = [len(s.replace(" ","")) for s in L]
 上記で作成した1からnまでの英単語の1つひとつについて、半角空白を削除した文字列長をリストMに設定します。

・return sum(M)
 上記文字列長の合計値を返します。


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

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

2012年5月20日日曜日

プロジェクトオイラー Problem16

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

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

Problem 16
215 = 32768 であり、これの各数字の合計は 3 + 2 + 7 + 6 + 8 = 26 となる。
同様にして、21000 の各数字の合計を求めよ。


私の解答例は以下です。
-----
def f(n): return sum([int(i) for i in str(2**n)])
print f(1000)
-----

1.関数f(n)
2のn乗の各桁の和を返します。

・2**n
 「**」演算子は累乗です。ここでは2のn乗のことです。
 107・・・376という302桁に数字になります。
pythonでは値の桁数制限がないのでこの表記で2の1000乗でも大丈夫です。
・str関数で文字列化します。
 ”107・・・376”という302文字の文字列です。
・次にlist関数で各桁1文字ずつのリストにします。
["1", "0", "7",・・・, "3", "7", "6”]というリストになります。
・[]を用いて、内装表示で、各桁1ずつのリストから要素1つずつを取り出して、int関数で数値に変換したリストになります。
[1, 0, 7,・・・, 3, 7, 6]というリストになります。
・sum関数で上記リストの和を求めます。


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

(追記)
・20120715

 list(str(2**n)) -> str(2**n) に修正。
 stringオブジェクトはlistオブジェクトと同じシーケンス(sequence)という種類のオブジェクトで、ループで回すことができるため。
 
・20120715
 ソースコード部分にSyntaxHighlighterを導入。

プロジェクトオイラー Problem15

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

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

Problem 15
2 × 2 のマス目の左上からスタートした場合、
引き返しなしで右下にいくルートは 6 つある。



では、20 × 20 のマス目ではいくつのルートがあるか。

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

def fact(n):
	if n<=0: return 1
	return fact(n-1)*n
	
def comb(n, m): return fact(n)//fact(n-m)//fact(m)

def f(a, b): return comb(a+b, a)

print f(20, 20)
-----

引き返しなしなので、マス目の辺を合計(a+b)本分、通ることになります。
これより多いことも少ないこともありません。
つまり、この問題は縦線a本と横線b本を並べた、

縦、横、横、縦、・・・、縦
などという(a+b)個の配列のパターン数を求めること同じです。

また縦線以外は横線だけなので、どちらか一方の配置が決まれば、残りは全部もう一方という1パターンに決まります。
つまり、この問題は縦線a本を(a+b)個の置き場に散らした、
縦、○、○、縦、・・・、縦

などという(a+b)個の配列のパターン数と同じです。

さらには、先ほどの縦という文字の配置位置番号を取り出すと、
1,4,・・・,(a+b)

などという数列のパターン数と同じことです。
これは、(a+b)個の中からa個を選ぶ組合せのパターン数と同じです。

このように問題文を読み替えたところで、使用している関数の説明です。

ここでは3つの関数を使っています。
1.fact(n)
・nの階乗を返す関数です。
 階乗は記号!で表記し、1からnまでの積です。n! = 1x2x・・・xn です。

・if n<=0: return 1
 return fact(n-1)*n
「fact(n-1)*n」は、n-1の階乗値とnの積、つまりnの階乗を計算します。
このように、関数内で関数自分自身を呼び出す記述を「再帰」といいます。
if文は、nが0の場合に再帰を終了させるための設定です。
この記述があるのでn-1(1つ前)の階乗値を次々に求めていき、
nが0になったところまで遡って1が返り、
return文で戻りながら次々に積を計算していきます。

2.comb(n, m)
・組合せ(combination)の場合の数、aCb を返す関数です。
・n個の中からm個を選ぶ選び方について、
 選ぶ順番を入れ替えたら違う組とする選び方を「順列」(permutation)といいます。
 選ぶ順番を入れ替えても同じ組とする選び方を「組合せ」(combination)といいます。

例)sとtという2つから2つ選ぶ場合
順列は(s,t)と(t,s)の2通り、組み合わせは(s,t)[または(t,s)]の1通りです。

n個の中からm個を選ぶ選び方が何通りあるかというパターン数、 数学用語では「場合の数」の公式は以下の通りです。
順列   nPm = n!/(n-m)!
組合せ nCm = n!/(n-m)!m!
(参考)順列(wikipedia)組合せ(wikipedia)


2つの式の違いは分母の「m!」で、これは選んだものの内部で選んだ順番を入れ替えると同じになるパターン数です。
同時に選ぶなど、選んだものの中で順番を関係無し、入れ替えても同じで1パターンと見なすのが「組合せ」です。

例)5つのモノから2つ選ぶ場合
順列   5P2 = (5x4x3x2x1)/(3x2x1)= 5x4 = 20(通り)
組合せ 5C2 = (5x4x3x2x1)/{(3x2x1)x(2x1)} = (5x4)/(2x1) = 10(通り)

・fact(n)//fact(n-m)//fact(m)
 演算子//は整数部分までの割り算の商です。組合せnCmを公式そのままの記述です。

3.f(a, b)
・縦a横bのマス目で左上から右下に引き返しなしでいくルート数です。
・comb(a+b, a)
(a+b)個の中からa個を選ぶ組合せのパターン数、(a+b)Caを求めます。
縦線に注目するか横線に注目するかの違いなので、(a+b)Cbでも同じ答えです。



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

(追記)
・20120715

 関数fact()の停止条件をn==0 -> n<=0 に修正。
 nが0未満の場合、無限ループになるため。
・20120715
 ソースコード部分にSyntaxHighlighterを導入。

プロジェクトオイラー Problem14

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

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

Problem 14
正の整数に以下の式で繰り返し生成する数列を定義する。
n → n/2 (n が偶数)
n → 3n + 1 (n が奇数)

13からはじめるとこの数列は以下のようになる。
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

13から1まで10個の項になる。

この数列はどのような数字からはじめても最終的には 1 になると考えられているが、まだそのことは証明されていない(コラッツ問題)
さて、100万未満の数字の中でどの数字からはじめれば一番長い数列を生成するか。

注意: 数列の途中で100万以上になってもよい



私の解答例は以下のとおりです。
-----
def g(n, i=1):
	if n==1: return i
	if n%2: return g(n*3+1, i+1)
	else: return g(n/2, i+1)
	
def f(n):
	a = b = 0
	for i in xrange(n-(1-n%2), n/3, -2):
		j = g(i)
		if b<j: a, b = i, j
	return a, b
	
a, b = f(1000000)
print a, ", len =",b
-----

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

1.g(n, i=1)
・nで始まるコラッツ数列が1になるまでの要素数を返します。
・引数iは何番目かという順番値です。初期値は1です。

・if n==1: return i
 1から先のコラッツ数列は、1→4→2→1→・・・と振動しますので、1になったら終了です。

 このif文は、nが1の場合に処理を終了させるための設定です。
・if n%2: return g(n*3+1, i+1)
 else: return g(n/2, i+1)
 コラッツ数列の定義です。
 %演算子は割り算の余りを求める演算子です。
 奇数は余りが1(論理判定でTrue)で、現在値を3倍して1加え、順番値も次に進めます。
 偶数は余りが0(論理判定でFalse)で、現在値を2で割り、順番値も次に進めます。
このように、関数内で自分自身の関数を呼び出す記述を「再帰」といいます。
問題文にもあるように必ず1になることは証明はされていませんが、
いつかは1になるという想定です。

なお、コラッツ数列は大学入試センター試験にも出題されています。
平成23年度(2011年度) 数学Ⅱ数学B 第6問(大学入試センターの公式サイト)
問題(pdf) 
解答(pdf)
公式サイトには過去3年分だけ載っているので、そのうちリンク先が消えるかもしれません。

2.f(n)
・iから始めて1になるまでのコラッツ数列のうち、最大項数を求めます。
・a = b = 0
 最大項数のときの開始値aとその最大項数bとし、0クリアしておきます。
・for i in xrange(n-(1-n%2), n/3, -2):

 コラッツ数列の開始値として、n-(1-n%2)から n/3まで, 2ずつ減らしていきます。
・「n-(1-n%2)」はnを超えない最大奇数です。
 %演算子は割り算の余りなので、(1-n%2)はnが偶数なら1で奇数なら0となり、この値をnから引くことで、偶数ならn-1で奇数ならnとなります。
 コラッツ数列の定義から、奇数の後は約3倍に増え、偶数の後は1/2に減るので、 最大項数になるような初項は必ず奇数だからです。
 また、奇数の後は約3倍に増えるため、n/3より小さい値は最大項数になることはありません。
・j = g(i)
 iから始めて1になるまでのコラッツ数列の項目数をjにセットします。
・if b<j: a, b = i, j
 そしてここまでの最大項数より大きければ、そちらを保存します。


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


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

2012年5月14日月曜日

プロジェクトオイラー Problem13

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

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

Problem 13
以下の50桁の数字100個の総和の上位10桁を求めよ。
(問題の数字は以下の変数p)

私の解答例は以下のとおりです。
-----
p = """
37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
64906352462741904929101432445813822663347944758178
92575867718337217661963751590579239728245598838407
58203565325359399008402633568948830189458628227828
80181199384826282014278194139940567587151170094390
35398664372827112653829987240784473053190104293586
86515506006295864861532075273371959191420517255829
71693888707715466499115593487603532921714970056938
54370070576826684624621495650076471787294438377604
53282654108756828443191190634694037855217779295145
36123272525000296071075082563815656710885258350721
45876576172410976447339110607218265236877223636045
17423706905851860660448207621209813287860733969412
81142660418086830619328460811191061556940512689692
51934325451728388641918047049293215058642563049483
62467221648435076201727918039944693004732956340691
15732444386908125794514089057706229429197107928209
55037687525678773091862540744969844508330393682126
18336384825330154686196124348767681297534375946515
80386287592878490201521685554828717201219257766954
78182833757993103614740356856449095527097864797581
16726320100436897842553539920931837441497806860984
48403098129077791799088218795327364475675590848030
87086987551392711854517078544161852424320693150332
59959406895756536782107074926966537676326235447210
69793950679652694742597709739166693763042633987085
41052684708299085211399427365734116182760315001271
65378607361501080857009149939512557028198746004375
35829035317434717326932123578154982629742552737307
94953759765105305946966067683156574377167401875275
88902802571733229619176668713819931811048770190271
25267680276078003013678680992525463401061632866526
36270218540497705585629946580636237993140746255962
24074486908231174977792365466257246923322810917141
91430288197103288597806669760892938638285025333403
34413065578016127815921815005561868836468420090470
23053081172816430487623791969842487255036638784583
11487696932154902810424020138335124462181441773470
63783299490636259666498587618221225225512486764533
67720186971698544312419572409913959008952310058822
95548255300263520781532296796249481641953868218774
76085327132285723110424803456124867697064507995236
37774242535411291684276865538926205024910326572967
23701913275725675285653248258265463092207058596522
29798860272258331913126375147341994889534765745501
18495701454879288984856827726077713721403798879715
38298203783031473527721580348144513491373226651381
34829543829199918180278916522431027392251122869539
40957953066405232632538044100059654939159879593635
29746152185502371307642255121183693803580388584903
41698116222072977186158236678424689157993532961922
62467957194401269043877107275048102390895523597457
23189706772547915061505504953922979530901129967519
86188088225875314529584099251203829009407770775672
11306739708304724483816533873502340845647058077308
82959174767140363198008187129011875491310547126581
97623331044818386269515456334926366572897563400500
42846280183517070527831839425882145521227251250327
55121603546981200581762165212827652751691296897789
32238195734329339946437501907836945765883352399886
75506164965184775180738168837861091527357929701337
62177842752192623401942399639168044983993173312731
32924185707147349566916674687634660915035914677504
99518671430235219628894890102423325116913619626622
73267460800591547471830798392868535206946944540724
76841822524674417161514036427982273348055556214818
97142617910342598647204516893989422179826088076852
87783646182799346313767754307809363333018982642090
10848802521674670883215120185883543223812876952786
71329612474782464538636993009049310363619763878039
62184073572399794223406235393808339651327408011116
66627891981488087797941876876144230030984490851411
60661826293682836764744779239180335110989069790714
85786944089552990653640447425576083659976645795096
66024396409905389607120198219976047599490197230297
64913982680032973156037120041377903785566085089252
16730939319872750275468906903707539413042652315011
94809377245048795150954100921645863754710598436791
78639167021187492431995700641917969777599028300699
15368713711936614952811305876380278410754449733078
40789923115535562561142322423255033685442488917353
44889911501440648020369068063960672322193204149535
41503128880339536053299340368006977710650566631954
81234880673210146739058568557934581403627822703280
82616570773948327592232845941706525094512325230608
22918802058777319719839450180888072429661980811197
77158542502016545090413245809786882778948721859617
72107838435069186155435662884062257473692284509516
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690
"""
L = [int(s) for s in p.split("\n") if s]
print str(sum(L))[:10]

-----

"""
 トリプルクォーテーション("または'の連続3つ)で挟むと、複数行にわたる文字列を改行コードも含めて設定できます。
 左辺が無く"""で挟むだけならば、ただのコメント行として機能します。
 ここでは与えられた長大な文字列を変数pに設定しています。

・L = [int(s) for s in p.split("\n") if s]
 最初に、for文で長大文字列pを改行コードで分割します。

 次に、if文でその分割値に値が設定されていれば、for文の前に渡します。
 さらに、int関数で後ろから受け渡された値を数値型にします。
 pythonでは数字型に桁数制限が無く、50桁の数値100個をリストLに設定します。
・str(sum(L))[:10]
 sum関数でリストLの和を求め、str関数で文字型に変えて、[:10]で上10文字分を取り出します。

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


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

2012年5月13日日曜日

プロジェクトオイラー Problem12

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

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

Problem 12
三角数の数列は自然数の和で表わされ、 7番目の三角数は
 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28
である。
三角数の最初の10項は
 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
となる。
最初の7項について、その約数を列挙すると、以下のとおり。
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
これから、7番目の三角数である28は、6個以上の約数をもつ最初の三角数であることが分る。
では、501 個以上の約数をもつ最初の三角数はいくらか。


私の解答例は以下のとおりです。
-----
def f(n):
	m, t, L = 0, 0, []
	while len(L)<n:
		m, t, L = m+1, t+m+1, []
		for i in xrange(1, t+1):
			if t%i: continue
			elif t<i*i: break
			L += [j for j in [i, t/i] if j not in L]
	return t, m
	
a, b = f(501)
print a, ",", str(b)+"th triangle number."

-----

・関数f(n)は、n個以上の約数をもつ最初の三角数を返します。

・m, t, L = 0, 0, []
 初期設定です。pythonでは複数の変数にまとめて設定できます。


・while len(L)<n:
 約数リストLの要素数がn未満の場合だけ処理を続けます。


・m, t, L = m+1, t+m+1, []
 ループ内カウンターmは、何番目の三角数かという序数です。
 m番目の三角数は、mまでの自然数の和なので、
 次の三角数(m+1番目の三角数)は、現在の三角数tと次の序数m+1の和です。

 約数リストLはクリアしておきます。

・for i in xrange(1, t+1):
 三角数tの約数リストLを作成します。約数候補iの範囲は1からtまでです。

 xrange(from, to)の第2引数toは、その値になったら処理を抜ける値なのでtでも処理を回したい場合は、その1つ先のt+1とします。

・if t%i: continue
 %演算子は割り算の余りを返します。ここでは三角数tを約数候補iで割った余りです。論理式は0:False, 0以外:Trueなので、余りがある割り切れなかった場合はcontinueで次の約数候補へ進みます。


・elif t<i*i: break
 elifは「else if」の意味でさらにチェックを続けます。
 約数候補iが約数ということは、これで割った商t/iも約数です。
 約数候補iを小さいほうから順に算出していくと、そのときの商t/iは大きいほうから順に算出できることになります。
 なので約数候補iは、最大でも自乗して三角数t未満になる場合のみで十分で、ここに達すれば約数ループは終わりにします。


・L += [j for j in [i, t/i] if j not in L]
 最初に、for文で「約数i」と「約数iで割ったときの商t/i」を取得します。
 次に、if文で約数リストLに無い場合のみ対象にします。

 そして、for文の前へ渡して計算した値(ここでは渡された値jそのもの)を要素に持つリストにして、約数リストLに結合します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
76576500 , 12375th triangle number.


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

2012年5月10日木曜日

プロジェクトオイラー Problem11

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

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

Problem 11

20 × 20 の数字(※「私の解答例」に記載)のなか、
()でマークされた数字の積は 26 × 63 × 78 × 14 = 1788696 となる。
上下左右斜めのいずれかの方向で連続する4つの数字の積のうち最大のものを求めよ。

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

p = """
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10(26)38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95(63)94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17(78)78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35(14)00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
"""
def g(L): return reduce(lambda x, y:int(x)*int(y), L)
def f(p, n):
	L, a = [t.split() for t in p.split("\n") if t], 0
	for i in xrange(len(L)):
		for j in xrange(len(L[i])):
			M = [
			[L[i+k][j] for k in xrange(n) if i+k<len(L)],
			[L[i][j+k] for k in xrange(n) if j+k<len(L[i])], 
			[L[i+k][j+k] for k in xrange(n) if i+k<len(L) and j+k<len(L[i])],
			[L[i+k][j-k] for k in xrange(n) if i+k<len(L) and 0<=j-k]]
			for k, m in zip(["down","right","rightdown","leftdown"], M):
				if len(m)==n: r = g(m)
    else: r = 0 if a<r: a, b, c, d, e = r, i, j, k, m return a, b, c, d, e a, b, c, d, e = f(p, 4) print a, "=", " x ".join(e), "from", (b, c), "to the", d

-----

・"""
 トリプルクォーテーション("または'の連続3つ)で挟むと、複数行にわたる文字列を改行コードも含めて設定できます。
 左辺が無く"""で挟むだけならば、ただのコメント行として機能します。
 ここでは与えられた長大な文字列を変数pに設定しています。

以下、2つの関数を使っています。
1.関数g(L)
 リストLの要素をすべて掛け合わせた結果を返します。

・lambda x, y:int(x)*int(y)
 ラムダ関数という表記方法です。関数名は無く、無名関数とも呼びます。
 式の中に関数を直書き(じかがき)するような場合に使用します。
 書式は「lambda 引数:処理」で、引数を処理した結果を返します。
 ここでは、2つの引数x,yを受け取り、数値扱いにしてその積を返します。

・reduce(lambda x, y:int(x)*int(y), L)
 reduce文は指定した関数に累積的に引数を渡した結果を返します。
 書式は「reduce(関数, シーケンス)」で、関数にシーケンスの1つ1つの値を左から右に累積的に適用します。
ここでは「2つの引数の積」を返す関数にリストLの要素を累積的に適用します。

ここでの処理は具体的には以下のようになります。

 最初、L[0] x L[1]を求めます。
 次に、直前で求めた値 x L[2]を求めます。

 さらに直前で求めた値 x L[3]を求めます。

やっていることは以下と同じです。
(・・・((L[0]*L[1])*L[2])*L[3]・・・)
つまり、引数のシーケンスの要素すべての積です。

ラムダ関数を使わず、def文で定義する関数で書き換えると以下の通りです。
def h(x, y): return int(x)*int(y)
reduce(h, L)


ラムダ関数を使えば、書き換え例での「h」という関数名が不要というわけです。

2.関数f(p,n)
 縦横配列イメージの文字列pに対して、上下左右斜めのいずれかの方向で連続するn個の数字の積のうち最大のものを返します。
 ただし、文字列pは半角空白で区切られた数字を複数行もつ文字列です。

・L, a = [t.split() for t in p.split("\n") if t], 0
 変数の初期設定です。変数aに0を設定し、Lには以下のように設定します。
 「for t in p.split("\n")」にて、文字列pを改行コード(\n)で分割し順に変数tに設定していきます。
 次に「if t」にて、先ほどのtのうち、論理判定でTrue(0以外、カラ以外のオブジェクト)の場合に処理対象とします。
 そして「t.split()」にて、先ほどのtをsplit文の引数(未設定時は半角空白)によって分割したリストを作成し、これをLの要素とします。
 
 結果としてリストLは、pの「各行のリスト」を要素にもつリストになります。
 L=[["08", "02", ・・・,"08"], ["49", "49", ・・・,"00"], ・・・]

・for i in xrange(len(L)):
  for j in xrange(len(L[i])):

 二重ループです。iが行番号、jが列番号です。いずれも0からの連番です。
 ループ内ではL[i][j]が二次元配列の現在処理位置を表します。
 iの最大値は、len(L)、リストLの要素数、つまり行数です。
 jの最大値は、len(L[i])、i行目の要素数、つまりi行目の列数です。

・M = [
   [L[i+k][j] for k in xrange(n) if i+k<len(L)],
   [L[i][j+k] for k in xrange(n) if j+k<len(L[i])],
   [L[i+k][j+k] for k in xrange(n) if i+k<len(L) and j+k<len(L[i])],
   [L[i+k][j-k] for k in xrange(n) if i+k<len(L) and 0<=j-k]]
 リストMに、要素として計算候補を内包表記でリストとして4つ入れます。

 いずれも内包表記でループ変数kは0からn個分の整数です。

 1番目のリストはL[i+k][j]。
列固定でn行分なので、現在位置から縦にn個分の値です。

 2番目のリストはL[i][j+k]。
行固定でn列分なので、現在位置から横にn個分の値です。

 3番目のリストはL[i+k][j+k]。
行番号を+1で下方向、列番号も+1で右方向に同時にずらしながらn個分なので、右斜め下にn個分の値です。

 4番目のリストはL[i+k][j-k]。
行番号を+1で下方向、列番号を-1で左方向に同時にずらしながらn個分なので、左斜め下にn個分の値です。

これで、M=[[下方向], [右方向], [右斜め下], [左斜め下]]の値となります。
なお、内包表記末尾のif文で要素数の範囲内の場合だけ有効にしています。
縦横表からはみ出る分は取得しません。
このため、リストM内の各リストには値がn個より少ないものもあります。

・for k, m in zip(["down","right","rightdown","leftdown"], M):
 zip関数は指定した複数のシーケンスから同じインデックス位置にある要素を順に取り出します。
 ここでは、以下のように取り出してそれぞれ変数kと変数mに設定します。
 最初、"down", M[0]の要素(=下方向の値のリスト)
 次に、"right",M[1]の要素(=右方向の値のリスト)
 ・・・となります。
 なお、pythonでは大文字と小文字は区別するので、変数のmとMは別扱いです。

・if len(m)==n: r = g(m)
 else: r = 0
mは計算対象の値のリストで、rに計算結果を設定します。
要素数がn個ある場合は関数gで計算し、そうでない場合は対象外なので0とします。

・if a<r: a, b, c, d, e = r, i, j, k, m
 計算結果rがその保存値であるaを超える場合、新たな保存値aとして保存します。i,j,k,mは関連情報として、それぞれb,c,d,eに保存しておきます。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
70600674 = 89 x 94 x 97 x 87 from (12, 6) to the leftdown


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

2012年5月9日水曜日

プロジェクトオイラー Problem10

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

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

Problem 10
10以下の素数の和は2 + 3 + 5 + 7 = 17である.
200万以下の全ての素数の和を計算しなさい.


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

def f(n):
	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 sum(L)
	
print f(2000000)
-----

・関数f(n)はn以下の素数の和を返す関数です。

・L = [2]
 Lは素数リストです。初期値には最小の素数の2を設定します。

・for t in xrange(3, n+1, 2):
 3以上の奇数を素数候補tとします。tは3以上n+1未満の範囲で2とびの値です。

・for s in L:
 素数リストの要素を1つずつループ変数sに設定します。


if not t%s: break
 素数候補t ÷ 素数リストの要素s で割り切れるか判定します。
 %演算子は割り算の余りを計算します。
 if文では、0=False,それ以外=Trueなので、余りが無く割り切れる場合、素数sのループは終了させ次の素数候補tの値に進みます。

elif t<s*s: L.append(t); break
 elifは「else if」のことで、直前のif文でひっかからなかった場合にさらに追加して条件判定をする文です。
 素数候補tが何かの素数を因子に持つとすればその最大値はtの平方根です。
 例えば36は6x6なので6以下の数の積から成り立っています。(36=2x2x3x3)
 言い換えれば、割り算チェックで使っている素数sの平方(2乗)s*sがtを超えない、そのようなsで割ってチェックすればチェックは十分ということになります。
 そしてt<s*sが成り立つまでチェックが済めば、素数候補tは素数ですので、素数リストLに追加し、素数sのループは終了させ次の素数候補tの値に進みます。
 なお、「;」は複数の命令文を1行に書くときの連結子です。

もう少し判定条件を厳しくできれば処理時間が短縮できるはずです。

・return sum(L)
 こうして素数リストLにはn以下の素数が入ったので、sum関数で合計を計算しその値を返します。


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

142913828922


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

2012年5月5日土曜日

プロジェクトオイラー Problem9

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

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

Problem 9
ピタゴラスの三つ組(ピタゴラスの定理を満たす自然数)とはa<b<cで
a² + b² = c²
を満たす数の組である.

例えば, 3² + 4² = 9 + 16 = 25 = 5²である.
a + b + c = 1000となるピタゴラスの三つ組が一つだけ存在する.このa,b,cの積を計算しなさい.

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

def f(n):
	for a in xrange(1, n//3):
		for b in xrange(a+1, (n-a)//2):
			c = n-a-b
			if (b<c) and (a**2 + b**2 == c**2):
				yield a, b, c

for a, b, c in f(1000):
		print a*b*c, ":", str(a)+"x"+str(b)+"x"+str(c)
-----

・f(n)は、和がnであるピタゴラスの3つの数を返す関数です。
 求める値はこの戻り値の3つの数の積です。

・ループ変数a
 a<b<cかつa+b+c=nなので、aは最大でもn/3です。
 これを超えるとa,b,cの和がnを超えてしまいます。
 なお、「//」は切り捨て除算といって、整数までしか計算しない割り算の商です。今までの問題で「/」を使っていた部分は、この「//」演算子に取り替えても動作します。動作速度は、途中で計算をやめてしまう「//」演算子の方が速いです。

・ループ変数b
 a<b<cかつa+b+c=nかつaの値が決まってしまった後なので、bとcの和がn-aになり、bは最大でも(n-a)/2です。
 これを超えるとbとcの和が(n-a)を超えてしまいます。
 また最小候補値はa<bより、a+1 です。

・変数c = n-a-b
 a<b<cかつa+b+c=nかつ外側のループでa,bの値が決まってしまった後なので、cは一意に決まります。

・if (b<c) and (a**2 + b**2 == c**2):
 判定条件です。
 a<b<cの条件について、a<bはループ変数bの初期値で規定したので、b<cを入れておきます。あとはピタゴラス数の定義式そのものです。

・yield a, b, c
 pythonには関数の戻り値を返す命令語が2つあります。returnとyieldです。
 return文は戻り値を1度返したら終わりで、関数中の変数はクリアされます。
 yield文は戻り値を返すときに処理状況を一旦凍結しておいて、再度呼び出されたときに処理を再開して次の値を返し続けます。

 問題文では「答えは一つだけ存在する」とありますが、念のため、答えが複数あるときに備えてyield文で返しています。

・for a, b, c in f(1000):
 関数fの呼び出しは、yield文での返しに合わせ、for文の繰り返し元として呼び出しています。


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

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

2012年5月4日金曜日

プロジェクトオイラー Problem8

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

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

Problem 8
以下の1000桁の数字から5つの連続する数字を取り出して その積を計算する。
そのような積の中で最大のものの値はいくらか。

例)6桁の数123789なら、1*2*3*7*8と2*3*7*8*9の二通りとなり、後者の2*3*7*8*9=3024が最大の積となる。

(問題の数字は以下の変数p)


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

p = \
"""
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
"""
def g(x, y): return x*y
def f(p, n):
 L, t = [int(i) for i in list(p) if "0"<=i<="9"], 1
 for i in xrange(len(L)-n+1):
  s = reduce(g, L[i:i+n])
  if s>t: t, v = s, i
 return t, v+1, L[v:v+n]

s = f(p, 5)
print s[0], ":", s[1], "番目からの", s[2], "の積"
-----
p = \
 バックスラッシュ(または円マーク)は継続行を示します。複数行を1行として扱いたい場合の行末に付けます。

・"""
 トリプルクォーテーション("または'の連続3つ )で挟むと、複数行にわたる文字列を改行コードも含めて設定できます。
 ここでは与えられた長大な文字列を変数pに設定しています。
 左辺が無い、"""~"""で挟むだけならば、ただのコメント行として機能します。

以下、2つの関数を使っています。
1.2つの数の積 g(x, y)
 2つの引数の積を返します。

2.文字列pに含まれる連続するn個の数字の積の最大値 f(p, n)
・L, t = ・・・
 文字列pを1字ずつ数字型で要素に持つリストLと、求める最大値tを初期化します。

・[int(i) for i in list(p) if "0"<=i<="9"]
 文字列pをlist関数で1文字ずつのリストにします。
 次に、for文で変数iに1つずつ取り出します。まだ改行文字も含まれています。
 そして、if文で変数iが"0"~"9"の場合だけ取り出し数字だけにします。
 最後に、こうして取り出した変数iをint関数で数値型に型変換します。

 p="731・・・" → L=[7, 3, 1, ・・・] となります。

 リストの内包表記での処理順は、
 中程のfor文 > 末尾のif文 > 先頭の配列値 です。
 上記の内包表記例では、if文で判定するのは、for文で取り出した直後でまだint関数が効いていない文字型なので、
 「if 0<=i<=9」ではなく「if "0"<=i<="9"」と判定します。

・for i in xrange(len(L)-n+1):
 変数iはn個掛け算するうちの最初の値です。
 n個の数字が取れるのは、最初から「最後からn-1番目まで」です。
 それより後ろはn個未満しか残っていないので対象外です。

・s = reduce(g, L[i:i+n])
 reduce関数は、reduce(関数名, シーケンス)として、関数にシーケンスの1つ1つの値を左から右に累積的に適用します。


 関数g(x, y)は引数を2つ受け取ってその積を返します。
 リストL[i:i+n]は、リストLのi番目からn個分の要素です。
 つまりここでの処理は以下のようになります。

 最初、関数gにL[i]とL[i+1]を渡し、その積を求めます。
 次に、関数gに先ほど求めた値とL[i+2]を渡し、その積を求めます。
 さらに関数gに先ほど求めた値とL[i+3]を渡し、その積を求めます。

 やっていることは以下を要素n個分続けることと同じです。
 (・・・((L[i]*L[i+1])*L[i+2])*L[i+3]・・・)

 for文を使って以下のように書くこともできます。
 s = L[i]
 for j in xrange(1, n):
  s *= L[i+j]


 なお、reduce関数はpython3ではfunctoolsに外出しされ、使用する行より前にimportしておく必要があります。
from functools import reduce

・if s>t: t, v = s, i
 reduce関数での計算値sが、いままでの最大値tよりも大きい場合、
 計算値sとそのときの開始位置iを、それぞれtとvとして保存しておきます。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
40824 : 365 番目からの [9, 9, 8, 7, 9] の積


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

2012年5月3日木曜日

プロジェクトオイラー Problem7

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

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

Problem 7
素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり、6番目の素数は 13 である。10001 番目の素数を求めよ。

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

def f(n):
	t, L = 2, [2]
	while len(L)<n:
		t += (t%2)+1
		for s in L:
			if not t%s: break
		else:
			L.append(t)
	return L[-1]
	
print f(10001)
-----

素数候補を「2と、3以上の奇数」として、リストに貯めた素数で割り切れるかチェックして、全ての素数で割り切れなければ素数としてリストに追加し、n個貯まるまで続けます。

・L, t = [2], 2
 初期値として、素数候補tに2、素数リストに要素2を設定します。


・while len(L)<n:
 素数リストの要素数がn未満なら素数を探し続け、n個取得して終了します。


・t += (t%2)+1
 素数候補tは、処理を簡単にするため「2と、3以上の奇数」とします。
演算子%は割り算の余りです。
 t=2のとき、0+1累積して、次のtは3、
 t=3のとき、1+1累積して、次のtは5、以降、7,9,・・・となります。

・for s in L: ~ else:
 素数リストの最初から1つずつ要素を取り出して変数sにセットします。
 forループを途中で抜けずに最後まで回った場合のみ、else節を行います。

・if not t%s: break
 素数判定です。
 素数候補を素数で割った余りがFalse(余り=0、割り切れる)の場合、for文を抜けます。このような途中抜けの場合はelse節は行いません。
 全部の素数で割り切れなかった場合、else節で素数リストに素数候補を追加します。
 なお、素数候補の半分の値よりも大きな数では、割り切れるわけがないので判定そのものが不要なのですが、このためにif文を1つ追加すると却って処理時間がかかったので、ここでは素数リストにある全部の素数をループで回しています。

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


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

2012年5月1日火曜日

プロジェクトオイラー Problem6

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

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

Problem 6
最初の10個の自然数について、その和の二乗と、二乗数の和は以下の通り。
  1² + 2² + ... + 10² = 385
  (1 + 2 + ... + 10)² = 3025
これらの数の差は 3025 - 385 = 2640 となる。
同様にして、最初の100個の自然数について和の二乗と二乗の和の差を求めよ。


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

#和の二乗
def p(n): return sum([i for i in xrange(1, n+1)])**2

#二乗の和
def q(n): return sum([i**2 for i in xrange(1, n+1)])

n=100
print p(n)-q(n), "( =", p(n), "-", q(n),")"
-----

1.和の二乗 p(n)
・[i for i in xrange(1, n+1)]

 「リストの内包表記」という表現方法です。
 xrange関数の部分は、1,2,・・・,n を順に返します。(イテレータオブジェクト)
 このイテレータから返される値が、for文の変数iとしてセットされ、
 forの前の変数iを要素として持つリストを表します。
 この部分の全体の意味は、[1,2,・・・,n]と同じです。
・sum(L)**2
 リストLの合計を取得し二乗します。
 これで上記とを合わせて (1 + 2 + ... + n)² を計算します。
 
2.二乗の和 q(n)
・[i**2 for i in xrange(1, n+1)]
 先ほどの説明とほぼ同じです。forの前を「i**2」とすることで、for文で取り出した変数iの二乗を要素として持つリストを表しています。

3.和の二乗と二乗の和の差
 print文の「p(n)-q(n)」が求める値です。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
25164150 ( = 25502500 - 338350 )


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