Euler : Problem 41

Posted by YpsilonTAKAI On 2011年6月29日水曜日 0 コメント
最大のパンデジタルな素数を求める問題。
ここでのパンデジタルな数というのは、1からnまでの全ての数を使った数ということなので、最大でも9桁(1から9)ということになります。

また、1から9まで全部足すと45になるので、9桁のパンデジタルな数は必ず3の倍数になっちゃいます。計算すると、3の倍数にならないのは、7桁と4桁(と1桁だけど、1は素数じゃない)だけ。


あとは、7桁以下の素数の大きなほうから順にパンデジタルかどうか確認していけばいいのでしょうけど、あえて、パンデジタルな数を作って素数かどうか判定する方式にした。
最初のコードは、あえてした割にはエレガントじゃないコードになっちゃった。

select-numsとnum-listx関数で、1からxまでの数の順列を作ろうとしてるんだけど、一般化できなかった。 マクロしかないような気がするけど、どうなんだろうと思って調べたら、contrib.combinatorics にあるみたい。permutations。
これを使ったら簡単だね。
短かいけど、そんなに速さは変らない。


;;
;; Problem 41 : 2011/6/9
;; "Elapsed time: 5.017956 msecs"

(use 'clojure.contrib.combinatorics)

(take 1
(flatten
(for [n [7 4]]
(filter is-prime? (map list-to-num
(permutations (range n 0 -1)))))))
;;



初めにつくったのがこれ。

select-numsは、[col digit-list]を受けとって、colで指定された順にdigit-listの数字を取っていく関数。

(select-nums [0 0 0 0] [1 2 3 4]) -> [1 2 3 4]
(select-nums [3 2 1 0] [1 2 3 4]) -> [4 3 2 1]
(select-nums [1 1 1 0] [1 2 3 4]) -> [2 3 4 1]


;;
;; Problem 41 : 2011/6/9
;;"Elapsed time: 5.947124 msecs"

(use 'clojure.contrib.math)

(defn select-nums
([col] (select-nums col [1 2 3 4 5 6 7 8 9]))
([col digit-list]
(loop [num-list digit-list
coll col
res-list []]
(if (empty? coll)
res-list
(let [tgt-num (nth num-list (first coll))]
(recur (vec (remove #(= % tgt-num) num-list))
(rest coll)
(conj res-list tgt-num )))))))

(defn num-list7 []
(for [a3 (range 7) a4 (range 6)
a5 (range 5) a6 (range 4) a7 (range 3) a8 (range 2)]
(select-nums [a3 a4 a5 a6 a7 a8 0] [7 6 5 4 3 2 1])))

(defn list-to-num [digit-list]
(apply + (map #(* %1 (expt 10 %2))
(reverse digit-list) (iterate inc 0))))

(time (doall (take 1 (filter is-prime?
(map list-to-num (num-list7))))))

;;

0 コメント:

コメントを投稿