Internet problem solving contest question

Question

I am trying to solve a problem from the IPSC http://ipsc.ksp.sk/2001/real/problems/f.html It basically asks to compute the following recursion.

    P(x) = 1                for 0<=x<4
    P(x) = P(x-1) + P(x-pi) for 4<=x,
    where pi = 3.1415926535... In this problem, you are asked to compute P(x) for a given x.

How to reach to a formula in this case.Maybe some how matrix exponentiation can be used?

Answer 1

@John no P(4-pi) is defined as 1 in the task description. You misunderstood the question. @user103260 4 different approaches:

1. Master Theorem
2. Akra-Bazzi-Theorem

3. Characteristic polynomial: x^n = x^(n-1) + x^(n-pi). Since the solution of the equation does not depend on n you could store the solution for the function up to some precision. Then follow the normal procedure to compute your solution, based on the two roots you will find.

4. An other way would be to consider the terms separately. Basically you have two sequences, one operates on the natural numbers and one operates on the numbers, shifted by pi. But you will never end up with something like sqrt(2) (Assuming x is a natural number). Define the remaining term of pi, when you subtract 3 as p = pi - 3 = 0.141... You can start writing down the first values as:

$$ P(4) = P(3) + P(4-\pi) = 1 + 1 = 2 \\ P(5-p) = P(4-p) + P(5-p-\pi) = 2\\ P(5) = P(4) + P(5-\pi) = P(4) + 1 = 3 \\ P(6-p) = P(5-p) + P(6-p-\pi) = P(5-p) + P(6-\pi+3-\pi) = 3 $$
But since you do only get linear combinations of p and pi you will never end up with something crazy. Therefore it might be worthwhile to try dynamic programming. I will also edit this post, if I come up with something clever :)

While you are waiting for other answers, could you maybe just compute the first 10 numbers and show them?

Answer 2

The function will be an integral step function. It will first step up at $x = 4$ when $P(4)=2$. Thereafter it will step up at $x$ if it stepped up at $x-1$ or $x-\pi$. It should be easy to see that the stepping points will be at $x =4 + m + n*\pi$ for integer $m,n \ge 0$. However note that when $m,n \gt 0$ the step will be greater than $1$ as both $x-1$ and $x-\pi$ were stepping points.

Let $S(m,n)=$ step in $P(x)$ at $x=4 + m + n*\pi$. The obvious recurrence relationship for $S$ is $S(m,n)=S(m-1,n)+S(m,n-1)$ for $m, n \gt 0$. When $m = 0$, $x =4 + (m-1) + n*\pi$ is not a stepping point, so $S(0,n)=S(0,n-1)$ for $n \gt 0$ and similarly $S(m,0)=S(m-1,0)$ for $m \gt 0$. We also have $S(0,0) = 1$. This is Pascal's Triangle and therefore $S(m,n) = \binom{m+n}{m}$.

It follows that for $x \ge 4$, $$P(x) = 1 + \sum \left \{ \binom{m+n}{m} : (4 + m + n*\pi)\le x,m, n \in\mathbb{Z}_{0} \right \}$$

$$P(x) = 1 + \sum_{n=0}^{\left \lfloor (x-4)/\pi \right \rfloor}\sum_{m=0}^{\left \lfloor x-4-n*\pi \right \rfloor}\binom{m+n}{m}$$