Code to find counterexamples to Matthew Daly's conjecture at Math Stack Exchange question 3529219.
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 code was adapted from dario2994/generate_hcn.py | |
# https://gist.github.com/dario2994/fb4713f252ca86c1254d?signup=true | |
# It outputs counterexamples to Matthew Daly's highly composite number... | |
# ... conjecture at Math Stack Exchange question 3529219 that are below MAXN | |
# 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**200 | |
# 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() | |
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 this point on is Jam's code from 2020-01-31 | |
primes = gen_primes() | |
DalyConjecture = [] #predicates of whether Daly's conjecture is true for the n'th HCN | |
rawhcn = [] #previous set of HCN stripped down to only numbers, w/o excess information | |
print('index of hcn','hcn','primes dividing hcn') | |
for el in hcn: | |
rawhcn.append(el[0]) | |
for el in hcn: | |
n=hcn.index(el)+1 #the index of the HCN, el[0], in the set of HCN | |
if n==1: | |
DalyConjecture.append((n,0)) | |
Factorization = [] #the prime factors of el up to multiplicity | |
x=el[0] #for each highly composite number | |
for i in range(len(el[2])): #for each power of primes in the prime factorization of x | |
if el[2][i]>=1 and len(DalyConjecture)<n: #if the prime is present in the factorization of x | |
#but no relevant prime divisor has yet been found | |
y=x//primes[i] | |
if y in rawhcn: #if the x divided by the prime is also a HCN | |
DalyConjecture.append((n,1)) #the proposition is true for x and included in the list as 1 | |
Factorization.append(primes[i]) #include the prime in the list of prime factors of x | |
if len(DalyConjecture)<n: #if there was no prime that divided x | |
DalyConjecture.append((n,0)) #the proposition is false and included in list as 0 | |
print(n,x,Factorization) | |
print('---') |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment