Fun with Functions I

The last three digits of F are 024 .

Solution 1: Use iteration to compute each element in the sequence until you reach the 1000th one. Note: You only have to keep track of the last 3 digits of each element, because the higher order digits do not affect the results of multiplication and addition on the last 3 digits.

# Python: Iteration
def iter_fun(x):
    if (x==0): 
        return 24
    if (x==1):
        return 42

    c = 2
    answer = 0
    minus1 = 42
    minus2 = 24

    while (c <=x):
        # calculate fun(c) based on the previous two terms, store result in answer
        # we only need the last 3 digits of the answer, so mod 1000
        answer = (c * minus1 + minus2) % 1000

        # update minus1, minus2, and c for the next iteration
        minus2 = minus1
        minus1 = answer
        c +=1

    return answer

print iter_fun(1000)

Solution 2 : Use recursion with memoization - storing return values in a lookup table so they don't have to be re-computed.

# Python: Recursion with Memoization

# store the base cases
lookup = {0:24, 1:42}

def memo_fun(x):
    if x not in lookup:
        fx = x * memo_fun(x - 1) + memo_fun(x - 2)
        fx = fx % 1000 # only need to store the last 3 digits of fx.

        lookup[x] = fx # store the value in the lookup table

    return lookup[x]

print memo_fun(1000)

1
2
3
4
5

global array
array=[24,42]
for i in xrange(2,1001):
    array.append(i*array[-1]+array[-2])
print int(str(array[-1])[-3:])

Nice question, good basis for other question. Array much faster than function.

I used Python to solve the problem. The program is as follows. The starting c = fun(0), and d = fun(1).

c=24

d=42

for i in range(2,1001):

    f=i*d+c

    print i,f

    c=d

    d=f