Jan

16

Summing numbers that cannot be written as a sum of two abundant numbers

Filed Under hisabati, project euler by  

Problem 23 from Project Euler asks for the sum of numbers that cannot be written as the sum of two abundant numbers:

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number whose proper divisors are less than the number is called deficient and a number whose proper divisors exceed the number is called abundant.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

When I read the problem, the requirements seemed to be pretty straight-forward. We need to find all the abundant numbers in the range so that we can determine all the numbers that are the sum of two abundant numbers. My first(naive) approach to this was terribly inefficient – it ran for hours and didn’t give the right answer. We cannot get around the need to determine the abundant numbers in range. However, we can reduce the search space when determining the numbers that are expressed as sums of two abundant numbers. To do this, we take advantage of some known properties:

  1. The upper bound for numbers that cannot be expressed as the sum of two numbers is actually 20161 not 28123 (as shown here).
  2. All even numbers greater than 48 can be written as the sum of two abundant numbers (also shown in the article here).

With these facts in mind, we are ready for the implementation. The first routine determines the abundant numbers in range.

  1: def abundant_nums_in_range(n):
  2:     abundant=[]
  3:     min_abundant_not_multiple_of_2_or_3 = 5391411025
  4:     for i in range(1,n):
  5:         if(i < min_abundant_not_multiple_of_2_or_3):
  6:             if(i % 2 != 0) and (i%3 != 0):
  7:                 continue
  8:         divisors = proper_divisors(i)
  9:         divisors_sum = 0
 10:         for d in divisors:
 11:             divisors_sum += d
 12:         if(divisors_sum > i):
 13:             abundant.append(i)
 14:     return abundant
 15:

The routine that determines proper divisors of a number tests divisors from 1 to the square-root of the number and extracts all divisors in pairs.

  1: def proper_divisors(n):
  2:     divisors =[]
  3:     maxValue = int(sqrt(n))+1
  4:     for i in range(1,maxValue):
  5:         if(n % i == 0):
  6:             if(i not in divisors):
  7:                 divisors.append(i)
  8:             quotient = n/i
  9:             if(quotient == n): continue
 10:             if(quotient not in divisors):
 11:                 divisors.append(quotient)
 12:     return divisors
 13:

The main routine for the solution is the method that determines all numbers in range that can be expressed as sum of two numbers. Since we know that all even numbers greater than 48 are in our target set, we only need to determine odd numbers in range. The only way to get an odd number by summing two numbers is to sum an even number with an odd.

  1: def abundant_pair_sums_in_range(n):
  2:     abundant_nums = abundant_nums_in_range(n)
  3:     even_abundants = []
  4:     odd_abundants = []
  5:     for a in abundant_nums:
  6:         if(a %2 == 0):
  7:             even_abundants.append(a)
  8:         else:
  9:             odd_abundants.append(a)
 10:     abundant_sum_nums = []
 11:     num_even_abundants = len(even_abundants)
 12:     num_odd_abundants = len(odd_abundants)
 13:     curr_num = 0
 14:     abundant_nums_filter = [0 for x in range(0,n)]
 15:     # all even numbers >48 are the sum of two abundants
 16:     for a in range(0,n):
 17:         if(a % 2 ==0):
 18:             if(a > 48):
 19:                 abundant_nums_filter[a] = 1
 20:             elif a in [24,30,32,36,38,40,42,44,48]:
 21:                 abundant_nums_filter[a] = 1
 22:     for i in range(0, num_even_abundants):
 23:         for j in range(0, num_odd_abundants):
 24:             curr_num = even_abundants[i] + odd_abundants[j]
 25:             if(curr_num < n):
 26:                 abundant_nums_filter[curr_num] = 1
 27:     for a in range(1,n):
 28:         if abundant_nums_filter[a] == 1 :
 29:             abundant_sum_nums.append(a)
 30:     return abundant_sum_nums
 31:

The last routine ties all operations together.

  1: def get_non_abundant_sums(n):
  2:     abundant_sums = abundant_pair_sums_in_range(n)
  3:     sum_all = sum([x for x in range(0,n)])
  4:     sum_abundants = sum(abundant_sums)
  5:     return (sum_all - sum_abundants)
  6:

Comments

Comments are closed.