Highly composite numbers list
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 |
Cool program, thanks
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
god bless you
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.
Awesome needed this for a project of mine. Many thanks!
nice
This was very helpful. Thanks a lot!
This has helped me a lot with investigating algorithms to generate highly composite numbers.
I suggest making two changes to further optimize this script:
- Move generating primes from line 28 to just before def gen_hcn and removing line 68, primes = gen_primes() as it then is unneeded.
- 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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This is cool. Thank you!