Posts Tagged ‘divisors’

Problem 21

Tuesday, March 3rd, 2009

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

?View Code PYTHON
def proper_divisors(n):
  """
  Find all divisors of n by trial division
  """
  divisors = set([1])
  for i in range(2, math.ceil(n ** 0.5)+1):
      if n % i == 0:
        divisors.add(i)
        divisors.add(n/i)
  return divisors
 
def amicable_numbers(n):
  candidates = range(1,n)
  amicables = []
  for a in candidates:
    b = sum(proper_divisors(a))
    if a != b \
        and sum(proper_divisors(a)) == b \
        and sum(proper_divisors(b)) == a:
      amicables.append(a)
      amicables.append(b)
      candidates.remove(b)
  return amicables
 
>>> sum(amicable_numbers(10000))
31626

Tags: , , , , ,
Posted in amicable numbers | No Comments »

Problem 12

Tuesday, February 10th, 2009

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:


1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Iterators again.

?View Code PYTHON
import math
 
def divisors(n):
  """
  Find all divisors of n by trial division
  """
  divisors = set([1])
  for i in range(1, math.ceil(n ** 0.5)+1):
      if n % i == 0:
        divisors.add(i)
        divisors.add(n/i)
  return divisors
 
class Triangle:
  def __init__(self):
    self.count = 1
    self.sum = 0
  def __iter__(self):
    return self
  def next(self):
    self.sum += self.count
    self.count += 1
    return self.sum
 
def problem12(n):
  t = Triangle()
  while True:
    x = t.next()
    num = len(divisors(x))
    if num > n:
      return x, num
 
>>> problem12(500)
problem12 took 6172.000 ms
(76576500, 576)

Tags: , , , , , ,
Posted in factors | No Comments »