Recurrence sequence in Java / Python / Mathematica

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)

开发者_StackOverflow社区

The problem is apparently in this a[(x+1)_]. However, I do not know how to do it iteratively in Mathematica.

---

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]

---

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)

---

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

---

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.

---

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.

---

A one-liner in Mathematica which gives a list of exact elements of your sequence:

In[66]:= NestWhileList[1 - 1/(#1 + 3) &, 1, 
 RealExponent[Subtract[##]] > -8 &, 2]

Out[66]= {1, 3/4, 11/15, 41/56, 153/209, 571/780, 2131/2911, \
7953/10864, 29681/40545}

The difference between the last two elements is less than 10^-8. It thus have taken 8 iterations:

In[67]:= Length[%]

Out[67]= 9