CH

Mircea Popescu asked for computations of the largest primorial to fit within first 515 bytes, and then 4096 later for reasonable reasons having to do with RSA padding and machine word widths. And so my adventures in remedial mathematics continue, with an implementation of the Sieve of Eratosthenes (which, no, I also had never heard about until Popescu mentioned it.

The sieve implementation is reasonable, although it struck me while writing this that the loop macro has quite clearly infected me to the point where Everything Must be Implemented in Terms of It. Also worth noting is the hilaribad hack of summing lists of primes sieved out from below 4096 and then re-sieving until a resulting list sums that is less than 2^4096.

Code:

(defun sieve (max)
  (let ((candidates (make-array (+ 1 max) :element-type 'bit :initial-element 1)))
    (setf (aref candidates 0) 0)
    (setf (aref candidates 1) 0)
    (loop for p from 2 below max
       do
         (if (= 1 (aref candidates p))
             (loop
                for multiple = (* p 2) then (+ multiple p)
                until
                  (>= multiple (+ 1 max))
                do
                  (setf (aref candidates multiple) 0))))
    (loop
       for c across candidates
       for i = 0 then (+ 1 i)
       when (= c 1)
       collect i)))

(defun primorial (bits)
  (loop
     for maxprime downfrom 4096
     and candidate = (apply #'* (sieve maxprime))
     when (< candidate (expt 2 bits))
     return candidate))

Runs handily in under a second on this computer:

Evaluation took:
  0.817 seconds of real time
  0.822183 seconds of total run time (0.800534 user, 0.021649 system)
  [ Run times consist of 0.053 seconds GC time, and 0.770 seconds non-GC time. ]
  100.61% CPU
  1,961,326,656 processor cycles
  191,607,056 bytes consed

76558065161304251460282055114108589258221172582778212897660717846236903644990337520644670635312274859358138194434424317353505197245841157023986591722929932769973839671344222659789484422389074929063428293359537890882352682080861666155856701907385016181234445501433485834355581608538613949727587779017785931260260914626833639125368582215957878131988744703627349494773630779893153944409332636543777256924688085994030412710490900818402513392514739096990707529801878922479452150366783115306806122953223681368887605169300935213053938361309417317043898395311172948859629735927090134805846868192283007483996959304908910108226729064589294656936714614166784010991216658976345808461171870505690571171978805123096417820213497926956045657612245751388557335587860629959153168802552603694003223199218992695468853266169445025000246364540137060717383649439362850511332616189438331864141257120887414392865895058690613856748502474649872890413430462675521160914666877619827907082224516198516371525941063258265811140191052136612858758172838162168739793712634892483833748520153818159361011542386867749973012327109013046262704823931996678577068234775283556117639727321779655106182561236936733490468113837255296884870490823282493283179240742667438880502010

Matching Diana Coman's and PeterL's. I recall mod6 confirming this number as well, but cannot find the log line. Do write in if you find it, listeners.

This excursion into the fascinating worlds of primes now complete, I'm going to return to my studies in remedial binary arithmetic (which are going fine, albeit slowly due to the annoying handicap of having my workstation not proximate to my sleep station; and a poverty of compute and space for compute away from the prying hands of toddlers in my current domicile; all of which are scheduled for remediation this fall, the orchestration of which is all very much under steam), which I'd left off in disgust recently having realized I was trying to write overgeneralized solutions the problem of reading a random n-byte integer from a byte stream.

There really is no better training ground for the intelligent, curious, and hardworking than The Republic of Bitcoin.