[Haskell-cafe] Is there an efficient way to generate Euler's totient function for [2, 3..n]?
daniel.is.fischer at googlemail.com
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.
> -- From: http://www.haskell.org/haskellwiki/99_questions/Solutions/34
> totient :: Int -> Int
> totient n = length [x | x <- [1..n], coprime x n]
> 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
> > 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.
More information about the Haskell-Cafe