Euler : Problem 52

Posted by YpsilonTAKAI On 2011年7月3日日曜日 0 コメント
1から6までの数を掛けてできる数が同じ数字で構成されている数字を見つける問題。

-6を掛けても桁数が変らないということは、たとえば、3桁なら166まで、
  6桁なら16666までということになる
-最上位が1なので、1から6倍した場合、最上位の数は全て異なる数になるので、
  桁数は6以上のはず。

あとは全数チェック。

答を見て、「あー。なんだよ。これかよ」と思った。 ちょっとくやしい。


;;
;; Problem 52 : 2011/6/15
;; "Elapsed time: 3178.80848 msecs"

(defn same-digits? [n m]
(= (sort (num-to-list n))
(sort (num-to-list m))))

(defn pe52-end-num [digit]
(+ (expt 10 digit)
(list-to-num (repeat digit 6))))

(take 1
(drop-while empty?
(for [digits (iterate inc 5)]
(filter #(and (same-digits? % (* 2 %))
(same-digits? % (* 3 %))
(same-digits? % (* 4 %))
(same-digits? % (* 5 %))
(same-digits? % (* 6 %)))
(range (+ (expt 10 digits) 2) (inc (pe52-end-num digits)))))))
;;
READ MORE

Euler : Problem 51

Posted by YpsilonTAKAI On 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))))), )))
;;
READ MORE

Euler : Problem 50

Posted by YpsilonTAKAI On 2011年6月29日水曜日 0 コメント
100万以下の素数で、もっとも大くの連続する素数の和で表わされるものを求める問題。

そのまま解いた。
素数のリストについて、初めから順に足していって、結果が素数になるかどうか都度判定する。
素数でなくなったら、素数のリストの先頭をとりのぞいてまた同様のことをする。
素数でなくなったときの情報を、前の結果と比べて結果を更新する。

時間かかりすぎ。



;;
;; Problem 50 : 2011/6/14
;; "Elapsed time: 276190.732342 msecs"

(defn longest-seq [coll max-val]
(loop [forward-coll []
rest-coll coll
max-seq []]
(if (empty? rest-coll)
max-seq
(let [next-foward (conj forward-coll (first rest-coll))
sum-of-coll (reduce + next-foward)]
(cond (> sum-of-coll max-val) max-seq
(is-prime? sum-of-coll)
(recur next-foward (rest rest-coll) next-foward)
:else
(recur next-foward (rest rest-coll) max-seq ))))))


(loop [primes (prime-nums-under 1000000)
max-count 0
res-seq []]
(if (< (count primes) max-count)
res-seq
(let [new-long-coll (longest-seq primes 1000000)
new-count (count new-long-coll)]
(if (< new-count max-count)
(recur (rest primes) max-count res-seq)
(recur (rest primes) new-count new-long-coll)))))
;;
READ MORE

Euler : Problem 49

Posted by YpsilonTAKAI On 0 コメント
同じ間隔で並んでいる3つの4桁の素数で、同じ数字で構成されているものを求める問題。

まず、4桁の素数を全てについて、構成する数字をキーにしたmapに入れる。同じ数字で構成されているものは同じキーに関連付けられる。
([1 4 8 7] , (1487 4817 8147))
のような感じ。

そして、その中の3つ以上の数が入っているものについて、等間隔にならんだ3数があれば取り出す。



;;
;; Problem 49 : 2011/6/14
;; "Elapsed time: 93.160443 msecs"

(defn seq-of-3 [coll]
(for [a coll b coll c coll :when (= (- (* b 2) a) c)
:when (< a b)
:when (< b c)]
[a b c]))


(let [four-digit-primes (drop-while #(< % 1000) (prime-nums-under 10000))
*digits-map* (atom {})]

(dorun
(map (fn [n]
(let [key (sort (num-to-list n))]
(swap! *digits-map* assoc key (cons n (@*digits-map* key)))))
four-digit-primes))

(mapcat seq-of-3
(for [key (keys @*digits-map*) :when (>= (count (@*digits-map* key)) 3)]
(sort (@*digits-map* key))))
)
;;
READ MORE

Euler : Problem 48

Posted by YpsilonTAKAI On 0 コメント
1から1000までの数nについてnのn乗の和を求める問題。

そのまま解いただけ。
最後の10桁だけ求めればいいので、足す前に11桁め以上を消してます。



;;
;; Problem 48 : 2011/6/13
;; "Elapsed time: 217.941386 msecs"

(reduce + (map #(rem (expt % %) 10000000000)(range 1 1001)))
;;
READ MORE

Euler : Problem 47

Posted by YpsilonTAKAI On 0 コメント
4つの連続駿数で、全てが4種類の素数に因数分解できるようなものをみつける問題。

1から順に全ての数を素因数分解して出てくる数字の種類を数え、もとの数とのペアにしたデータを作る。
あたまから順に4つずつ取って、全部の数字の種類が4になった最初のものが答え。

factorsは前に作った、素因数分解したものをリストで返す関数。

時間かかりすぎ。


;;
;; Problem 47 : 2011/6/13
;; "Elapsed time: 162902.866705 msecs"

(take 1
(filter
(fn [coll] (every? #(= 4 (first %)) coll))
(partition 4 1
(map #(vector (count (distinct (factors %))) %)
(range 1 1000000)))))
;;
READ MORE

Euler : Problem 46

Posted by YpsilonTAKAI On 0 コメント
奇数の合成数のうち、「素数と、何かの2乗の2倍の和」で表わされない最小の数を求める問題。

なんか、全然エレガントじゃないけど、素数じゃない奇数について、その数以下の素数を引いた残りが平方数になっているかどうか判定した。


;;
;; Problem 46 : 2011/6/13
;; "Elapsed time: 841.523433 msecs"

(defn square? [n]
(= (sqrt n) (int (sqrt n))))

(defn not-prime-plus-double-sq [n]
(every? false?
(map (fn [pnum]
(let [tstval (- n pnum)]
(and (even? tstval)
(square? (/ tstval 2 )))))
(prime-nums-under n))))

(take 1 (filter not-prime-plus-double-sq
(filter (complement is-prime?) (range 1 1000000 2))))
;;
READ MORE