Daniel Fischer schrieb:
On Saturday 14 May 2011 19:38:03, KC wrote:
Instead of finding the totient of one number, is there a quicker way
when processing a sequence?
For some sequences.
You may find alternative ways of computation in the Online Encyclopedia
of Integer Sequences.
It's declarative and may help to verify more efficient implementations.
WOW! Good insight. :)
On Sun, May 22, 2011 at 9:27 AM, Henning Thielemann
schlepp...@henning-thielemann.de wrote:
Daniel Fischer schrieb:
On Saturday 14 May 2011 19:38:03, KC wrote:
Instead of finding the totient of
Is there an efficient way to generate Euler's totient function for [2,3..n]?
Or an arithmetical sequence?
Or a geometric sequence?
Or some generalized sequence?
--
--
Regards,
KC
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
On Sat, May 14, 2011 at 10:22 AM, KC kc1...@gmail.com wrote:
Is there an efficient way to generate Euler's totient function for [2,3..n]?
Or an arithmetical sequence?
Or a geometric sequence?
Or some generalized sequence?
Does computing the totient function require obtaining the prime
Instead of finding the totient of one number, is there a quicker way
when processing a sequence?
-- From: http://www.haskell.org/haskellwiki/99_questions/Solutions/34
totient :: Int - Int
totient n = length [x | x - [1..n], coprime x n]
where
coprime a b = gcd a b == 1
On Sat, May 14,
On Saturday 14 May 2011 19:38:03, KC wrote:
Instead of finding the totient of one number, is there a quicker way
when processing a sequence?
For some sequences.
For [1 .. n] (you asked about [2 .. n], but it may be better to include 1),
it can efficiently be done, O(n*log log n), iirc.
