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.
Here’s a solution in C++.
#include <cstdio> #include <vector> using std::vector; // Computes the highly composite numbers less than n. void HighlyComposites(const int n, vector<int>* highly_composites) { vector<int> divisor_counts(n, 0); for (int i = 1; i < n; ++i) { for (int j = i; j <= n; j += i) { divisor_counts[j]++; } } int max_divisors = 0; for (int i = 1; i < n; ++i) { int divisor_count = divisor_counts[i]; if (divisor_count > max_divisors) { highly_composites->push_back(i); max_divisors = divisor_count; } } } void PrintVector(const vector<int>& v) { printf("["); for (int i = 0; i < v.size(); ++i) { if (i > 0) printf(", "); printf("%d", v[i]); } printf("]\n"); } int main(int argc, char* argv[]) { vector<int> highly_composites; int limit = 2162160 + 1; // t make sure you get them all up to 2,162,160 HighlyComposites(limit, &highly_composites); PrintVector(highly_composites); }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.
#include <cstdio> #include <vector> using std::vector; // Computes the highly composite numbers less than n. void HighlyComposites(const int n, vector<int>* highly_composites) { vector<int> divisor_counts(n, 0); for (int i = 1; i < n; ++i) { for (int j = i; j < n; j += i) { divisor_counts[j]++; } } int max_divisors = 0; for (int i = 1; i < n; ++i) { int divisor_count = divisor_counts[i]; if (divisor_count > max_divisors) { highly_composites->push_back(i); max_divisors = divisor_count; } } } void PrintVector(const vector<int>& v) { printf("["); for (int i = 0; i < v.size(); ++i) { if (i > 0) printf(", "); printf("%d", v[i]); } printf("]\n"); } int main(int argc, char* argv[]) { vector<int> highly_composites; int limit = 2162160 + 1; // t make sure you get them all up to 2,162,160 HighlyComposites(limit, &highly_composites); PrintVector(highly_composites); }> “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 […]