Highly Composite Numbers, A Sieving Approach

July 19, 2016

We’ve seen programs to compute the sequence of highly composite numbers in two previous exercises. Today, we look at a third algorithm, based on the Sieve of Eratosthenes.

If you have to find a the divisors of a number, or count them, you can employ the brute-force method of testing each possible divisor from 1 to n, as in the first solution to this problem, or you can factor n and compute the divisors, as we have done in a previous exercise. But if you have to find the divisors of a bunch of numbers, in sequence, you can sieve for them; we also did that in a previous exercise. Once you know the divisor-count for each number from 1 to n, a simple sequential scan looking for successive records will create the list of highly composite numbers.

Your task is to write a program to calculate highly composite numbers less than a limit n using a sieving algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

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

1. Daniel said

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]

2. Daniel said

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

3. Daniel said

> “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”.

4. […] 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 […]