Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Highly composite numbers list
#!/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
# Generates a list of the hcn <= MAXN.
def gen_hcn():
primes = gen_primes()
print(primes)
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))
for e in range(1, e_max+1):
n = el[0]
div = el[1]
exponents = el[2].copy()
n *= pow(primes[i], e)
div *= e+1
exponents.append(e)
if n > MAXN: break
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")
primes = gen_primes()
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)
Number of candidates for being highly composite is 32749
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
@tuckcodes

This comment has been minimized.

Copy link

tuckcodes commented May 8, 2018

This is cool. Thank you!

@SecondThread

This comment has been minimized.

Copy link

SecondThread commented Jul 7, 2018

Cool program, thanks

@andr14142

This comment has been minimized.

Copy link

andr14142 commented Oct 29, 2018

Last 11 HCNs in this table are incorrect because of 64 bit grid overflow. Correct 11 latest HCNs are:
146: 74801040398884800 64512
147: 106858629141264000 65536
148: 112201560598327200 69120
149: 149602080797769600 73728
150: 224403121196654400 80640
151: 299204161595539200 82944
152: 374005201994424000 86016
153: 448806242393308800 92160
154: 673209363589963200 96768
155: 748010403988848000 98304
156: 897612484786617600 103680
The mistake may be corrected with the integer division instead of multiplying in rows 16-23:

     n = 1
    div = 1
    quotient = MAXN
    for i in range(l):
            n *= pow(primes[i], exponents[i])
            div *= exponents[i]+1
            quotient //= pow(primes[i], exponents[i])
   if quotient == 0: 
            return
@weskerhluffy

This comment has been minimized.

Copy link

weskerhluffy commented Nov 14, 2018

god bless you

@dario2994

This comment has been minimized.

Copy link
Owner Author

dario2994 commented Aug 23, 2019

Fixed some errors in the table (as pointed out by @andr14142).
The reason of the mistake is not the one suggested by @andr14142 as in python there is no integer overflow. In particular executing the program on my computer generates exactly the same list as @andr14142. Maybe when I created the list of highly composite numbers I used a different script (in C++) that had some overflow issues.

@Thatyougoon

This comment has been minimized.

Copy link

Thatyougoon commented Dec 20, 2019

Awesome needed this for a project of mine. Many thanks!

@LoneRanger9000

This comment has been minimized.

Copy link

LoneRanger9000 commented Jun 22, 2020

nice

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.