## Highly Composite Numbers

### July 12, 2016

[ Today’s exercise was written by Zacharias Voulgaris, based on a Numberphile video. Guest authors are always welcome; contact me if you wish to write an exercise. ]

A highly composite number, also called an anti-prime, is a number *n* for which d(*m*) < d(*n*) for all *m* < *n*, where d(*x*) is the *divisor* function that gives a count of the number of divisors of *x*; in other words, a highly composite number has more divisors than any smaller number. Thus, a highly composite number, which has many divisors, is the opposite of a prime number, which has only two divisors. The sequence of highly composite numbers, which begins 1, 2, 4, 6, 12, 24, 36, … (A002182), has been studied by Ramanujan and Erdös, among others, and is a continuing object of study by number theorists. A famous highly composite number, known to Plato, is 5040.

Your task is to write a program that returns all highly composite numbers less than a given limit. 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

This version calculates the number of divisors as suggested by the first comment for [a href=”http://oeis.org/A000005″]A000005[/a]: it calculates the prime factorization of the number, and then calculates the product of (exponent+1). Under Kawa Scheme, at least, this ends up being about 35% faster than the brute force method. (The factorization could be further optimized, too.)

So: HCNs are a subset of numbers with non-ascending sequences of prime exponents, we can generate all such sequences using a couple of extension operations ([a,b,c]->[a,b,c,1] and [a,b,c] -> [a,b,c+1]) and use a heap to generate the corresponding numbers in order.

Runtime is limited by the length of the primes array – with primes up to 119, we get 540 HCNs in about 15 mins (the 540th is 3625096965993854307674502488829776160975104640000 with 10899947520 divisors).

@matthew. I like your solution. It is easy to speed it up by a factor of 2, by changing extend1 and extend2 a little to calculate the new n, d from the former ones. By the way, 119 is not a prime.

@Paul: Thanks, much appreciated. Good point on 119, can’t think what I was thinking there (I don’t think it affects the result though).

Reusing the n and d values is a good idea (also we can reuse some of the arrays, helping with memory allocation – and bytearrays are probably better too).

There are some nice algorithms linked from https://en.wikipedia.org/wiki/Highly_composite_number that use serious maths to get much larger values.

[…] different solution to the previous exercise exploits the form of highly composite numbers, which always consists of small primes to large […]

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