Landau’s function for one million billions (2009)

Let <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>𝔖</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> denote the symmetric group with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> letters, and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>g</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> the maximal order of an element of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>𝔖</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> . If the standard factorization of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>M</mml:mi> </mml:math> into primes is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>M</mml:mi> <mml:mo>=</mml:mo> <mml:msubsup> <mml:mi>q</mml:mi> <mml:mn>1</mml:mn> <mml:msub> <mml:mi>α</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:msubsup> <mml:msubsup> <mml:mi>q</mml:mi> <mml:mn>2</mml:mn> <mml:msub> <mml:mi>α</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:msubsup> <mml:mo>...</mml:mo> <mml:msubsup> <mml:mi>q</mml:mi> <mml:mi>k</mml:mi> <mml:msub> <mml:mi>α</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:msubsup> </mml:mrow> </mml:math> , we define <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℓ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>M</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> to be <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msubsup> <mml:mi>q</mml:mi> <mml:mn>1</mml:mn> <mml:msub> <mml:mi>α</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:msubsup> <mml:mo>+</mml:mo> <mml:msubsup> <mml:mi>q</mml:mi> <mml:mn>2</mml:mn> <mml:msub> <mml:mi>α</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:msubsup> <mml:mo>+</mml:mo> <mml:mo>...</mml:mo> <mml:mo>+</mml:mo> <mml:msubsup> <mml:mi>q</mml:mi> <mml:mi>k</mml:mi> <mml:msub> <mml:mi>α</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:msubsup> </mml:mrow> </mml:math> ; one century ago, E. Landau proved that <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>g</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:msub> <mml:mo movablelimits="true" form="prefix">max</mml:mo> <mml:mrow> <mml:mi>ℓ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>M</mml:mi> <mml:mo>)</mml:mo> <mml:mo>≤</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mi>M</mml:mi> </mml:mrow> </mml:math> and that, when <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> goes to infinity, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo form="prefix">log</mml:mo> <mml:mi>g</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>∼</mml:mo> <mml:msqrt> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo form="prefix">log</mml:mo> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msqrt> </mml:mrow> </mml:math> . There exists a basic algorithm to compute <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>g</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>n</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> ; its running time is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>𝒪</mml:mi> <mml:mfenced close=")" open="(" separators=""> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>/</mml:mo> <mml:msqrt> <mml:mrow> <mml:mo form="prefix">log</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:msqrt> </mml:mfenced> </mml:mrow> </mml:math> and the needed memory is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>𝒪</mml:mi> <mml:mo>(</mml:mo> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> ; it allows computing <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>g</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> up to, say, one million. We describe an algorithm to calculate <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>g</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> for <mml:math xmlns:mml="http://www.w3.org/1998/