I Taught My Computer to Explore the Landau Function — and It Led Straight Toward the Riemann Hypothesis

Landau's function

Permutations and Counting A set $\displaystyle V$ is said to contain $\displaystyle n$ elements if its elements can be counted as $\displaystyle 1,2,\dotsc ,n$. In other words, $\displaystyle V$ can be placed in one-to-one correspondence with the set $\displaystyle \{1,2,\dotsc ,n\}$. Sometimes it is more convenient to start counting from zero, in which case we consider $\displaystyle \{0,1,2,\dotsc ,n-1\}$. Definition of a Permutation A permutation of a set V is a bijection $\displaystyle f:V\rightarrow V$ that is, a one-to-one correspondence of the set onto itself. Since we can count the elements of $\displaystyle V,$ we can label them as $\displaystyle V=\{v_{1} ,\ v_{2} ,\ ...,v_{n}\}$ But there are many ways to assign such labels. For example, a set with two elements can be listed in exactly two orders: $\displaystyle ( v_{1} ,v_{2})$ or $\displaystyle ( v_{2} ,v_{1})$. Thus, a permutation may be viewed as a reordering or reindexing of the elements of the set. If one ordering is written as $\displaystyle ( v_{1} ,v_{2} ,\dotsc ,v_{n})$, another ordering obtained by a permutation can be written as $\displaystyle ( v_{\ }{}_{\ }{}_{i_{1}} ,v_{i_{2}} ,\dotsc ,v_{i_{n}})$, where $\displaystyle ( i_{1} ,i_{2} ,\dotsc ,i_{n})$ is a rearrangement of $\displaystyle ( 1,2,\dotsc ,n)$. Often, to simplify notation, we omit the symbols $\displaystyle v_{i}$ altogether and talk directly about permutations of the index set $\displaystyle \{1,2,3,\dotsc ,n\}$. This is natural, since the permutation acts only on the indices, not on the intrinsic nature of the elements themselves. Counting Permutations How many different ways can we count or order a set of $\displaystyle n\ $elements? Equivalently, how many distinct permutations are there of$\displaystyle \ n$ elements? The number of all possible permutations of a set with nelements is denoted by $\displaystyle n!$ "(read “" n" factorial”)." Thus, $\displaystyle n!$ represents the number of distinct orderings of $\displaystyle n$ objects. For example: $\displaystyle 2!=2$:there are two ways to order two elements $\displaystyle 1!=1$ $\displaystyle 3!=6$ since there are six possible orderings of three elements $\displaystyle ( 1,2,3)$ $\displaystyle ( 1,3,2)$ $\displaystyle ( 2,1,3)$ $\displaystyle ( 2,3,1)$ $\displaystyle ( 3,1,2)$ $\displaystyle ( 3,2,1)$ Counting the Empty Set Finally, consider the empty set, which contains no elements at all: $\displaystyle \emptyset =\{\}$. (Notice that the set $\displaystyle \{0\}$ is not empty — it contains one element.) In how many ways can one “count” the empty set? Since there is nothing to arrange, the question reduces to: In how many ways can one do nothing? The mathematical answer is: exactly one. Hence, by convention, $\displaystyle 0!=1$. Algorithm for Generating All Permutations Let’s take a finite ordered set $\displaystyle 𝑉=\{1,2,\dotsc ,𝑛\}$. We want to produce all possible rearrangements of these $\displaystyle 𝑛$ elements — that is, all $\displaystyle 𝑛$! permutations Recursive Idea The idea is simple and elegant: To find all permutations of $\displaystyle n$ elements, fix one element in front, then recursively permute the remaining $\displaystyle n-1$ elements Formally: Base case: If $\displaystyle n=1$, there is only one permutation: $\displaystyle ( 1)$. Recursive step: Suppose we already know all permutations of $\displaystyle \{1,2,\dotsc ,n-1\}$. To obtain all permutations of $\displaystyle \{1,2,\dotsc ,n\} :$ Insert the new element $\displaystyle n$ into every possible position in each existing permutation. Example for $\displaystyle n=3$ Start with $\displaystyle \{1,2\}$: $\displaystyle ( 1,2) ,\ ( 2,1)$ Now insert $\displaystyle 3$ into every possible position: From $\displaystyle ( 1,2)$: $\displaystyle (\mathbf{3} ,1,2) ,( 1,\mathbf{3} ,2) ,( 1,2,\mathbf{3})$ From $\displaystyle ( 2,1)$: $\displaystyle (\mathbf{3} ,2,1) ,( 2,\mathbf{3} ,1) ,( 2,1,\mathbf{3})$ Total $\displaystyle 6=3!$ permutations. Recursive Algorithm (Pseudocode) Here is the algorithm in a concise recursive form: PERMUTE(A, l, r) Input: array A of elements to permute l = starting index r = ending index Output: all permutations of A[l..r] if l == r then print A else for i from l to r do swap(A[l], A[i]) PERMUTE(A, l+1, r) swap(A[l], A[i]) // backtrack Explanation The function PERMUTE generates all permutations of the subarray$\displaystyle \ A[ l..r]$. The algorithm proceeds by

fixing one element (by swapping it into position l),

then recursively permuting the rest of the array.

After each recursive call, it restores the array to its original order (backtracking step). This method systematically explores every possible ordering. Example Run For $\displaystyle A=[ 1,2,3]$: Fix $\displaystyle 1$ in front → permute $\displaystyle [ 2,\ 3] \ \rightarrow \ ( 1,2,3) ,\ ( 1,3,2)$ Fix $\displaystyle 2$ in front → permute $\displaystyle [ 1,\ 3] \ \rightarrow \ ( 2,1,3) ,\ ( 2,3,1)$ Fix $\displaystyle 3$ in front → permute $\displaystyle [ 1,\ 2] \ \rightarrow \ ( 3,1,2) ,\ ( 3,2,1)$ All $\displaystyle 6$ permutations appear exactly once. Iterative Variant (Lexicographic order) There is also a non-recursive method, known as Heap’s algorithm or the lexicographic algorithm, used in computational implementations. Lexicographic algorithm (outline): Start with the list sorted in ascending order. Find the rightmost pair $\displaystyle ( a_{k} ,a_{k+1})$ with $\displaystyle a_{k} < a_{k+1}$. Find the smallest element $\displaystyle a_{l} >a_{k}$ to the right of $\displaystyle a_{k}$. Swap $\displaystyle a_{k}$ and $\displaystyle a_{l}$. Reverse the sublist after position $\displaystyle k$. Repeat until no such pair exists. This generates permutations in lexicographic order (the same order used by std::next_permutation in C++). The set of all permutations of a set A permutation of a finite set Xis a bijective map $\displaystyle σ :X\rightarrow X$. If $\displaystyle X=\{1,2,\dotsc ,n\}$, the set of all permutations of $\displaystyle X$ forms a group under composition, called the symmetric group $\displaystyle S_{n}$. Thus, $\displaystyle S_{n} =\left\{σ :\{1,\dotsc ,n\}\rightarrow \{1,\dotsc ,n\} \mid σ \ is\ bijective\right\}$. Each element of $\displaystyle S_{n}$ corresponds to a rearrangement of the integers $\displaystyle 1,\dotsc ,n$. For instance, for $\displaystyle n=4$, $\displaystyle σ =\begin{pmatrix} 1 & 2 & 3 & 4\\ 2 & 4 & 3 & 1 \end{pmatrix}$ means $\displaystyle σ ( 1) =2,\ σ ( 2) =4,\ σ ( 3) =3,\ σ ( 4) =1$. Cycle decomposition Every permutation can be uniquely (up to order of factors) decomposed into disjoint cycles. A cycle of length$\displaystyle \ k$ is a permutation that sends $\displaystyle i_{1}\rightarrow i_{2} ,\ \ i_{2}\rightarrow i_{3} ,\ ...,\ \ i_{k-1}\rightarrow i_{k} ,\ i_{k}\rightarrow i_{1}$, and fixes all other elements. It is denoted $\displaystyle ( i_{1} ,\ i_{2} \dotsc \ i_{k})$. Two cycles are disjoint if they act on disjoint subsets of $\displaystyle \{1,\dotsc ,n\}$. Disjoint cycles commute, and their product gives the full permutation. So any $\displaystyle σ \in S_{n}$ can be written uniquely as $\displaystyle σ =C_{1} \ C_{2} \cdots C_{r}$, where $\displaystyle C_{i}$ are disjoint cycles with lengths $\displaystyle a_{1} ,a_{2} ,\dotsc ,a_{r}$, satisfying $\displaystyle a_{1} +a_{2} +\cdots +a_{r} =n$ For instance, if $\displaystyle σ =\begin{pmatrix} 1 & 2 & 3 & 4\\ 2 & 4 & 3 & 1 \end{pmatrix}$ we have $\displaystyle 1\rightarrow 2,2\rightarrow 4,4\rightarrow 1$ $\displaystyle 3\rightarrow 3$ $\displaystyle σ =( 1,2,5)( 3)$ Order of a permutation The order of a permutation$\displaystyle \ σ $, denoted $\displaystyle ord⁡( σ )$ is the smallest positive integer$\displaystyle \ k$ such that $\displaystyle σ ^{k} =e$, where $\displaystyle e$ is the identity permutation (i.e., $\displaystyle e( i) =i$ for all $\displaystyle i$). Now, if $\displaystyle σ =C_{1} \ C_{2} \cdots C_{r}$, is the product of disjoint cycles with lengths $\displaystyle a_{1} ,\dotsc ,a_{r}$, then each cycle $\displaystyle C_{i}$ has order $\displaystyle a_{i}$, and since disjoint cycles commute, $\displaystyle σ ^{k} =e$ if and only if $\displaystyle a_{i} \mid k$ for all $\displaystyle \ i$. Therefore, $\displaystyle ord⁡( σ ) =lcm( a_{1} ,a_{2} ,\dotsc ,a_{r}) ,$ the least common multiple of the cycle lengths. Example Let $\displaystyle σ =( 1\ 2\ 4)( 3\ 5) \in S_{5}$. The cycle lengths are $\displaystyle a_{1} =3$ and $\displaystyle a_{2} =2$. Hence $\displaystyle ord⁡( σ ) =lcm( 3,2) =6$. Indeed,$\displaystyle \ σ ^{6} =e$, and no smaller positive power yields the identity. Definition of the Landau function The Landau function g(n) is defined as the maximum order of an element in the symmetric group $\displaystyle S_{n}$. That is, $\displaystyle g( n) =\max_{σ \in Sn} \ ord⁡( σ )$, where $\displaystyle ord( σ )$ is the smallest positive integer $\displaystyle k$ such that $\displaystyle σ ^{k} =e$.

Connecting to permutations Each permutation $\displaystyle σ \in S_{n}$ decomposes into disjoint cycles, say of lengths $\displaystyle a_{1} ,a_{2} ,\dotsc ,a_{r}$, with $\displaystyle a_{1} +a_{2} +\cdots +a_{r} =n$. The order of $\displaystyle σ $ is then the least common multiple of its cycle lengths: $\displaystyle ord⁡( σ ) =lcm( a_{1} ,a_{2} ,\dotsc ,a_{r})$. Hence, the problem of finding $\displaystyle g( n$) becomes: $\displaystyle g( n) =\max_{a_{1} +a_{2} +...+a_{r} =n} \ lcm( a_{1} ,a_{2} ,\dotsc ,a_{r})$

So we are choosing a partition of $\displaystyle n$ to maximize this $\displaystyle lcm$.

The asymptotic behavior — where the prime connection becomes explicit

Landau (1903) proved that $\displaystyle log( g⁡( n)) \sim \sqrt{n\ log\ n}$ as $\displaystyle n\rightarrow \infty $.

Recent work (and classical work going back to Landau/Massias/Nicolas/Robin) shows that

a fairly simple upper bound on the Landau function $\displaystyle g( n)$ is equivalent to

the Riemann Hypothesis (RH). https://arxiv.org/abs/1907.07664

In my book — The Riemann Hypothesis Revealed — you will find all the essential mathematical groundwork needed to approach one of the deepest problems in modern thought. 

My goal is not only to explain what is known, but to equip you with the tools, intuition, and confidence to go further — to continue the exploration where classical results end and genuine discovery begins. 

Efficient computation Landau proved that the optimal LCM corresponds to using prime powers $\displaystyle p^{k}$ as the cycle lengths. Thus: $\displaystyle \log( ⁡g( n)) =\max_{\sum p^{k} \leqslant n}\sum \log\left( p^{k}\right) \ $ This is a knapsack problem: maximize $\displaystyle \sum \log\left( p^{k}\right)$with cost $\displaystyle \sum p^{k} \leqslant n$. We can compute it efficiently with dynamic programming.

Dynamic Programming Idea Let’s define a state that captures a partial computation of $\displaystyle g( n)$: $\displaystyle G[ i] =g( i)$ and try to express $\displaystyle G[ n]$ in terms of smaller values $\displaystyle G[ k]$ for $\displaystyle k< $n. Now,

suppose we fix one cycle length $\displaystyle k$ (a block size in the partition). Then we can consider that one part of the permutation cycle has

length$\displaystyle \ k$, and the remaining part has total length $\displaystyle n-k$.

So, the overall LCM becomes: $\displaystyle lcm( k,\ \ something\ that\ sums\ to\ \ n-k)$ But “something that sums to $\displaystyle n-k$” is exactly represented by $\displaystyle G[ n-k]$. Hence the recurrence: $\displaystyle G[ n] =\max_{1\leq k\leq n} \ lcm( k,G[ n-k])$ That’s the central DP formula. It says: To compute $\displaystyle g( n)$,

try taking one cycle of length$\displaystyle \ k$,

and combine it with the best (maximum LCM) structure possible for the remaining $\displaystyle n-k$ elements. Algorithm (Step-by-step) Initialize $\displaystyle G[ 0] =1$ (the LCM of the empty set conventionally equals 1).

For each n=1 to N: Initialize G[n]=1 For each k=1 to n: Compute G[n]=max⁡(G[n],lcm(k,G[n-k])) Output G[n]. Example Let’s compute a few by hand: G[1]=max⁡(lcm(1,G[0]))=1 G[2]=max⁡(lcm(1,G[1]),lcm(2,G[0]))=max⁡(1,2)=2 G[3]=max⁡(lcm(1,G[2]),lcm(2,G[1]),lcm(3,G[0]))=max⁡(2,2,3)=3 G[4]=max⁡(lcm(1,3),lcm(2,2),lcm(3,1),lcm(4,1))=max⁡(3,2,3,4)=4 G[5]=max⁡(lcm(1,4),lcm(2,3),lcm(3,2),lcm(4,1),lcm(5,1))=max⁡(4,6,6,4,5)=6 So the sequence starts: 1, 2, 3, 4, 6, 6, 12, 15, 20, 30, ... That matches the Landau function table. Implementation sketch Precompute all prime powers $\displaystyle p^{k} \leq n$. Use a 1D DP array: dp[s]=maximum of log⁡("lcm of cycles") using total size s. In practice: dp[s + $\displaystyle p^{k}$] = max(dp[s + $\displaystyle p^{k}$], dp[s] + $\displaystyle \log\left( p^{k}\right)$); At the end, $\displaystyle g( n) =exp⁡(\max_{s\leq n} \ dp[ s])$.

C++ Implementation (Efficient up to n = 2000)

 

#include <bits/stdc++.h>

using namespace std;

int main() {

    const int N = 200;

    vector<double> dp(N + 1, 0.0);

    // Generate all prime powers <= N

    vector<int> primePowers;

    vector<bool> isPrime(N + 1, true);

    isPrime[0] = isPrime[1] = false;

 

    for (int p = 2; p <= N; ++p) {

        if (isPrime[p]) {

            for (int q = p * 2; q <= N; q += p)

                isPrime[q] = false;

            long long power = p;

            while (power <= N) {

                primePowers.push_back((int)power);

                power *= p;

            }

        }

    }

 

    // Dynamic programming: maximize sum of logs

    for (int x : primePowers) {

        double lx = log((double)x);

        for (int s = N - x; s >= 0; --s) {

            dp[s + x] = max(dp[s + x], dp[s] + lx);

        }

    }

 

    // Output results

    ofstream out("landau.dat");

    out << "# n g(n)\n";

    for (int n = 1; n <= N; ++n) {

        double maxlog = 0.0;

        for (int s = 0; s <= n; ++s)

            maxlog = max(maxlog, dp[s]);

        double gn = exp(maxlog);

        out << n << " " << fixed << setprecision(0) << gn << "\n";

    }

    out.close();

    cerr << "Generated landau.dat up to n = " << N << endl;

    return 0;

}

Plotting with Gnuplot

Once you compile and run this C++ code (producing landau.dat), open Gnuplot and enter:

reset

 

# Set terminal and output format

set terminal pngcairo size 2400,1600 enhanced font 'Arial-Bold'

set output 'landau.png'

 

# Set the terminal to display the plot in a window

#set terminal wxt enhanced

set logscale y

set title "Landau Function g(n)"

set xlabel "n"

set ylabel "g(n)"

set grid

plot "landau.dat" using 1:2 with lines lw 5 title "g(n)"