Highly Composite Numbers, A Sieving Approach
July 19, 2016
Sieving for divisor counts is done in the two nested do
-loops, then the scan for records is done in the let
-loop:
(define (hcn n) (let ((divs (make-vector (+ n 1) 0))) (do ((i 1 (+ i 1))) ((<= n i)) (do ((j i (+ j i))) ((<= n j)) (vector-set! divs j (+ 1 (vector-ref divs j))))) (let loop ((i 1) (record 0) (hcns (list))) (if (<= n i) (reverse hcns) (if (< record (vector-ref divs i)) (loop (+ i 1) (vector-ref divs i) (cons i hcns)) (loop (+ i 1) record hcns))))))
For relatively small values of n, this is quite fast, less than 2 seconds for the highly composite numbers less than a million. Unfortunately, it will slow down as n gets larger:
> (time (hcn 1000000)) (time (hcn 1000000)) 23 collections 1872 ms elapsed cpu time, including 31 ms collecting 1861 ms elapsed real time, including 12 ms collecting 100003656 bytes allocated, including 96031104 bytes reclaimed (1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560 10080 15120 20160 25200 27720 45360 50400 55440 83160 110880 166320 221760 277200 332640 498960 554400 665280 720720)
You can run the program at http://ideone.com/VXju2x.
Advertisements
Pages: 1 2
Here’s a solution in C++.
Output:
The inner loop should go up to n, not n+1. I originally wrote the function to print all highly composites including n, but then saw the instructions say less than n. When updating, I mistakenly didn’t correct that inner loop bound. The code still seemingly worked with the out-of-bounds bug. Here’s the corrected version.
> “The inner loop should go up to n, not n+1”
I meant to say “The inner loop should go up to n-1, not n”.
[…] studied highly composite numbers in a series of several previous exercises, and had a lot of fun. In today’s exercise we look at a related concept: highly […]