Ir para o conteúdo

Primalidade dos números 2n^2-1 (Euler, 216)

Nota: Considere os números \(t(n)\) da forma \(t(n)=2n^2-1\) onde \(n>1\). Os primeiros números do género são 7, 17, 31, 49, 71, 97, 127 e 161. Constata-se que apenas \(49=7*7\) e \(161=7*23\) não são primos. Para \(n\leq10000\) existem 2202 números \(t(n)\) que são primos.

Quantos números \(t(n)\) são primos para \(n\leq50~000~000\)?

in Project Euler, problem 216

isPrime n = all (/= 0) . map (n `mod`) $ [2..squareRoot n]
  where
    squareRoot = truncate . sqrt . fromIntegral

list = map (subtract 1 . (*2) . (^2)) [2..]  -- 2n^2-1

main = do
  putStrLn . show $ solveit 10000     -- caso de controlo
  putStrLn . show $ solveit 50000000  -- caso em estudo
    where
      solveit n = length . filter isPrime $ take (n-1) list

Colocando a fórmula numa função à parte:

-- isPrime...

list = map t [2..]
t = subtract 1 . (*2) . (^2)  -- t(n) = 2n^2-1

main = do
  -- output...
    where
      solveit n = length . filter isPrime $ takeWhile (<= (t n)) list