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. Variant 1 (doesn't need to include 1): for i = 1 to n: sieve[i] := i for i = 2 to n: if sieve[i] == i -- i is prime for j = 1 to (n `div` i): sieve[i*j] := sieve[i*j]/i A more involved but faster variant is first building a smallest prime factor sieve, then calculating the totients from that (by the multiplicativity of the totient function; this is where it's nice to include 1); this allows a few optimisations the other one doesn't.

-- 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

NEVER do that! It's awfully slow.

On Sat, May 14, 2011 at 10:29 AM, Warren Henning

wrote:

...

On Sat, May 14, 2011 at 10:22 AM, KC wrote:

...

Is there an efficient way to generate Euler's totient function for [2,3..n]?

Or an arithmetical sequence?

Totients of [a, a+d .. a+n*d] ? For some values of a and d it can be done efficiently, in general not.

...

...

Or a geometric sequence?

Totients of [a*q^k | k <- [x .. y]] ? Yes, find the factorisations of a and q; from those it's trivial to compute the factorisations of a*q^k, and from those the totients. Of course, for large a and q finding the factorisation may be nontrivial.

...

...

Or some generalized sequence?

No, without special structure, the only way is to find each totient individually.

...

Does computing the totient function require obtaining the prime factorization of an integer,

For a single integer, an efficient calculation of the totient requires finding the prime factorisation, for a range [1 .. n], you can stop a little short of that.

...

which can't be done in polynomial time?

I suppose you mean "polynomial in the number of digits". I don't think it's proven that there's no polynomial time algorithm, just none has been found (yet) [if there is one].

...

Maybe I misunderstood what you were saying.

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 wrote:

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.

http://oeis.org/A000010

...

...

-- 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

NEVER do that! It's awfully slow.

It's declarative and may help to verify more efficient implementations.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- -- Regards, KC