Recurrence sequence in Java / Python / Mathematica

Question

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.

Answer 1

Java

double A = 1;
int n = 0;
while (true) {
  System.out.println(n + " " + A);
  A = 1 - 1 / (A + 3);
  n++;
}

Python

A = 1.0
n = 0
while 1:
  print n, A
  A = 1 - 1 / (A + 3)
  n += 1

Answer 2

Mathematica:

a[0] := 1
a[k_] := 1 - 1/(a[k - 1] + 3)

I substituted k = n + 1 because that makes the expression simpler. The result is equivalent.

Answer 3

Mathematica

a[0] = 1;
a[n_] := a[n] = 1 - 1/(a[n-1] + 3)

(Note the memoization trick.)

Also, a[n] converges (very quickly) to sqrt(3)-1:

Solve[x == 1 - 1/(x+3), x]

Answer 4

Python

next = lambda x: 1.0 - (1.0 / (float(x) + 3.0))
last, z, count = -1, 0.0, 0
while last != z:
  print count, z
  last, z, count = z, next(z), count+1

I try to avoid writing "while True" or such if I can avoid it. Almost certainly no code that I write will loop forever. In this case, it ran sixteen times for me. Sixteen is a lot less than ℵ-null.

Answer 5

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)