Y箱

素数のうち、表われる全ての同じ数字をいれかえてできる組を作ったとき、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))))), )))
;;