fibonacci divisibility advanced problem 71
Back to Problem Solutions forum
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.
Hi pearl_barley,
Thanks for response. Sorry but I am not sure what you are trying to say.
I understand the modulo arithmetic rule under the "Magic property of the Remainder" in the article about modular arithmetic.
The rest of what you say I do not follow.
For the actual problem M is very large so I do not know what n is and consequently I do not know what (n-1) nor (n-2) is. It follows that I do not then have a fibonacci sequence of known length.
Sorry, I write badly.
You say
I do not know what (n-1) nor (n-2)
But you not need to know them. I try explain in formula
F(n) % m = (F(n-1) + F(n - 2)) % m = (F(n-1) % m + F(n - 2) % m) % m
And we only need not F(n-1) but F(n-1)%m and not F(n-2) but F(n-2)%m
Is it help?
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.
Hi pearl_barley and Rodion,
Pearl thanks so much for your example - a great description and thanks for your patience.
Clearly I should go and get lots of practice with pencil and paper working with modulos and looking for patterns!
If there are any good websites you know of that encourage this do let me know. Maybe Khan Academy.
Problem solved.
what? order of a second? IT took my python program an eternity to count to 2 million
pearl barley
I followed your example:
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
You are correct. Thanks.