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

14 May 2011

      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.

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

Daniel Fischer