# Listing all numbers that are more composite than every number less than it

This code is my first naive attempt at writing a program that lists all numbers less than a given value that are more composite (have more divisors) than any number less than that number (for example, 12 is more composite than any number less than it).

def composite_count(limit):
most_divisors = 0
for i in range(limit):
tally = 0
for j in range(i):
if not (i + 1) % (j + 1):
tally += 1
if tally > most_divisors:
most_divisors = tally


After running the program a few times, I started to see some patterns like the fact that all of the listed answers were even, that all answers greater than 12 are divisible by 12, or that all answers greater than 60 are divisible by 60. I also ran some tests involving prime factorization and found that although the more composite numbers do not always have more prime factors, the sum of their prime factors are always larger. Despite all this information I was not able to figure out any changes to the algorithm that would create significant time saves.

Here is a naive approach: We basically do a modified sieve to store for each number its lowest prime divisor, and then with that we can factorize numbers in log n complexity (I used python 3):

    import math
from operator import mul

def count_factors(num, lowest_prime_factor):
factors = {}
while (lowest_prime_factor[num] != 1):
factors[lowest_prime_factor[num]] = factors.get(lowest_prime_factor[num], 0) + 1
num = int(num / lowest_prime_factor[num])
prod = 1
for num in factors.values():
prod *= (num + 1)
return prod
def highly_composite_list(maxn):

lowest_prime_factor = [1] * (maxn + 1)

for num in range(2, maxn, 2):
lowest_prime_factor[num] = 2

for num in range(3, maxn, 2):
if lowest_prime_factor[num] == 1: # its prime
lowest_prime_factor[num] = num
for k in range(num * 2, maxn , num):
if lowest_prime_factor[k] == 1: # we havent marked lowest prime factor before
lowest_prime_factor[k] = num

composites = []
highest = 1
for num in range(2, maxn):
factors = count_factors(num, lowest_prime_factor)
if factors > highest:
composites.append(num)
highest = factors

return composites

print(highly_composite_list(1000000))


Now, reading some special properties about this numbers, we can make a much better algorithm: we generate only the possible numbers that satisfy necessary conditions to be highly composite and then we process only those to filter the ones that were really highly composite:

    low_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
MAX_N = 1
for prime in low_primes:
MAX_N *= prime
candidates = []

def count_factors_2(num):
factors = 1
idx = 0
while(num != 1):
count = 0
while (num % low_primes[idx] == 0):
count +=1
num /= low_primes[idx]
factors *= (count + 1)
idx += 1
return factors

def generate_candidates(idx, num, previous_exponent, current_exponent):
if num < MAX_N:
candidates.append(num)
if current_exponent < previous_exponent: # current exponent must be equal or less than previous one
generate_candidates(idx, num * low_primes[idx], previous_exponent, current_exponent + 1) # we either stay with current prime and increase exponent
generate_candidates(idx + 1, num * low_primes[idx + 1], current_exponent, 1) # or move to next prime

def highly_composite_list_2():

generate_candidates(0, 2, MAX_N, 1) #generate candidates that satisfy necessary conditions

composites = []
highest = 0
for num in sorted(candidates): # its important that they are sorted to know current highest number of divisors
factors = count_factors_2(num)
if factors > highest:
composites.append(num)
highest = factors
return composites

print(highly_composite_list_2())

• This code as it currently is has several big problems. Mainly, it doesn't use functions or anything similar to allow easy control of the highest number. – Oscar Smith Oct 12 '17 at 18:37
• The performance is great though. – Oscar Smith Oct 12 '17 at 18:37
• @OscarSmith feel free to offer an edit, only used to improve performance and python is not my main language. You mean MAX_N? It can me any number below the product of the primes in low_primes. It could be generalized to find the primes necessary for any n (find primes until product exceeds it), but tried to keep code with the minimum. – juvian Oct 12 '17 at 18:48
• This is the most basic fix I could come up with. The code is still messy, but it now only returns answers less than the limit – Oscar Smith Oct 12 '17 at 19:44

The biggest thing that will gain you performance is breaking this up into two functions, one that gets the prime factor list of a number, and another that computes the total number of factors from a prime factorization (using This method). Using this, we get the following

def generate_primes(end):
primes = []
for i in range(2, end):
for j in range(2, i):
if i % j == 0:
break
else:
primes.append(i)
return primes

def prime_power_generator(x, primes):
# Most of these steps will not be run.
# The largest prime iterated to will be the largest prime factor of x
# (not including x)
for p in primes:
if x % p == 0:
times = 0
while x % p == 0:
times += 1
x //= p
yield times
if x == 1:
return

def number_of_factors_with_help(x, primes):
for power in prime_power_generator(x, primes):

def better_composite_count(limit):
primes = generate_primes(int(limit**.5)+1)
most_divisors = 0
for x in range(2,limit+1,2):
num_divisors = number_of_factors_with_help(x, primes)
if num_divisors > most_divisors:
most_divisors = num_divisors


By limit=10**5, this is clearly superior, taking .02 seconds, instead of 50 for the OP. However, there is a better way. These numbers have several properties that allow much more a much faster search. For any highly compoite n, the prime factorization of n:

• contains consecutive primes starting with 2
• with decreasing frequency
• the largest prime factor has frequency 1 (except for 4 and 36)

There are very few numbers that satisfy these constraints, and computing them by their prime factorization means we don't have to factor them later. These insights leads to the following code:

def gen_primes():
D = {}
q = 2  # first integer to test for primality.

while True:
if q not in D:
# not marked composite, must be prime
yield q

#first multiple of q not already marked
D[q * q] = [q]
else:
for p in D[q]:
D.setdefault(p + q, []).append(p)
# no longer need D[q], free memory
del D[q]
q += 1

def num_factors(prime_factorization):
ans = 1
for power in prime_factorization:
ans *= power+1
return ans

def composite_candidates(primes, limit, factors=(1,), num=2, candidates=None, idx=0):
if candidates == None:
candidates={1:1, 4:3, 36:9}
if num < limit:
if factors[-1] == 1:
candidates[num] = num_factors(factors)
# current exponent must be equal or less than previous one
if len(factors) == 1 or factors[-2] > factors[-1]:
# we either stay with current prime and increase exponent
composite_candidates(primes,
limit,
factors[:-1] + (factors[-1] + 1,),
num * primes[idx],
candidates,
idx)
# or move to next prime
idx += 1
composite_candidates(primes,
limit,
factors + (1,),
num * primes[idx],
candidates,
idx)
return candidates

def best_composite_count(limit):
# primes up to the largest possible in a highly composite number
primes = []
prime_product = 1
for prime in gen_primes():
primes.append(prime)
prime_product *= prime
if prime_product > limit:
break

# generate numbers, and number of factors for numbers that might work
candidates = composite_candidates(primes, limit)
composites = []
most_divisors = 0
# its important that they are sorted to know current highest number of divisors
for num in sorted(candidates.keys()):
num_divisors = candidates[num]
if num_divisors > most_divisors:
composites.append(num)
most_divisors = num_divisors
return composites


This yields another similarly massive increase over the previous, and can sieve up to 10^30 in less than 5 seconds.

• is this a good implementation of what you are talking about: pastebin.com/LH0fnnfz – Julian Oct 12 '17 at 5:57
• @Julian That looks like it would be enough to ask a new question. I could think of a few ways to do it differently. Make sure to reference this question for context. – Graipher Oct 12 '17 at 8:25
• how would I name the question? Also how what would be different in the body of the question? If I make a new question also "Listing all numbers that are more composite than every number less than it" it will probably get flagged as a duplicate – Julian Oct 12 '17 at 15:30
• Also the code isn't his, which would cause problems. – Oscar Smith Oct 12 '17 at 15:55
• Also note that these two answers are not the same. better_count adds 1 to the answer list. I think this is probably right, but it still needs considering. – Oscar Smith Oct 12 '17 at 16:04