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.

Posted by programmingpraxis

Filed in Exercises

4 Comments »

4 Responses to “Highly Composite Numbers, A Sieving Approach”

Daniel said

July 23, 2016 at 12:56 PM

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:

[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, 1081080, 1441440, 2162160]

Daniel said

July 23, 2016 at 1:04 PM

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);
}

Daniel said
July 23, 2016 at 1:05 PM
> “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”.
Highly Abundant Numbers | Programming Praxis said
December 20, 2016 at 9:01 AM
[…] 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 […]

Programming Praxis