Posts Tagged ‘iterator’

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 »

Problem 25

Thursday, February 5th, 2009

“The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?
“

It is possible to do this mathematically, but I brute forced this one for the chance to implement a Fibonacci iterator (used a Fibonacci generator back in Problem 2).

?View Code PYTHON
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Fibonacci:
  "Iterator for fibonacci sequence"
  def __init__(self):
    self.first = 1
    self.second = 1
    self.counter = 0
  def __iter__(self):
    return self
  def count(self):
    return self.counter
  def next(self):
    self.current = self.first
    self.first = self.second
    self.second = self.current + self.first
    self.counter += 1
    return self.current
 
def problem25(n):
  f = Fibonacci()
  while True:
    x = f.next()
    xlength = len(str(x))
    if xlength == n:
      return f.count()
 
>>> problem25(1000)
4782

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