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

プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索してください。

問６３　「n 乗して得られる n 桁の正整数は何個あるか?」
5桁の数 16807 = 75は自然数を5乗した数である.
同様に9桁の数 134217728 = 89も自然数を9乗した数である.

自然数をn乗して得られるn桁の正整数は何個あるか?
－－－－－

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






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

def f():
	import math
	return [(a,b,a**b) for a in xrange(1,10) for b in xrange(1, int(1/(1-math.log(a, 10)))+1)]

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

自然数aをb乗してb桁の正整数ということは、桁数の区切りは10の累乗値なので以下の式が成り立ちます。
0 ≦ 10(b-1) ≦ ab ＜ 10b ・・・(A)
a>1、b>1 ・・・(B)

まず、aの変域を求めます。(A)の右部分の２式より、
1 ≦ a ＜ 10 ・・・(C)

次にbの変域を求めます。
(A)の左部分をbについて解きます。
まず、左部分の２式の対数をとって、
(b-1)*log10 ≦ b*(log a)

次にbを左辺に寄せて、
(b-1)/b ≦ (log a)/log10

対数の底を10にして、
1-(1/b) ≦ log10a

1-log10a ≦ 1/b

b ≦ 1/(1-log10a)

(B)よりb>0なので、bの変域は
1 ≦ b ≦ 1/(1-log10a) ・・・(D)

上記(C)(D)の範囲で二重ループさせます。

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

１．関数f()
・import math
　数学用関数モジュールmathをインポートして使えるようにしておきます。

・return [(a,b,a**b) for a in xrange(1,10) for b in xrange(1, int(1/(1-math.log(a, 10)))+1)]
　内包表記内に二重ループを入れています。
　まず前の「for a in xrange(1,10)」で、aが1以上10未満の整数でループします。
　そしてループ変数aを後ろのfor文へ渡します。
　後ろの「for b in xrange(1, int(1/(1-math.log(a, 10)))+1)」で、
　bが1以上1/(1-math.log10a)未満の整数でループします。
　math.log()関数は対数関数です。第２引数は対数の底です。
　int関数で切り捨てて整数にします。
　このa,bの値を先頭の式、(a,b,a**b)に渡します。
　これは問題に合うa, b, aのb乗の値のタプルです。
　このタプルを内包表記でリストにため、そのまま呼び出し元に返します。

２．関数の外
・L = f()
　print len(L),L
　関数f()で問題に合うa, b, aのb乗のタプルを格納したリストを取得しLとします。
　求める個数、とそのリストを表示します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
49
（追記）
・20130127　ネタバレ注意の追記など