Here's code I wrote to generate Highly Composite Numbers that have divisors that have a power of two. Not the most elegant code, but gets the job done
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 

Highly composite numbers are numbers that have more divisors than the numbers below them. With some bit of number theory, it is particularly easy to construct HCNs with divisors of powers of two. This is because
A number $n = p^{a}q^{b}r^{c} ...$ has $(a+1)(b+1)(c+1)...$ divisors
$500 = 5^{3}2^{2}$, therefore it must have $(3+1)(2+1)$ = 12 divisors
1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500 (12 divisors)
1 2 3 4 5 6 7 8 9 10 11 

I will now go through how my program "thinks"
It starts with $2$ primes: $2$ and $3$
It selects the next candidate, which is the next prime. In this step, $5$
It checks if $2^{2}$ and $3^{2}$ are less than the candidate. We can see that $4$ is less than $5$, so we put it in the list of divisors
We add $2^{4}$ to the heap (to be clear, the heap is a different thing from the divisor list). What this will achieve, if you add this number to the heap, is that the number of divisors will remain a power of two. I construct this by making the exponent of two in our list is one less a power of two. $1 + 2 + 4 = 2^{3}  1$
We can see that our candidate prime, $5$, is larger than everything in the heap, so we put it in the divisor list
We put $5^{2}$ to the heap
Our next candidate is $7$
It checks if there's a number less than $7$ in our heap. There isn't, so we add $7^{2}$ to the heap and checks the next prime candidate, 11.
So on.
Is there a way to make this algorithm without a heap structure, or is the heap required? I was using a heap as a way to make sure that the numbers at the bottom are the smallest number, so I can be sure that there are no smaller numbers in the middle of the heap. I was thinking maybe using a heap structure was overkill. What do you think?
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
Sort by:
Top NewestThis is an interesting problem. Nice solution too! As best as I know, I have not seen a better way (or a more direct way) to do this without a heap. But this is not surprising as we do not have a closed form answer to every interesting number theoretic question.
Log in to reply
nicely done
Log in to reply