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

Question

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):
    answer = []
    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
            answer.append((i + 1))
    return answer

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.

Can someone please help me make this code meaningfully faster?

Answer 1

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())    

Answer 2

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):
    answer = 1
    for power in prime_power_generator(x, primes):
        answer *= power+1
    return answer

def better_composite_count(limit):
    answer = [1]
    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
            answer.append(x)
    return answer

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.