Anonymous user
Chowla numbers: Difference between revisions
m
→{{header|Haskell}}
(→{{header|Wren}}: Library name change.) |
|||
Line 1,517:
=={{header|Haskell}}==
Uses arithmoi Library: https://hackage.haskell.org/package/arithmoi-0.11.0.0
===Single Threaded===
<lang haskell>{-# LANGUAGE NumericUnderscores #-}
import Math.NumberTheory.Primes (factorise, unPrime, Prime)
Line 1,555 ⟶ 1,556:
main = do
mapM_ (uncurry (printf "chowla(%2d) = %d\n")) $ chowlas [1..37]
mapM_ (uncurry (printf "There are %8s primes < %10s\n")) $
chowlaPrimes [100, 1_000, 10_000, 100_000, 1_000_000, 10_000_000]
mapM_ (printf "%10s is a perfect number.\n")
printf "There are %2d perfect numbers < 35,000,000\n" $ length
where
chowlas = map ((,) <$> id <*> chowla)
Line 1,613 ⟶ 1,614:
33,550,336 is a perfect number.
There are 5 perfect numbers < 35,000,000
</pre>
===Using dataflow parallelism===
compiled with "-O2 -threaded -rtsopts"<br/>
ran with "chowla +RTS -N6"
<lang haskell>import Math.NumberTheory.Primes (factorise, unPrime, Prime)
import Text.Printf (printf)
import Data.List.Split (chunksOf)
import Data.List (intercalate, mapAccumL)
import Data.Bifunctor (bimap)
import Control.Monad.Par (runPar, get, spawnP)
import Control.Monad (join)
chowla :: Word -> Word
chowla 1 = 0
chowla n = f n
where
f = (-) =<< pred . sumFactors . factorise
sumFactors = product . map fl
where
fl (n, count) = foldr (\p s -> s + unPrime n ^ p) 1 [1 .. count]
chowlaPrime :: Word -> Bool
chowlaPrime 1 = False
chowlaPrime n = chowla n == 0
chowlaPerfectNum :: Word -> Bool
chowlaPerfectNum 1 = False
chowlaPerfectNum n = chowla n == pred n
chowlaPrimes :: (Word, Word) -> (Word, Word)
chowlaPrimes (min, max) = (count, max)
where
chunkSize = (max - min) `div` 10
chunks = chunksOf (fromIntegral chunkSize) [min..max]
countChunk = foldr (\n count -> if chowlaPrime n then succ count else count) 0
count = runPar $ do
pars <- mapM (spawnP . countChunk) chunks
result <- mapM get pars
pure $ sum result
commas :: (Show a, Integral a) => a -> String
commas = reverse . intercalate "," . chunksOf 3 . reverse . show
main :: IO ()
main = do
mapM_ (uncurry (printf "chowla(%2d) = %d\n")) $ chowlas [1..37]
mapM_ (uncurry (printf "There are %8s primes < %10s\n"))
(chowlaP
[ (1, 10^2)
, (succ $ 10^2, 10^3)
, (succ $ 10^3, 10^4)
, (succ $ 10^4, 10^5)
, (succ $ 10^5, 10^6)
, (succ $ 10^6, 10^7) ])
mapM_ (printf "%10s is a perfect number.\n" . commas) chowlaPerfect
printf "There are %2d perfect numbers < 35,000,000\n" $ length chowlaPerfect
where
chowlas = fmap ((,) <$> id <*> chowla)
chowlaP = fmap (bimap commas commas)
. snd
. mapAccumL (\total (count, max) -> (total + count, (total + count, max))) 0
. fmap chowlaPrimes
chunks = chunksOf ((35*10^6) `div` 10) [1..35 * 10^6]
chowlaPerfect = runPar $ do
pars <- mapM (spawnP . filter chowlaPerfectNum) chunks
result <- mapM get pars
pure $ join result
</lang>
=={{header|J}}==
| |||