Hatena::Grouphaskell

Haskellで遊ぶよ

 | 

2009-06-24

「すべての奇数の合成数は、1つの整数の自乗の2倍と1つの素数の和で表される」?

10:51

Goldbach が考えた命題の反例を上げる問題。(一般に Goldbach 予想と呼ばれているものではない)


合成数というのは、9,15,21,25のように、2つ以上の素数の積となるもの。

例えば9は、

9 = 7 + 2 * 1^2

となり、「1つの整数の自乗の2倍と1つの素数の和」である。

この反例を見つける Haskell プログラム。

primes :: [Integer]
primes = sieve [2..]
    where
        sieve (x:xs) = x : (sieve [y| y <- xs, y `mod` x /= 0])

oddCompos :: [Integer]
oddCompos = filter isCompos [3,5..]
    where
        isCompos x = not.null $ [n| n <- [3,5..floor(sqrt(fromIntegral(x))) ], x `mod` n == 0]

main = print $ head $ filter isNotGoldbach oddCompos
    where
        isNotGoldbach x = all (/=x) [n*n*2+p | n <- takeWhile (\n->n*n*2<x) [1..], p <- takeWhile (\p->n*n*2+p<=x) primes]

結果。

5777

最後のリスト内包表記で、n*n*2 を3回もやっているのがなんとかならないかなー。リストの内包表記は、その中に出てくる値の状態を保持できないのがたまにキズ。なんと、let が使えたらしい。

また、一番最後の primes というところで、毎回最初から素数を求めてるんじゃないかと思ったけど、これは trace してみたところ、ちゃんと必要なところだけ計算しているみたいだった。(各 x に対して最初からやり直しているような書き方だけど、hugs でも最適化されている)

rst76rst762009/06/24 22:05関数 isNotGoldbach の中で n に対して p は一意に定まるので let で書けます。
これを直せばインタプリタでも十分速いはず。
n*n*2 の計算も一応まとめると、↓のようになるかと。
isNotGoldbach x = all (/=x) [n2+p | n2 <- takeWhile (<x) $ map (\n->n*n*2) [1..], let p = head $ dropWhile (<x-n2) primes]

edvakfedvakf2009/06/24 23:58そんなところで let が使えたのですね!! 便利です。
おっしゃる通り、かなり速くなりました。ありがとうございます。

トラックバック - http://haskell.g.hatena.ne.jp/edvakf/20090624
 |