I am afraid I am really struggling with this problem.

My code solves the problem within a few seconds for M = 433156 (answer n = 282) and M = 233328 (answer n = 1620).

However on test data with e.g. M = 441485 I find after a longer time n = 3480.

For M = 383228 after a vert long time I guess n > 40000.

I found a forum post dated 2015-02-10 in which Rodion's replies to efesmirfis help somewhat although even with this help - I still cannot see through the problem

From the hint:

To calculate (A + B) % M you need not know A and B themselves - it is enough to know A%M and B%M

I played with small numbers as suggested.

So for example I could see that for M = 17 it is easy to see that n = 9 and that Fib(9) = Fib(8) + Fib(7) fib(8) = 21, so fib(8)%17 = 4 fib(7) = 13, so fib(7)%17 = 13 (4 + 13) % 17 = 0

From here I was not sure how knowing 4 and 13 helps. I can see 13 is in the fibonacci sequence (as is a prime) and 4 is not although 21 = (4 + 17) is in the fibonacci sequence. But for large values of M, two integers A and B which add to M would still require computing fibonacci numbers and searching to see if these modulo M equal A and/or B would it not ?

Whilst playing with pencil and paper I noticed that expanding F(n) = F(n-1) + F(n-2)

leads to the binomial coefficients (numbers in pascals triangle) but again I could not find how this would help in getting an efficient solution.

Maybe you can help without completely giving the game away.

I have course done lots of google searching but the amount of information related to fibonacci is somewhat overwhelming - pisano periods, etc., ..

Hello. I tried this task what you say and it work. You writen

and that Fib(9) = Fib(8) + Fib(7) fib(8) = 21, so fib(8)%17 = 4 fib(7) = 13

You not count from end. Not 9,8,7. But better you count from start! Because can remember that problem about "modulo calculations", I can add numbers many times and divide module many times and therie module remains.

0 1 1 2 3 5 8 13

now 8 add 13 is 21 and we module it so it 21%17=4

next is 13 + 4 is 17 anyway too soon, but if tried for any modulo it works always.

I tried just that minute and it work and because this I think it right what you say, if just start from start not backwords.

No it does not help. As I said in original post:

From here I was not sure how knowing 4 and 13 helps. I can see 13 is in the fibonacci sequence (as is a prime) and 4 is not although 21 = (4 + 17) is in the fibonacci sequence. But for large values of M, two integers A and B which add to M would still require computing fibonacci numbers and searching to see if these modulo M equal A and/or B would it not ?

There are a total of 8 pairs of integers A, B that add to exactly M=17 and an infinite number that add to k*M, k being some positive integer k>1.

How to I know to choose 4 and 14 as opposed to A=3, B=14 or A=5, B=12.

In the real problem M=433156 for example, there are 216578 pairs A, B that add to equal M

Sorry (

you say

there are 216578 pairs A, B that add to equal M

i think you is trying to find way to solve without calcalating all secuence of fibonaci

i dont know such metod!

what i propouse is calculating all secuence by module M

becase if we calculate by module we do fast, numbers are never big

let do exemple, let M=18, we bild secuence:

fib(0)%18 = 0
fib(1)%18 = 1
fib(2)%18 = 1
fib(3)%18 = (1+1) % 18 = 2
fib(4)%18 = (1+2) % 18 = 3
fib(5)%18 = (2+3) % 18 = 5
fib(6)%18 = (3+5) % 18 = 8
fib(7)%18 = (5+8) % 18 = 13
fib(8)%18 = (8+13) % 18 = 3
fib(9)%18 = (13+3) % 18 = 16
fib(10)%18 = (3+16) % 18 = 1
fib(11)%18 = (16+1) % 18 = 17
fib(12)%18 = (1+17) % 18 = 0

afte fib(7) we dont sum fibonaci valus itseves, but theire modules only. we stop when reach 0 and print number of step (12)

Hello Friends! That is interesting point:

i think you is trying to find way to solve without calcalating all secuence of fibonaci. i dont know such metod!

I never thought about it myself. The solution I thought of is just as described above. Let me clarify what the statement says:

Values will not exceed 2000000

This is both about input values and result values. So yes, summing up 2mln of small values even in scripting languages like Python shouldn be on order of second, I think.