Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Code to find counterexamples to Matthew Daly's conjecture at Math Stack Exchange question 3529219.
#!/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