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 with maximum possible orders. Given that any can be written as disjoint cycles, and given that the order of any cycle is its length, the order of 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 , the maximum possible order will be the maximum lcm of all partitions of .

For any let be the largest order of elements of . 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 by a brute force approach:

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

A somewhat more elegant approach uses the fact that the largest prime factor of 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 be the maximum order of a permutation in , subject to the constraint that all cycle lengths are powers of the first primes. Then , where ranges through all powers of the -st prime up to . 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):
    g=gpf(N)
    sieve = [True]*(g+1)
    prime = []
    for n in xrange(2,g+1):
        if sieve[n]:
            prime.append(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)
  5301036508850487626975427714489912082038158551922510400

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

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

About these ads