to site top page

Problem 24 - Project Euler

# Python3 fileencoding: utf-8
import math
import time

chars = list("0123456789")
quantity = len(chars)
order = 10 ** 6 - 1
ans = ""

st = time.time()
for num in [math.factorial(i) for i in range(quantity - 1, -1, -1)]:
    ans += chars.pop(order // num)
    order %= num

print("answer : {0}, {1}sec.".format(ans, time.time() - st))

安易に考えるのであれば,0123456789から9876543210を整列して1000000番目を取り出せばいいんですが,それだと多少の無駄が出てきてしまいます.なので,まず手作業での解き方を考えます(この手の問題は高校数学で出てきます).以下,2718282番目(7432518960)を例に取ります.

2718282番目は何か

先頭を固定して考えると,残りの9桁の並べ方が 9! = 362880 通りあります.2718282を362880で割ると約7.5,つまり,辞書順で8番目の数 = 7で始まる事になるわけです.

2718282 - 7 * 362880 = 178122 で,これを 8! = 40320 で割ると約4.4,なので2番目の数は辞書順で5番目の数 = 4,178122 - 4 * 40320 = 16842,16842を 7! = 5040 で割ると3.3,3番目の数は辞書順で4番目の数 = 3,16842 - 3 * 7! = 1722,……,これを 0! = 1 まで繰り返すと,7432519068が出てきます.

ずれてますね.欲しいものは7432518960なんですが,7432519068が出てきました.こいつなんなのかっていうと,7432518960の次のもの.0123456789ってのが何番目になるのか考えてみますと,実は0番目になります.なので,n番目を求めたい場合, n - 1 に対して上記の手順を施してやらねばなりません.2718281に対して上記手順を施してやると,以下のようになります.

2718281 = 7 * 9! + 178121
 178121 = 4 * 8! +  16841
  16841 = 3 * 7! +   1721
   1721 = 2 * 6! +    281
    281 = 2 * 5! +     41
     41 = 1 * 4! +     17
     17 = 2 * 3! +      5
      5 = 2 * 2! +      1
      1 = 1 * 1! +      0
      0 = 0 * 0!

以上から,0123456789の文字からそれぞれ7番目,4番目,3番目,2番目,2番目,1番目,2番目,2番目,1番目,0番目(0番~9番)と取り去っていけば,7432518960が出来ます.

以上の操作をプログラムにやらせたのが,冒頭のPython Scriptになります.0123456789から9876543210の3628800個すべて生成して1000000番目指定するよりは速いです.

ついでに:7432518960が何番目に当たるか

上記とやってる事ほぼ同じですが.辞書式なので頭から見ていきます.

先頭の数が7なので,0~6で始まるものは(当然)7432518960よりも前に並んでいます.先頭を固定して考えると残りの9桁の並べ方が 9! = 362880 通りあるので,7432518960よりも前に並んでいる数は 7 * 9! = 2540160 個あることになります.なので,7で始まるものは 2540160 + 1 番以降に並べられる事になります.

同様にして,70~73で始まるものは7432518960よりも前に並んでおり,後ろ8桁の並べ方が 8! = 40320 通り,よって7432518960は“0~6で始まるもの” + “70~73で始まるもの” + 1番以降に並べられるわけで,以下も同様に考えて行けば良い,と.

同様に考えて行けばいいのですが,5ステップ目,74325まで見た時ですが,この段階で既に2~4が使われているので,74325xxxxxの前にあるものは74320xxxxxと74321xxxxxの二種類.なので74325xxxxxの前にあるものは 2 * 5! = 240 だけ増える事になります.

上記を考慮しつつ計算すると, 7 * 9! + 4 * 8! + 3 * 7! + 2 * 6! + 2 * 5! + 1 * 4! + 2 * 3! + 2 * 2! + 1 * 1! = 2,718,281 ,この数が743251890xまでの数で,7432518960はその次の数なので,1足して2,718,282番目,となります.

can't load my result

最近の記事(5件分)

する事

そのうち記事にするかもリスト

欲しい本