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 ein 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 &lt;= 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 &lt;= n:
                newval = q * landau_vals[n-q]
                if newval &gt; 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()

Leave a Reply

Your email address will not be published. Required fields are marked *