Euler : Problem 51

Posted by YpsilonTAKAI On 2011年7月3日日曜日 0 コメント
素数のうち、表われる全ての同じ数字をいれかえてできる組を作ったとき、8つ素数の組ができるものを探す問題。

* 8つの組ができるということは、置き換えるところに 10個の数字(0123456789)のうちの
  8つを入れることができなければならない。

このことから、

- 1の位は入れ替え対象にならない。
  <== 10個のなかに偶数が5つありすべて取り除くことができない。
      1の位が偶数のとき2以外は素数ではない。

- 入れ替える数は1つではない。
  <== 10個の数字には3を法とすると0,1.2になるものがそれぞれ3つ以上あるため、
      2つを取り除いても、かならず0,1.2になるものが含まれる。
      また、対象の数を構成する残りの各桁の数の和は、3を法とすると0,1.2のいずれかになる。
      結局、数字を入れかえてできる数のなかには、各桁の数の和が3を法とすると0になるものが
      必ずできてしまうことになる。
      ある数の各桁の数の和が3を法として0の場合その数は3で割り切れるので、素数ではない。

- 入れ替える数は2つではない。
  <== 2つを同じ数に入れ替える場合、入れ替えた数字の合計は、 0->0, 1->2, 2->4... であり、
      それぞれ3を法とすると、 0,2,1,0,2,1... となり、0,1.2になるものがそれぞれ3つ以上ある。
      以下、1つの場合と同様の理由で、素数でなくなるものが出てしまう。

- 3つの数を入れ替えることは可能、
  <== 3つの数字の合計は3を法とするとすべて0であるため、もとが素数であればどの数字に入れ替えても、
      3の倍数にはならない。

- 4つは1つ、5つは2つのときと同様の理由でできない。 6つは可能である。
  ところが、4つ以上入れ替えてできる数列は3つの入れ替えとも考えられるので、3つ入れ替えたものより
  前に4つ以上入れ替えたものが現れることはない。

ということで、同じ数字が1の位以外の場所に3つある素数だけが調査対象になる。

3つに限定することで、ロジックを簡単にすることができるが、次のような問題がある。それぞれ検討した結果問題ないと考えた。
- 初めにみつかったものが組の中で最小でない可能性がある。
  全ての数列を作って最小のものを取ることにすれば回避できる。
- 12桁以上の数であった場合、どの数も4こ以上の同じ数字を含んでいるかもしれず、ひっかからない可能性がある。
  それより小さな数であることを期待する。(というか、そんなにでかい素数は扱えない)

1つだけ出そうとしたら、出た答えの最上位から幾つかが0になるものだった。問題文ではこのような場合の扱いが明確でないので、計算しなおしになった。

手順は、
- 4桁以上の素数の列に、どの数字が何回出てくるかという情報をくっつける。
- 同じ数を3つだけ含むものを抽出する。
- 3つある数字を0~9の数字に置き換えて、それぞれ素数かどうか判定する。
- 8つ以上が素数になるものを抽出。


;;
;; Problem 51 : 2011/6/15
;; "Elapsed time: 2729.218378 msecs"

(def tgt-prime (drop-while #(< % 1000) (prime-nums-under 1000000)))

(defn replace-digits [num digit]
(for [rep (range 0 10)]
(list-to-num (map #(if (= % digit) rep %) (num-to-list num)))))

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

(defn num-to-list [num]
(map #(Character/digit % 10) (str num)))

(defn group-same
"Split into same value group
ex. (2 3 1 3 1 3 3) -> [(1 1) (2) (3 3 3 3)]"
([col] (group-same (sort col) []))
([col res]
(if (empty? col)
res
(let [[head tail] (split-with #(= (first col) %) col)]
(recur tail (conj res head ))))))

;;; original
(filter (fn [[digit-of-three num]]
(> (count (filter is-prime?
(replace-digits num digit-of-three))) 7))
(map (fn [[count-list num]]
[(last (first count-list)) num])
(filter (fn [[tst _]] (some #(= 3 (first %)) tst))
(map (fn [prime]
(list (map #(list (count %) (first %))
(group-same (butlast
(num-to-list prime))))
prime))
tgt-prime))))
;;



なんかごたごたしててわかりにくいので、「->>」まくろを使ったバージョンを書いてみた。
見やすいけど、lispっぽくないね。


;;
;; macro version
(take 1
(->> tgt-prime
(map (fn [prime]
(list (map #(list (count %) (first %))
(group-same (butlast (num-to-list prime))))
prime)), )

(filter (fn [[tst _]] (some #(= 3 (first %)) tst)), )

(map (fn [[count-list num]]
[(last (first count-list)) num]), )

(filter (fn [[digit-of-three num]]
(< 7 (count
(filter is-prime?
(replace-digits num digit-of-three))))), )))
;;

0 コメント:

コメントを投稿