Skip to content

Instantly share code, notes, and snippets.

@dario2994

dario2994/generate_hcn.py

Last active January 22, 2024 15:54
Show Gist options
  • Star 52 You must be signed in to star a gist
  • Fork 5 You must be signed in to fork a gist
  • Save dario2994/fb4713f252ca86c1254d to your computer and use it in GitHub Desktop.
Save dario2994/fb4713f252ca86c1254d to your computer and use it in GitHub Desktop.
Download ZIP
Highly composite numbers list
Raw
generate_hcn.py
#!/usr/bin/env python3
# This program prints all hcn (highly composite numbers) <= MAXN (=10**18)
#
# The value of MAXN can be changed arbitrarily. When MAXN = 10**100, the
# program needs less than one second to generate the list of hcn.
from math import log
MAXN = 10**18
# Generates a list of the first primes (with product > MAXN).
def gen_primes():
primes = []
primes_product = 1
for n in range(2, 10**10):
is_prime = True
for i in range(2, n):
if n % i == 0:
is_prime = False
if is_prime:
primes.append(n)
primes_product *= n
if primes_product > MAXN: break
return primes
primes = gen_primes()
# Generates a list of the hcn <= MAXN.
def gen_hcn():
# List of (number, number of divisors, exponents of the factorization)
hcn = [(1, 1, [])]
for i in range(len(primes)):
new_hcn = []
for el in hcn:
new_hcn.append(el)
if len(el[2]) < i: continue
e_max = el[2][i-1] if i >= 1 else int(log(MAXN, 2))
n = el[0]
for e in range(1, e_max+1):
n *= primes[i]
if n > MAXN: break
div = el[1] * (e+1)
exponents = el[2] + [e]
new_hcn.append((n, div, exponents))
new_hcn.sort()
hcn = [(1, 1, [])]
for el in new_hcn:
if el[1] > hcn[-1][1]: hcn.append(el)
return hcn
hcn = gen_hcn()
# From here on is only pretty printing.
print("Number of highly composite numbers less than", MAXN, "is", len(hcn),"\n")
def PrintWithCorrectSpaces(a, b, c):
aspace = int(log(MAXN, 10)) + 5
bspace = int(log(hcn[-1][1], 10)) + 5
assert(len(a) < aspace)
assert(len(b) < bspace)
print(a, " "*(aspace-len(a)), b, " "*(bspace-len(b)), c)
PrintWithCorrectSpaces("number", "divisors", "factorization")
for el in hcn:
factorization = "*".join([str(primes[i])+("^"+str(el[2][i]) if el[2][i]>1 else "") for i in range(len(el[2]))])
PrintWithCorrectSpaces(str(el[0]), str(el[1]), factorization)
Raw
list.txt
Number of highly composite numbers less than 1000000000000000000 is 156
number divisors factorization
1 1
2 2 2
4 3 2^2
6 4 2*3
12 6 2^2*3
24 8 2^3*3
36 9 2^2*3^2
48 10 2^4*3
60 12 2^2*3*5
120 16 2^3*3*5
180 18 2^2*3^2*5
240 20 2^4*3*5
360 24 2^3*3^2*5
720 30 2^4*3^2*5
840 32 2^3*3*5*7
1260 36 2^2*3^2*5*7
1680 40 2^4*3*5*7
2520 48 2^3*3^2*5*7
5040 60 2^4*3^2*5*7
7560 64 2^3*3^3*5*7
10080 72 2^5*3^2*5*7
15120 80 2^4*3^3*5*7
20160 84 2^6*3^2*5*7
25200 90 2^4*3^2*5^2*7
27720 96 2^3*3^2*5*7*11
45360 100 2^4*3^4*5*7
50400 108 2^5*3^2*5^2*7
55440 120 2^4*3^2*5*7*11
83160 128 2^3*3^3*5*7*11
110880 144 2^5*3^2*5*7*11
166320 160 2^4*3^3*5*7*11
221760 168 2^6*3^2*5*7*11
277200 180 2^4*3^2*5^2*7*11
332640 192 2^5*3^3*5*7*11
498960 200 2^4*3^4*5*7*11
554400 216 2^5*3^2*5^2*7*11
665280 224 2^6*3^3*5*7*11
720720 240 2^4*3^2*5*7*11*13
1081080 256 2^3*3^3*5*7*11*13
1441440 288 2^5*3^2*5*7*11*13
2162160 320 2^4*3^3*5*7*11*13
2882880 336 2^6*3^2*5*7*11*13
3603600 360 2^4*3^2*5^2*7*11*13
4324320 384 2^5*3^3*5*7*11*13
6486480 400 2^4*3^4*5*7*11*13
7207200 432 2^5*3^2*5^2*7*11*13
8648640 448 2^6*3^3*5*7*11*13
10810800 480 2^4*3^3*5^2*7*11*13
14414400 504 2^6*3^2*5^2*7*11*13
17297280 512 2^7*3^3*5*7*11*13
21621600 576 2^5*3^3*5^2*7*11*13
32432400 600 2^4*3^4*5^2*7*11*13
36756720 640 2^4*3^3*5*7*11*13*17
43243200 672 2^6*3^3*5^2*7*11*13
61261200 720 2^4*3^2*5^2*7*11*13*17
73513440 768 2^5*3^3*5*7*11*13*17
110270160 800 2^4*3^4*5*7*11*13*17
122522400 864 2^5*3^2*5^2*7*11*13*17
147026880 896 2^6*3^3*5*7*11*13*17
183783600 960 2^4*3^3*5^2*7*11*13*17
245044800 1008 2^6*3^2*5^2*7*11*13*17
294053760 1024 2^7*3^3*5*7*11*13*17
367567200 1152 2^5*3^3*5^2*7*11*13*17
551350800 1200 2^4*3^4*5^2*7*11*13*17
698377680 1280 2^4*3^3*5*7*11*13*17*19
735134400 1344 2^6*3^3*5^2*7*11*13*17
1102701600 1440 2^5*3^4*5^2*7*11*13*17
1396755360 1536 2^5*3^3*5*7*11*13*17*19
2095133040 1600 2^4*3^4*5*7*11*13*17*19
2205403200 1680 2^6*3^4*5^2*7*11*13*17
2327925600 1728 2^5*3^2*5^2*7*11*13*17*19
2793510720 1792 2^6*3^3*5*7*11*13*17*19
3491888400 1920 2^4*3^3*5^2*7*11*13*17*19
4655851200 2016 2^6*3^2*5^2*7*11*13*17*19
5587021440 2048 2^7*3^3*5*7*11*13*17*19
6983776800 2304 2^5*3^3*5^2*7*11*13*17*19
10475665200 2400 2^4*3^4*5^2*7*11*13*17*19
13967553600 2688 2^6*3^3*5^2*7*11*13*17*19
20951330400 2880 2^5*3^4*5^2*7*11*13*17*19
27935107200 3072 2^7*3^3*5^2*7*11*13*17*19
41902660800 3360 2^6*3^4*5^2*7*11*13*17*19
48886437600 3456 2^5*3^3*5^2*7^2*11*13*17*19
64250746560 3584 2^6*3^3*5*7*11*13*17*19*23
73329656400 3600 2^4*3^4*5^2*7^2*11*13*17*19
80313433200 3840 2^4*3^3*5^2*7*11*13*17*19*23
97772875200 4032 2^6*3^3*5^2*7^2*11*13*17*19
128501493120 4096 2^7*3^3*5*7*11*13*17*19*23
146659312800 4320 2^5*3^4*5^2*7^2*11*13*17*19
160626866400 4608 2^5*3^3*5^2*7*11*13*17*19*23
240940299600 4800 2^4*3^4*5^2*7*11*13*17*19*23
293318625600 5040 2^6*3^4*5^2*7^2*11*13*17*19
321253732800 5376 2^6*3^3*5^2*7*11*13*17*19*23
481880599200 5760 2^5*3^4*5^2*7*11*13*17*19*23
642507465600 6144 2^7*3^3*5^2*7*11*13*17*19*23
963761198400 6720 2^6*3^4*5^2*7*11*13*17*19*23
1124388064800 6912 2^5*3^3*5^2*7^2*11*13*17*19*23
1606268664000 7168 2^6*3^3*5^3*7*11*13*17*19*23
1686582097200 7200 2^4*3^4*5^2*7^2*11*13*17*19*23
1927522396800 7680 2^7*3^4*5^2*7*11*13*17*19*23
2248776129600 8064 2^6*3^3*5^2*7^2*11*13*17*19*23
3212537328000 8192 2^7*3^3*5^3*7*11*13*17*19*23
3373164194400 8640 2^5*3^4*5^2*7^2*11*13*17*19*23
4497552259200 9216 2^7*3^3*5^2*7^2*11*13*17*19*23
6746328388800 10080 2^6*3^4*5^2*7^2*11*13*17*19*23
8995104518400 10368 2^8*3^3*5^2*7^2*11*13*17*19*23
9316358251200 10752 2^6*3^3*5^2*7*11*13*17*19*23*29
13492656777600 11520 2^7*3^4*5^2*7^2*11*13*17*19*23
18632716502400 12288 2^7*3^3*5^2*7*11*13*17*19*23*29
26985313555200 12960 2^8*3^4*5^2*7^2*11*13*17*19*23
27949074753600 13440 2^6*3^4*5^2*7*11*13*17*19*23*29
32607253879200 13824 2^5*3^3*5^2*7^2*11*13*17*19*23*29
46581791256000 14336 2^6*3^3*5^3*7*11*13*17*19*23*29
48910880818800 14400 2^4*3^4*5^2*7^2*11*13*17*19*23*29
55898149507200 15360 2^7*3^4*5^2*7*11*13*17*19*23*29
65214507758400 16128 2^6*3^3*5^2*7^2*11*13*17*19*23*29
93163582512000 16384 2^7*3^3*5^3*7*11*13*17*19*23*29
97821761637600 17280 2^5*3^4*5^2*7^2*11*13*17*19*23*29
130429015516800 18432 2^7*3^3*5^2*7^2*11*13*17*19*23*29
195643523275200 20160 2^6*3^4*5^2*7^2*11*13*17*19*23*29
260858031033600 20736 2^8*3^3*5^2*7^2*11*13*17*19*23*29
288807105787200 21504 2^6*3^3*5^2*7*11*13*17*19*23*29*31
391287046550400 23040 2^7*3^4*5^2*7^2*11*13*17*19*23*29
577614211574400 24576 2^7*3^3*5^2*7*11*13*17*19*23*29*31
782574093100800 25920 2^8*3^4*5^2*7^2*11*13*17*19*23*29
866421317361600 26880 2^6*3^4*5^2*7*11*13*17*19*23*29*31
1010824870255200 27648 2^5*3^3*5^2*7^2*11*13*17*19*23*29*31
1444035528936000 28672 2^6*3^3*5^3*7*11*13*17*19*23*29*31
1516237305382800 28800 2^4*3^4*5^2*7^2*11*13*17*19*23*29*31
1732842634723200 30720 2^7*3^4*5^2*7*11*13*17*19*23*29*31
2021649740510400 32256 2^6*3^3*5^2*7^2*11*13*17*19*23*29*31
2888071057872000 32768 2^7*3^3*5^3*7*11*13*17*19*23*29*31
3032474610765600 34560 2^5*3^4*5^2*7^2*11*13*17*19*23*29*31
4043299481020800 36864 2^7*3^3*5^2*7^2*11*13*17*19*23*29*31
6064949221531200 40320 2^6*3^4*5^2*7^2*11*13*17*19*23*29*31
8086598962041600 41472 2^8*3^3*5^2*7^2*11*13*17*19*23*29*31
10108248702552000 43008 2^6*3^3*5^3*7^2*11*13*17*19*23*29*31
12129898443062400 46080 2^7*3^4*5^2*7^2*11*13*17*19*23*29*31
18194847664593600 48384 2^6*3^5*5^2*7^2*11*13*17*19*23*29*31
20216497405104000 49152 2^7*3^3*5^3*7^2*11*13*17*19*23*29*31
24259796886124800 51840 2^8*3^4*5^2*7^2*11*13*17*19*23*29*31
30324746107656000 53760 2^6*3^4*5^3*7^2*11*13*17*19*23*29*31
36389695329187200 55296 2^7*3^5*5^2*7^2*11*13*17*19*23*29*31
48519593772249600 57600 2^9*3^4*5^2*7^2*11*13*17*19*23*29*31
60649492215312000 61440 2^7*3^4*5^3*7^2*11*13*17*19*23*29*31
72779390658374400 62208 2^8*3^5*5^2*7^2*11*13*17*19*23*29*31
74801040398884800 64512 2^6*3^3*5^2*7^2*11*13*17*19*23*29*31*37
106858629141264000 65536 2^7*3^3*5^3*7*11*13*17*19*23*29*31*37
112201560598327200 69120 2^5*3^4*5^2*7^2*11*13*17*19*23*29*31*37
149602080797769600 73728 2^7*3^3*5^2*7^2*11*13*17*19*23*29*31*37
224403121196654400 80640 2^6*3^4*5^2*7^2*11*13*17*19*23*29*31*37
299204161595539200 82944 2^8*3^3*5^2*7^2*11*13*17*19*23*29*31*37
374005201994424000 86016 2^6*3^3*5^3*7^2*11*13*17*19*23*29*31*37
448806242393308800 92160 2^7*3^4*5^2*7^2*11*13*17*19*23*29*31*37
673209363589963200 96768 2^6*3^5*5^2*7^2*11*13*17*19*23*29*31*37
748010403988848000 98304 2^7*3^3*5^3*7^2*11*13*17*19*23*29*31*37
897612484786617600 103680 2^8*3^4*5^2*7^2*11*13*17*19*23*29*31*37
@BullHunter3
Copy link

This has helped me a lot with investigating algorithms to generate highly composite numbers.

I suggest making two changes to further optimize this script:

  1. Move generating primes from line 28 to just before def gen_hcn and removing line 68, primes = gen_primes() as it then is unneeded.
  2. Move line 44, if n > MAXN: break, to after line 41 to eliminate having to unnecessarily calculate div and appending exponents.

FYI:
Your method is about 10 times faster than the Saino and Saino algorithm (implemented in Python). Their paper can be found at: http://wwwhomes.uni-bielefeld.de/achim/julianmanuscript3.pdf

@EntityPlantt
Copy link

Thank you very much! 🤗 It helped me a lot to decide whether my idea of dynamic programming fits for the problem Six (EJOI 2017).
A little bit sad that it is in only one language, may write it in C++ or JS later

@GithubUserNotABot
Copy link

GithubUserNotABot commented Aug 2, 2023 via email

@ivanovmp
Copy link

I rewrote it in C++. Impressive, it is really fast!

https://godbolt.org/z/hxavf6sP9

@BullHunter3
Copy link

Neat! I may have to revisit the Highly Composite Number problem space.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment