Programming Praxis – Sieving For Totients

In today’s Programming Praxis exercise, our goal is to calculate the totients of a given range of numbers using a sieve. Let’s get started, shall we?

Due to the way I structured my code, Data.Map is a little more convenient than Data.Vector (since Data.Vector lacks the equivalent of the adjust function).

import qualified Data.Map as M

The sieving can be solved easily with two folds. The outer one to check all the elements in the list, and the inner one to update all the multiples of a given index. One space-saving trick is to realize that you don’t need to treat i and its multiples differently, since i * (1 – 1/i) = i – i/i = i – 1. This saves a separate insert call.

totients :: Integral a => a -> [a]
totients n = M.elems $ foldl (\m i -> if m M.! i == i
    then foldr (M.adjust (\x -> div (x*(i-1)) i)) m [i,2*i..n] else m)
    (M.fromList $ zip [0..n] [0..n]) [2..n]

A test to see if everything is working properly:

main :: IO ()
main = print $ totients 100
About these ads

Tags: , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: