2
$\begingroup$

I have this triangle:

$$\begin{array}{} &&&&&&&1\\ &&&&&&1&&1\\ &&&&&2&&2&&2\\ &&&&3&&4&&4&&3\\ &&&5&&7&&8&&7&&5\\ &&8&&12&&15&&15&&12&&8\\ &13&&20&&27&&30&&27&&20&&13\\ 21&&33&&47&&57&&57&&47&&33&&21 \end{array}$$

(Original image.)

As you can see this triangle is builed as the Pascal Triangle except that on the sides we have the Fibonacci Sequence.

My goal is to find the the $m$th number from $n$th row (first row is counted with $1$, first number from a row is counted with $1$).

Example: $n=7, m=5$: the answer is $27$.

So how can I do this without calculate the entire triangle? Maybe is formula, if it is I want to know what to learn in order to find out that formula. If finding a formula is too hard, maybe there is an algorithm faster than calculating the entire triangle.

The truth is that I have to write a program for this problem, max value for $n$ is $20000$ ($m\le n$) and my program should run under $1$ second. At a moment the numbers are getting to big for my pc so I have to calculate the entire triangle in modulo $666013$ (I didn't choose this number, this are my restriction). I calculate only half of the triangle but still too slow so I thought maybe math should help, so what to learn?

Hope you can help me. :)

$\endgroup$
1
$\begingroup$

Basically, to make your program simple and easy to understand, we can use two FUNCTIONS i.e. one for calculating Fibonacci Sequence and the other for calculating the mth number of nth row.

int Fibonacci(int n){

if(n==1 || n==2) return 1;

else return (Fibonacci(n-1) + Fibonacci(n-2));

}

int Pascal_Fibonacci(int n, int m){

if(m==1 || n==m) return Fibonacci(n);

else return (Pascal_Fibonacci(n-1,m-1) + Pascal_Fibonacci(n-1,m));

}

This is the basic way to calculate the number. Now, you can modify according to your needs :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.