4
\$\begingroup\$

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?

\$\endgroup\$
0
\$\begingroup\$

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())    
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Oscar Smith Oct 12 '17 at 18:37
  • \$\begingroup\$ The performance is great though. \$\endgroup\$ – Oscar Smith Oct 12 '17 at 18:37
  • \$\begingroup\$ @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. \$\endgroup\$ – juvian Oct 12 '17 at 18:48
  • \$\begingroup\$ 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 \$\endgroup\$ – Oscar Smith Oct 12 '17 at 19:44
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ is this a good implementation of what you are talking about: pastebin.com/LH0fnnfz \$\endgroup\$ – Julian Oct 12 '17 at 5:57
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Graipher Oct 12 '17 at 8:25
  • \$\begingroup\$ 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 \$\endgroup\$ – Julian Oct 12 '17 at 15:30
  • \$\begingroup\$ Also the code isn't his, which would cause problems. \$\endgroup\$ – Oscar Smith Oct 12 '17 at 15:55
  • \$\begingroup\$ 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. \$\endgroup\$ – Oscar Smith Oct 12 '17 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.