×

SIGFIB - Editorial

Author: Devendra Agarwal
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu

Hard.

Mathematics.

PROBLEM:

Find the value for the expression ∑ (6*x*y*z*Fibo[x]*Fibo[y]*Fibo[z]) where x+y+z = N.

Explanation

Free Advice: Please sit with a pen/pencil and a copy to grasp the solution for the problem.

We will denote Fibo[x] with F[x] , and T[x,y,z] = Fibo[x]*Fibo[y]*Fibo[z] in the whole editorial.

= ∑ 6*x*y*z*T[x,y,z]

= ∑ 6*x*y*(N-x-y)*T[x,y,z] //x+y+z = N

= ∑ 6*x*y*N*T[x,y,z] - 6*x2*y*T[x,y,z] - 6*x*y2*T[x,y,z] //Follows from previous step

From symmetry of x and y, we can say that

∑ 6*x2*y*T[x,y,z] = ∑ 6*x*y2*T[x,y,z] ,where x+y+z = N

Answer = ∑ 6*x*y*N*T[x,y,z] - 2*∑ 6*x*y2*T[x,y,z]

Let us now bifurcate to solve both expressions individually,i.e.

Let E1 = ∑ 6*x*y*T[x,y,z] , E2 = ∑ 6*x*y*N*T[x,y,z]

E1

E1 =

= ∑ (2*x*y + 2*y*z + 2*z*x)*T[x,y,z] //Reason: symmetry

= ∑ ((x+y+z)2-x2-y2-z2)*T[x,y,z] //Formula of 2*x*y + 2*y*z + 2*z*x

= ∑ (N2 - 3*x2)*T[x,y,z] //Reason: x+y+z= N , and from symmetry of x,y,and z.

= N2*∑ T[x,y,z] - ∑ 3*x2*T[x,y,z]

E2

E2 =

= ∑ 6*x2*y*T[x,y,z]

= ∑ (3*x2*y+6*y2*x)*T[x,y,z] //Symmetry

Using the Identity: (x+y+z)3 = x3 + y3 + z3 + 3*x2*y+6*y2*x + 3*(x+y)*z*(x+y+z) , and also using the fact that x+y+z = N , we get :

= ∑ (N3 - (x3 + y3 + z3 + 3*(xy+yz)*N))*T[x,y,z]

= ∑ (N3 - (3*x3 + 3*(2*x*y)*N)*T[x,y,z] //Symmetry Arguments

= N3* ∑T[x,y,z] - 3*∑ x3*T[x,y,z] - N* ∑ 6*x*y*T[x,y,z]

= N3* ∑T[x,y,z] - 3*∑ x3*T[x,y,z] - N*E1

For calculating E2 , you need E1 , ∑T[x,y,z] and ∑ x3*T[x,y,z]. For calculating E1 , you need ∑ T[x,y,z] and ∑ x2*T[x,y,z].

Overall for calculating answer , all we need is to calculate these three terms : ∑T[x,y,z] , ∑ x2*T[x,y,z] and ∑ x3*T[x,y,z].

Let us try to solve ∑T[x,y,z] :

First off all , you should write a small code to find the pisano period of all numbers from 1 to 100000, you will note that the maximum pisano period is 375000. Maximum value of Period / M <= 6.
Now , you must have realised that the solution is aiming at Order(period of fibo mod M )
Let f denotes the fibonacci series and let P denotes it’s period.
Consider the polynomial G(x):
(f[0] + f1∗x + f2∗x2 + .... + f[P-1]∗xP-1 )2
Coefficient of xi [ i< P ] is f[0]*f[i]+f1*f[i-1]+...+f[i]*f[0]
Coefficient of xi [ i ≤ P and i < 2*P ] : f[P-1]*f[i-(P+1)] +...+f[i-(P+1)]*f[P-1]
You can easily find the coefficients in O(N) time instead of using FFT algorithm.
Coefficient[i]=(Coefficient[i+2]-Coefficient[i+1]-f[i+1])mod M for i ≤ P − 3
Try to find out for i>=P.

Now,try to find out the solution to ∑T[x,y,z] using the polynomial.

let al = N mod P , I = N/P , NP = N mod P
for(int i=0;i<P;i++)
z1=Coeficient[al]+Coeficient[al+P]
z2=Coeficient[al];
s = (N-i)/P
ns1 = ( ns1+  f[i]\*z1\*normal(s) )%M;      //normal(s) is the series : Sigma(s-t) , t goes from 0 to s-1
ns2=(ns2+f[i]\*z2)
if(i<=NP)
ns3 = (ns3+f[i]\*z2)%M;
al=(al-1+P) % P;

s1 = (s1+s2\*I+s3) % M;


s1 contains the value of ∑T[x,y,z]. You need to start from small N and M , try to find the pattern and code it.You may find the pseudo code to be beneficial.

For solving the other two version , it is quite straight forward from here. You will get a different series to solve in both cases and the overall structure remains almost the same.

Below is the pseudo code for ∑ x2*T[x,y,z]

let al = N mod P , I = N/P , NP = N mod P
for(int i=0;i<P;i++)
z1=Coeficient[al]+Coeficient[al+P]
z2=Coeficient[al];
s = (N-i)/P
ss1 = ( ss1+  f[i]\*z1\*square( i , s) )%M;        //square(i,s) is the series : Sigma( ((i+t\*p)^2)\*(s-t)) , t goes from 0 to s-1
ss2 = ( ss2+ fz2\*squaring(i,s) )               //squaring(x,s) is x^2 + (x+P)^2 + ....s terms
if(i<=NP)
ss3 = (ss3 + x<sup>2</sup>\*f[i]\*z2)
al=(al-1+P) % P;

ss1 = (ss1+ss2+ss3) % M;


I hope you can find for ∑ x3*T[x,y,z] yourself.

I saw some awesome solutions , I would like to invite every participant to share their awesome ideas with us :) .

Complexity:

O(period) per test case = O(M) per test case.

AUTHOR'S and TESTER'S SOLUTIONS:

This question is marked "community wiki".

3.0k93164187
accept rate: 12%

8383515

(12 Aug '14, 06:31)

May be noob question. Can someone please explain the second decomposition in calculating E2? i.e. how sigma(6x2yT[x,y,z]) = sigma((3x2y+6y2x)T[x,y,z])

(02 Sep '14, 22:58)

 7 Awesome problem!!! I guess there can be a lot of ways to solve this problem. In my case I derived a formula for the nth term by solving set of simultaneous equations of 12 variables taking a clue from this paper: http://www.mathstat.dal.ca/FQ/Scanned/15-2/hoggatt1.pdf F(N) = ∑ (6xyzFibo[x]Fibo[y]Fibo[z]) = ((5N^5 + 35.N^3 - 4.N).Fibo(N) - 36.N^2.Lucas(N))/500 The problem with the above approach was that for M which have factors which are powers of 2 and 5, mod inverse of 500 does not exist. For these cases I used a different approach, the idea again from the same paper. I used the recurrence relations for the rth Fibonacci convolution sequences. I pre-computed 5th Fibonacci convolution sequence for the highest powers of 2 and 5 possible. The generating function for the 5th Fibonacci convolution sequence is (x/(1-x-x^2))^6, whereas our sequence has a generating function of 6.(x.(1+x^2)/(1-x-x^2)^2)^3 or 6.(x^-3 + 3.x^-1 + 3.x^1 + x^3).(x/(1-x-x^2))^6. So we can obtain F(N) from the 5th Fibonacci convolution sequence by using the formula F(N) = 6. (F5(N-3) + 3.F5(n-1) + 3.F5(N+1) +F5(N+3)) , where F5(N) is the 5th Fibonacci convolution sequence as pre-computed above. Finally, to address how we arrived at the generating function of our sequence, we notice that our function is the result of convolution of the sequence N.Fibo(N) with itself 2 times. Generating function of the sequence N.Fibo(N) is the first derivative of the Fibonacci sequence shifted by 1 position whose generating function is x/(1-x-x^2) and hence has a generating function x.(1+x^2)/(1-x-x^2)^2 Hence the generating function for our sequence is 6 times the cube of this as we are convolving 2 times. answered 11 Aug '14, 16:43 5★n2n_ 1.8k●6●13●19 accept rate: 9% I went the same route but got stuck on the case where M % 2 ==0 || M % 5 == 0 Could you please provide the link of your solution? (11 Aug '14, 18:56) 2 omg awesome explanation!!! I really get blown away by how truly talented some people are...and even though I'll never reach this level, just having the chance to learn a few things is already awesome for me :D Thanks for this (11 Aug '14, 20:19) kuruma3★ 1 I got the generating function, and I found a 12th order recursion that described the sequence. Sadly, I couldn't do necessary matrix multiplications within the time limit. Alas, it seemed like a decent approach at the time. (12 Aug '14, 07:04) Great work ^_^ I was going for this problem, did a bit of mathematics but other problems took a lot of time. A good way to learn, Thanks :-D (12 Aug '14, 14:42)
 1 http://pan.baidu.com/s/1sjqGiDn this is how i solve it（chinese） answered 11 Aug '14, 17:14 2★mazeyu 30●1 accept rate: 0% That's really a fancy solution! (13 Aug '14, 15:35)
 0 May be noob question. Can someone please explain the second decomposition in calculating E2? i.e. how sigma(6x2yT[x,y,z]) = sigma((3x2y+6y2x)T[x,y,z]) answered 18 Aug '14, 08:02 21●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,851
×1,359
×139
×33
×1

question asked: 11 Aug '14, 15:13

question was seen: 5,547 times

last updated: 02 Sep '14, 22:58