-
-
Save dario2994/fb4713f252ca86c1254d to your computer and use it in GitHub Desktop.
| #!/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) |
| 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 |
This program is wonderful ... and it helps me realize how much I do not yet understand about Python.
I'm 72, and starting in 1977, I was a professional and educational BASIC programmer. If you know someone who enjoyed playing a 16K Star Trek program on the Radio Shack TRS-80 Model One Level One way back then, I was the author, though most people did not know because a most prolific pirate (founder/president of St Louis Users Group) proudly bragged to me that he took my name out of the program so that it would no longer be copyrighted. (You can see me playing my program on page 9 of the October 1978 INTERCOM magazine posted here:
https://www.radioshackcatalogs.com/flipbook/hep_intercom_1978_10.html
I still think in BASIC then translate into Python as I try to write new programs, and the program I wrote (for fun) took nine hours to get to the 89th HCN.
I'd love to understand your logic better. Do you have a copy of your program that is commented or includes documentation? And if not, can you point me to some readings that would help me learn what some of your techniques accomplish?
Finally, I started my version of the program (and later sought out better programs, and yours is the best) because of a question over on Quora. May I post a link to your program that allows people to run the program on ProgramIZ?
I made two changes ... I added a list of exponents because I think it looks slightly nicer, removed the asterisks, used an input statement for number of digits in the longest number, and repeated the number of HCN's at the bottom. Here are the last few lines of a recent run:
< copy >
627358099380321608032228919424000 38928384 2¹⁰ 3⁵ 5³ 7² 11² 13¹ 17¹ 19¹ 23¹ 29¹ 31¹ 37¹ 41¹ 43¹ 47¹ 53¹ 59¹ 61¹ 67¹
674885228121255063186185655744000 39321600 2⁹ 3⁴ 5³ 7² 11¹ 13¹ 17¹ 19¹ 23¹ 29¹ 31¹ 37¹ 41¹ 43¹ 47¹ 53¹ 59¹ 61¹ 67¹ 71¹
679637940995348408701581329376000 39813120 2⁸ 3⁴ 5³ 7² 11² 13² 17¹ 19¹ 23¹ 29¹ 31¹ 37¹ 41¹ 43¹ 47¹ 53¹ 59¹ 61¹ 67¹
927967188666725711881005276648000 41287680 2⁶ 3⁴ 5³ 7² 11² 13¹ 17¹ 19¹ 23¹ 29¹ 31¹ 37¹ 41¹ 43¹ 47¹ 53¹ 59¹ 61¹ 67¹ 71¹
Number of highly composite numbers less than 10^33 is 330
< / copy >
Yes, I made sure to give you credit in the program listing and at the top of the program output.
Here's my copy of your program:
https://programiz.pro/ide/python/K7WD9FRIDQ
If you object, I will change it back to my very slow program.
and I mention your program (at long last) in this answer:
Neat! I may have to revisit the Highly Composite Number problem space.