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 . (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 = 
main = print.p136 $ 50*10^6

遅いです。

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