## Highly Composite Numbers

### July 12, 2016

We give an answer in Julia:

function nod(x::Int64) # number of divisors n = 2 # every number is divisible by 1 and by itself for z = 2:div(x,2) if x % z == 0 n += 1 end end return n end function hcp(N::Int64 = 1000) # Highly Composite Numbers y = [1] # list of highly composite numbers z = [1] # list of corresponding number of divisors for x = 2:N n = nod(x) if n > z[end] push!(y, x) push!(z, n) end end return hcat(y, z) end

The calculation of the number of divisors is brute force, checking each *z* from 1 to *n* âˆ’ 1 for divisibility. Function `hcp`

iterates from 2 to the limit and stores each number whose divisor count exceeds the current maximum.

Since ideone does not provide Julia, a corresponding Scheme program is available at http://ideone.com/3EjR09.

Advertisements

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

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