8
$\begingroup$

Landau's function $g(n)$ is the largest order of an element of the symmetric group $S_n$. Equivalently, $g(n)$ is the largest least common multiple (lcm) of any partition of $n$.

In general $g(n)$ is hard to compute and bounds are known.

I am wondering is it possible to compute $g(n)$ efficiently or even find easy closed form for special cases.

EDIT as Alexander Bors points out in comment, $\log{g(n)} \sim \sqrt{n\log{n}}$ which makes $g(n)$ exponential in $n$, possibly answering the previous revision.

Is there an infinite increasing sequence $a(n)$ of naturals for which $g(n)$ can be efficiently computed, assuming one can store $g(a(n))$ in RAM of sufficiently powerful computer?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Since $\mathrm{log}\hspace{2pt}g(n)\sim\sqrt{n\cdot\mathrm{log}\hspace{2pt}n}$, the number of ciphers of $g(n)$ alone is already too large to allow for computation in time polynomial in $\mathrm{log}\hspace{2pt}n$ on any infinite set of values for $n$. $\endgroup$
    – Alexander Bors
    Commented Jan 6, 2015 at 14:53
  • 1
    $\begingroup$ If $n$ is the sum of the first $k$ primes, can $g(n)$ be anything other than the product of those primes? $\endgroup$
    – Gerry Myerson
    Commented Jan 6, 2015 at 14:59
  • $\begingroup$ @GerryMyerson yours would have been very nice, but I think it can be something else: for $n=\sum_{p \le 43}=281$ g(n) factors as 2^4 * 3^2 * 5^2 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 43 $\endgroup$
    – joro
    Commented Jan 6, 2015 at 15:20
  • $\begingroup$ @GerryMyerson you can verify this in the OEIS b-file: oeis.org/A000793/b000793.txt $\endgroup$
    – joro
    Commented Jan 6, 2015 at 15:23
  • 2
    $\begingroup$ Yes, there's a smaller example at $n=100=2+3+\cdots+23$, where $g(n)=(16)(9)(5)(7)(11)(13)(17)(19)$. $\endgroup$
    – Gerry Myerson
    Commented Jan 6, 2015 at 15:32

0

Reset to default

You must log in to answer this question.