Recurrence sequence in Java / Python / Mathematica

java, python, sequence, wolfram-mathematica

Solution

Python, simplest:

def a(n):
  if n == 0: return 1
  return 1 - 1 / float(a(n-1) + 3)

# limit is sqrt(3) - 1
limit = 3.0 ** 0.5 - 1.0

# get 9 digits' precision
i = 0
while abs(a(i) - limit) > 1.0e-9:
  i += 1

print i

This emits `8`, suggesting that optimizations such as recursion elimination or memoizing are likely not warranted.

Of course normally we'd want to get the limit numerically rather than analytically, so the normal way to loop would be rather different -- and best encapsulated in a higher-order function...:

# get a function's limit numerically
def limit(f, eps=1.0e-11):
  previous_value = f(0)
  next_value = f(1)
  i = 2
  while abs(next_value - previous_value) > eps:
    previous_value = next_value
    next_value = f(i)
    i += 1
  return next_value

Nontrivial looping logic is usually best encapsulated in a generator:

def next_prev(f):
  previous_value = f(0)
  i = 1
  while True:
    next_value = f(i)
    yield next_value, previous_value
    i += 1
    previous_value = next_value

with the help of this generator, the `limit` HOF becomes much simpler:

def limit(f, eps=1.0e-11):
  for next_value, previous_value in next_prev(f):
    if abs(next_value - previous_value) < eps:
      return next_value

Note how useful the separation is: `next_prev` embodies the concept of "get the next and previous value of the function", `limit` just deals with "when should the loop terminate".

Last but not least, itertools often offers a good alternative to generators, letting you encapsulate finicky iteration logic in speedy ways (though it does take some getting used to...;-):

import itertools

def next_prev(f):
  values = itertools.imap(f, itertools.count())
  prv, nxt = itertools.tee(values)
  nxt.next()
  return itertools.izip(prv, nxt)

Problem

How can you write the following statement in the given languages? ``` a(0) = 1 a_(n+1) = 1 - 1 / ( a_n + 3) ``` I need to find the smallest value of `n` when `a_n -> 0.732050...`. My attempt in Mathematica ``` a[(x+1)_] = 1 - 1/(a[x_] + 3) ``` The problem is apparently in this `a[(x+1)_]`. However, I do not know how to do it iteratively in Mathematica.

Original source

Related problems