Last Friday, I participated in the Google Code Jam, a programming puzzle contest sponsored by Google. It was the first qualification round, and I was very happy with how I did, coming in 74th in my heat (there were three heats, and mine had almost 3000 participants).

There were three problems, each with two data sets. The last problem was really more of a math problem, which I figured would have given me more of an edge because most of the time when I cheat on my second love, computers, it’s with my first love, math. However, I couldn’t complete it in the time allotted. But I also couldn’t stop thinking about it. I eventually came up with a solution which I’ll share here.

It’s problem C in round 1A (start here), but essentially, you have to find the last three digits before the decimal point for the number (3 + √5)^{n} where n is a whole number that can be very large (up to two billion).

This means you cannot calculate the whole thing; it would contain several hundred million digits, which would use most of RAM just to hold the representation. So you have to figure out a trick.

Here’s what I came up with (too late to submit). Let A_{n} = (3 + √5)^{n} and B_{n} = (3 – √5)^{n}. Observe that A_{n} = X_{n} + Y_{n}√5 for some series X_{0}, X_{1}, … and Y_{0}, Y_{1}, … where each of X_{n} and Y_{n} are whole numbers. You can show this easily by induction. You can show a similar thing for B_{n}; in fact, B_{n} = X_{n} – Y_{n}√5.

This means that A_{n}+B_{n} = 2X_{n}.

Notice that (3 – √5) < 1, so B_{n} < 1 for n>1, and goes towards 0 very quickly. Since A_{n} = 2X_{n} – B_{n}, we can calculate A_{n} by calculating 2X_{n} and subtracting a “small” number… that is, the last three digits of A_{n} are the same as the last three digits of 2X_{n}-1.

So all we need to do is figure out X_{n}!

We know that X_{0} = 1, Y_{0} = 0. A_{n+1} = A_{n}(3 + √5), so

X_{n+1} + Y_{n+1}√5 = A_{n+1} = A_{n}(3 + √5) = (X_{n} + Y_{n}√5)(3 + √5) = (3X_{n}+5Y_{n})+√5(X_{n}+3Y_{n})

so separating rational and irrational parts yields the pretty recurrence relation X_{n+1} = 3X_{n} + 5Y_{n} and Y_{n+1} = X_{n}+3Y_{n}.

That means X_{n+1} and Y_{n+1} depend only upon X_{n} and Y_{n}. Since we only care about the last three digits, that means that there are only 1000*1000=a million different combinations of X_{n}, Y_{n}, and thus, the series must repeat in fewer than a million iterations. It shouldn’t be too hard to find a repeat.

Here’s the Python code to find the cycle length:

def _a_b_n(n):
if n == 0:
return 3,1
a,b = a_b_n(n-1)
return ((3*a+5*b) % 1000, (a+3*b) % 1000)
CACHE={}
def a_b_n(n):
if not CACHE.has_key(n):
CACHE[n] = _a_b_n(n)
return CACHE[n]
F={}
for i in xrange(int(1e6)):
k = (Xn, Yn) = a_b_n(i)
#print i, a, b, (2*a-1)%1000
if F.has_key(k):
#print "repeat: %d, %d" % (i,F[k])
break
F[k] = i
cycle_length = i-F[k]
print "cycle length is", cycle_length

When you run this, it takes less than a tenth of a second to figure out that the cycle length is 500, and A_{503}, B_{503} = A_{3}, B_{3}. So now it’s easy! Calculating the first 503 terms is enough.

Here is the rest of the code:

def do_trial(f):
n = int(f.readline())
if n>cycle_length:
n %= cycle_length
n += cycle_length
t = a_b_n(n-1)
return (2*t[0]-1) % 1000
f = sys.stdin
count = int(f.readline())
for i in xrange(count):
v = do_trial(f)
print "Case #%d: %03d" % (i+1, v)

It runs in pretty much no time at all, thanks to the excessive caching.