Make your own Highly Composite Number!

Find the smallest number with 25005002^{500500} divisors. Give your answer modulo 500500507500500507.

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

github

 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
# https://projecteuler.net/problem=500
# Find the smallest number with 2^500500 divisors.
# Give your answer modulo 500500507. 

import primes # Function I made to iterate through primes
import heapq as heap
import sys

h = []
divisors = [2, 3]

limit = 500500 - 1
divs = 2

def addDivisor(divisor):
    global divs
    if divs > limit:
        # print divisors
        print reduce(lambda x, y: x*y % 500500507, divisors) % 500500507
        sys.exit(0)
    divisors.append(divisor)
    divs = divs + 1

def main():
    # heap[0] = Actual number
    # heap[1] = Base number
    # heap[2] = Exponent
    heap.heappush(h, (4, 2, 2))
    heap.heappush(h, (9, 3, 2))

    for prime in primes.primeGen():
        # Select candidate from bottom of heap
        div = h[0]
        while div[0] < prime:
            div = heap.heappop(h)
            addDivisor(div[0])
            newExponent = div[2]*2
            heap.heappush(h, 
                    (div[1]**(newExponent), div[1], newExponent))
            div = h[0]
        addDivisor(prime)
        heap.heappush(h, (prime**2, prime, 2))


if __name__ == "__main__":
main()

Explanation

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=paqbrc...n = p^{a}q^{b}r^{c} ... has (a+1)(b+1)(c+1)...(a+1)(b+1)(c+1)... divisors

500=5322500 = 5^{3}2^{2}, therefore it must have (3+1)(2+1)(3+1)(2+1) = 12 divisors

1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500 (12 divisors)

Sample run

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
[2, 3, 4]  = 24 has 2^3 divisors
[2, 3, 4, 5]  = 120 has 2^4 divisors
[2, 3, 4, 5, 7]  = 840 has 2^5 divisors
[2, 3, 4, 5, 7, 9]  = 7560 has 2^6 divisors
[2, 3, 4, 5, 7, 9, 11]  = 83160 has 2^7 divisors
[2, 3, 4, 5, 7, 9, 11, 13]  = 1081080 has 2^8 divisors
[2, 3, 4, 5, 7, 9, 11, 13, 16]  = 17297280 has 2^9 divisors
[2, 3, 4, 5, 7, 9, 11, 13, 16, 17]  = 294053760 has 2^10 divisors
[2, 3, 4, 5, 7, 9, 11, 13, 16, 17, 19]  = 5587021440 has 2^11 divisors
[2, 3, 4, 5, 7, 9, 11, 13, 16, 17, 19, 23]  = 128501493120 has 2^12 divisors
[2, 3, 4, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25]  = 3212537328000 has 2^13 divisors

I will now go through how my program "thinks"

  1. It starts with 22 primes: 22 and 33

  2. It selects the next candidate, which is the next prime. In this step, 55

  3. It checks if 222^{2} and 323^{2} are less than the candidate. We can see that 44 is less than 55, so we put it in the list of divisors

  4. We add 242^{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=2311 + 2 + 4 = 2^{3} - 1

  5. We can see that our candidate prime, 55, is larger than everything in the heap, so we put it in the divisor list

  6. We put 525^{2} to the heap

  7. Our next candidate is 77

  8. It checks if there's a number less than 77 in our heap. There isn't, so we add 727^{2} to the heap and checks the next prime candidate, 11.

So on.

my question

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?

Note by Timothy Samson
1 year, 8 months ago

No vote yet
1 vote

  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:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

This 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.

Agnishom Chattopadhyay Staff - 1 year, 8 months ago

Log in to reply

nicely done

Daniel Xiang - 1 year, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...