Problem 136

http://projecteuler.net/index.php?section=problems&id=136

とりあえず、100まで調べて
奇素数nに対して、nに対する解が唯一 iff n=3 (mod 4)
奇素数nに対して、4nに対する解は唯一
奇素数nに対して、16nに対する解は唯一
まで分かった。
他の合成数に対してはよく分からないが解は唯一にならないみたい。
ということで、多分正しいのだろうという推測のもと

import Number
import Data.List

p136 lim = foldl' count 0. (1:). takeWhile(<lim). tail $ primes
    where count c n | mod n 4 == 3  = c + 1 + t (4*n) +  t (16*n)
                    | otherwise = c + t (4*n) + t (16*n)
          t x | x < lim = 1
              | otherwise = 0

main = print.p136 $ 50*10^6

遅いです。

フォーラムに証明が載っていたが、もう少しきれいに証明できそうなんだが。できない。