Landau’s function

A few weeks ago, when I was writing about the general group-theoretical version of the Elgamal cryptosystem, I was led to try to find elements of the symmetric group S_n with maximum possible orders. Given that any e\in S_n can be written as disjoint cycles, and given that the order of any cycle is its length, the order of e is the lowest common multiple of the lengths of its cycles. Since a set of cycle lengths may be considered as an integer partition of n, the maximum possible order will be the maximum lcm of all partitions p of n.

For any n let g(n) be the largest order of elements of S_n. It turns out that this function is quite well known, and is called Landau’s function, after Edmund Landau, who first investigated it. Some values are given in the OEIS as sequence number 793.

It can be calculated for small values of n by a brute force approach:

def landau(n):
    return max([lcm(i) for i in p])

A somewhat more elegant approach uses the fact that the largest prime factor p of g(n) satisfies


and has been coded in Python by David Radcliffe and can be seen here. David’s insight was to use dynamic programming, as he explains in his comments:

We compute Landau’s function using dynamic programming, by adding one prime at a time. Let L(N,k) be the maximum order of a permutation in S_N, subject to the constraint that all cycle lengths are powers of the first k primes. Then L(N,k+1) = \max q*L(N-q,k), where q ranges through all powers of the (k+1)-st prime up to N. We stop when all possible prime factors have been exhausted.

Taking the heart of David’s program for use in Sage produces:

def gpf(N):
    return int(1.328 * (N*log(N))**0.5) + 1

def landau(N):
    sieve = [True]*(g+1)
    prime = []
    for n in xrange(2,g+1):
        if sieve[n]:
            if n^2 <= N:
                for m in xrange(n^2,g+1,n):
                    sieve[m] = False
    landau_vals = [1]*(N+1)
    for p in prime:
        for n in xrange(N,1,-1):
            q = p
            while q <= n:
                newval = q * landau_vals[n-q]
                if newval > landau_vals[n]:
                    landau_vals[n] = newval
                q *= p
    return landau_vals[N]

This is very fast:

sage: landau(2000)

The first brute force method would most definitely not be suitable here:

sage: p=Partitions(2000)
sage: p.cardinality()

One Response

  1. […] blog post here describes somebody else’s efforts at coding this up. He gets an improvement over the naive approach by […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The AIM Network

The Australian Independent Media Network


Get every new post delivered to your Inbox.

Join 54 other followers

%d bloggers like this: