The Kitchen Sink and Other Oddities

Atabey Kaygun

Landau's Function

The problem I was working on yesterday is an old problem that was first studied by Landau. I recommend an excellent article on the subject written by W. Miller.

If we use \(g(n)\) the denote the maximum order of an element in \(\Sigma_n\) the symmetric group on \(n\)-letters, the sequence is already recorded at the On-Line Encyclopedia of Integer Sequences.

There are different implementations calculating \(g(n)\). I recommend J.-L. Nicolas’ recent paper at arXiv for a more recent overview and references.

There are really fast and efficient implementations out there. There is one implementation that I really liked. Today, I will re-write it in lisp by changing it a bit along the way.

An implementation

For my implementation, I will need a function that returns the first prime number appearing after a specific integer. This is not very efficient but it will do.

(defun next-prime (n)
  (cond 
    ((< n 2) 2)
    ((= n 2) 3)
    ((evenp n) (next-prime (1- n)))
    (t (let* ((m (+ 2 n))
              (z (floor (sqrt m))))
          (do* ((a 3 (+ a 2)))
               ((or (> a z) (zerop (mod m a)))
                (if (> a z) 
                   m 
                   (next-prime m))))))))

NEXT-PRIME

Next, I took the core of the implementation I mentioned and translated as follows:

(defun landau (n)
  (let* ((limit (floor (* 1.328 (sqrt (* n (log n))))))
         (acc (make-array n :initial-element 1)))
      (do ((p 2 (next-prime p)))
          ((> p limit) (aref acc (1- n)))
         (loop for m from (1- n) downto 0 do
            (setf (aref acc m)
                  (do* ((res (aref acc m)
                             (max res (* q (aref acc (- m q)))))
                        (q p (* p q)))
                  ((> q m) res)))))))

LANDAU

And let me test it:

 (loop for i from 1 to 200 collect (landau i))

(1 1 2 3 4 6 6 12 15 20 30 30 60 60 84 105 140 210 210 420 420 420 420 840
 840 1260 1260 1540 2310 2520 4620 4620 5460 5460 9240 9240 13860 13860
 16380 16380 27720 30030 32760 60060 60060 60060 60060 120120 120120 180180
 180180 180180 180180 360360 360360 360360 360360 471240 510510 556920
 1021020 1021020 1141140 1141140 2042040 2042040 3063060 3063060 3423420
 3423420 6126120 6126120 6846840 6846840 6846840 6846840 8953560 9699690
 12252240 19399380 19399380 19399380 19399380 38798760 38798760 58198140
 58198140 58198140 58198140 116396280 116396280 116396280 116396280
 140900760 140900760 157477320 157477320 232792560 232792560 232792560
 232792560 281801520 446185740 446185740 446185740 446185740 892371480
 892371480 1338557220 1338557220 1338557220 1338557220 2677114440
 2677114440 2677114440 2677114440 2677114440 2677114440 3375492120
 3375492120 5354228880 5354228880 5354228880 5354228880 5354228880
 5354228880 6750984240 6750984240 7216569360 7216569360 8172244080
 12939386460 13385572200 13831757940 13831757940 25878772920 25878772920
 38818159380 38818159380 41495273820 41495273820 77636318760 77636318760
 82990547640 82990547640 82990547640 82990547640 82990547640 82990547640
 155272637520 155272637520 165981095280 165981095280 165981095280
 165981095280 165981095280 165981095280 209280511440 209280511440
 232908956280 232908956280 388181593800 401120980260 414952738200
 414952738200 414952738200 802241960520 802241960520 1203362940780
 1203362940780 1203362940780 1203362940780 2406725881560 2406725881560
 2406725881560 2406725881560 2406725881560 2406725881560 2872543794120
 2872543794120 4813451763120 4813451763120 4813451763120 4813451763120
 4813451763120 4813451763120 5745087588240 5745087588240 6141300525360
 6141300525360 7220177644680 7220177644680 12033629407800 12033629407800
 12033629407800 12033629407800 12033629407800 12033629407800 14440355289360
 14841476269620)