This problem is pretty tricky and I wasted all my time on it. At first I simply
used Haskell's Double type and unfortunately the precision is not even enough
for the small data set.

Let p = 3 + /5
    q = 3 - /5

First I tried to work out the recurrence. Let p^n = a_n + b_n * /5, a_n and b_n
are integers. We have:
  a_1 = 3, b_1 = 1
  a_n = 3 * a_(n-1) + 5 * b_(n-1), b_n = a_(n-1) + 3 * b_(n-1)

a_n and b_n are easy to solve. The problem is that to find out the integer
digits of (b_n * /5), we need arbitrarily precise floating arithmetic! :-(

It was after I read about discussions on google group and the solution of Reid
(rank 4) that I finally understood the solution.

Let y_n = p^n + q^n
    x_n = y_n - 1

We need the answer for p^n, but why are we looking at y_n? Because 0 < q^n < 1.
Furthermore, from the binomial theorem we know that /5 will be cancelled out in
y_n. Therefore, y_n is an integer, and so x_n is the answer we are looking at!

Next, we should work out a recurrence for y_n. Let's square it and see what happens. 

(y_n)^2 = p^(2n) + q^(2n) + 2 * (pq)^n
        = y_(2n) + 2 * (4^n)
        = y_(2n) + 2 * 2^(2n)
There we have it for even numbers, y_(2n) = (y_n)^2 - 2 * 2^(2n)        

y_n * y_(n+1) = p^(2n+1) + q^(2n+1) + (p+q) * (pq)^n
              = y_(2n+1) + 6 * 2^(2n)
              = y_(2n+1) + 3 * 2^(2n+1)
There we have it for odd numbers, y_(2n+1) = y_n * y_(n+1) - 3 * 2^(2n+1)

The time complexity is log(n).

=======================================================

Other people noted that for y_n = (3 + /5)^n + (3 - /5)^n,
y_(n+2) = 6y_(n+1) - 4y_n

This just looks like the Fibonacci numbers, doesn't it? In fact, we can use
matrix to solve it within log(n) time, just like
http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form