The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field. # 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}$

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

## Warm-up Questions

1. Convert the recursive function $$f(n)=f(n-1)+1,$$ with $$f(0)=0$$ into a non-recursive form.
2. Consider the incomplete recursive function $$f(n)=2f(n-1)$$. What mathematical function could it implement and how would you make it complete?
3. 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 2
Pay attention to the numbers you subtract (subtractors) each time. You may want to subtract sufficiently many.
• Hint 3
Can you spot a group of subtractors that repeats? How many groups are there?
• Hint 4
Now concentrate on what happens outside the argument of $$f$$. What value is added in each group?
• Hint 5
Pay 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 . Please do not write to this address regarding general admissions or course queries.