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

Sat May 14 20:00:28 CEST 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.

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

```