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

[Daniel Fischer]

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
> 
> <warren.henning at gmail.com> wrote:
> > On Sat, May 14, 2011 at 10:22 AM, KC <kc1956 at gmail.com> 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.