# Practice Paper 1 Question 19

Let \(f\) be the recursive function below, with \(f(1)=f(0)=0\). What is the value of \(f(1337)\)? \[ \begin{array}{l} f(n)=f(n-1)-1 \qquad\text{ if $n$ is divisible by 2 or 3 }\\ f(n)=f(n-2)+2 \qquad\text{ otherwise} \end{array} \]

## Related topics

## Warm-up Questions

- Convert the recursive function \(f(n)=f(n-1)+1,\) with \(f(0)=0\) into a non-recursive form.
- Consider the incomplete recursive function \(f(n)=2f(n-1)\). What mathematical function could it implement and how would you make it complete?
- Let \(f(n)=f(n-3)+1\) with \(f(n)=0\) for \(n<0\). What is \(f(90)?\)

## Hints

- Hint 1\(n\) appears only in the argument of \(f\). Concentrate first only on the argument of \(f\), going down from 1337.
- Hint 2Pay attention to the numbers you subtract (subtractors) each time. You may want to subtract sufficiently many.
- Hint 3Can you spot a group of subtractors that repeats? How many groups are there?
- Hint 4Now concentrate on what happens outside the argument of \(f\). What value is added in each group?
- Hint 5Pay attention to the final terms of the recursion.

## Solution

We begin by tracing the recurrence. Since \(n\) appears only in the argument of \(f\), we can concentrate first only on what happens with the argument as it goes down from 1337. Firstly, \(1337\) is not divisible by \(2\) or \(3\), hence we have:

- \(1337-2=1335\) which is divisible by \(3\), then
- \(1335-1=1334\) which is divisible by \(2\), then
- \(1334-1=1333\) which is not divisible by \(2\) or \(3\), then
- \(1333-2=1331\) which is not divisible by \(2\) or \(3\), then
- \(1331-2=1329\) which is divisible by \(3\), then
- \(1329-1=1328\) which is divisible by \(2\), ...

We notice that the sequence \((-2,-1,-1,-2)\) of subtractors repeats every \(6\) integers. The number of times this happens is \(\lfloor1337/(2+1+1+2)\rfloor=222\) times. This gives a remainder of 5, which we need to keep in mind.

We're done with the argument of \(f\). In terms of its value, every time the argument goes to \(-2\) the value increases with \(2\), and every time the argument goes to \(-1\) the value decreases with \(1\). Hence we have: \[ \begin{align} f(1337) &=222(+2-1-1+2)+f(5)\\ &=444+f(3)+2\\ &=444+f(2)-1+2\\ &=444+f(1)-1-1+2\\ &=444 \end{align} \]

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.[email protected]. Please do not write to this address regarding general admissions or course queries.