## 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):
p=Partitions(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

$p<1.328\sqrt{n\ln(n)}$

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):
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


### One Response

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

The AIM Network

The Australian Independent Media Network