Can you Solve it? High School Math Competition Problem

A high school math competition problem dealing with the Fibonnaci sequence.

[Aoskar]

Write a program that uses a for loop to get the 2010th number and run % 7 on it?

[pokemonded]

Looking at what F1, F2, F3.. In Mod 7, we get the following sequence: 1, 1, 2, 3, 5, 1, 6, 0, 6, 5, 4, 2, 6, 1, 0... And after that it just repeats. The sequence is of length 16. 2010=10(mod 16) and the tenth value in the sequence is 6.

[noahz.]

Tips for anybody who wants to solve it: There is a nice pattern you can find in the first few parts of the sequence, that tells you which F_n are divisible by which number, use modular arithmetic to do the rest.
I'll post the solution in a bit, I don't wanna spoil it

[DavoBrawn]

We see the remainder (MOD) pattern repeats after F₁₆. Take the MOD₁₆ of 2010 (16 divides evenly into 2000, leaving 10 remainder) and find the index of the pattern. Answer is the same as MOD₇ of F₁₀.

[MusicNewb]

F2010 mod 7 = 6. Pattern repeats every 16 times starting from F6. F6 mod 7 = 1. F22 mod 7 = 1. F38 mod 7 = 1 and so on.

[manuelpanganoron]

Fibonacci. Remainder of 7
F1 =1. 1
F2 =1. 1
F3 =2. 2
F4 =3. 3
F5 =5. 5
F6 =8. 1 note rem. is 5+3-7
F7 =13. 6 note rem. is 1+5
F8 =21. 0 note rem. is 6+1-7
F9. 6
F10. 6
F11. 5
F12. 4
F13. 2
F14. 6
F15. 1
F16. 0
F17. 1

by this point the remainder from F1 to F16 repeats from F17 to F32 and so forth...

F2010 has 125 sets of 16 with a remainder of 10.

In the 16 set the 10th remainder is 6.
Hence, the answer is 6.

[benjones]

Spoilers:






It's 6. Notice that Fn+2 mod 7 = (Fn+1 + Fn) mod 7 = ((Fn+1 mod 7)+(Fn mod 7)) mod 7.
So now we have a new rule to generate the nth Fibonnaci number mod 7. Note that this sequence only has 7 possible values (0-6), and since the sequence is infinite, it must repeat at some point. The first 18 values of the sequence are:

1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0, 1, 1...

After the 16th term, the sequence begins to repeat. Thus F2010 mod 7 = F(2010 mod 16) mod 7 = F(10) mod 7 = 6.

[FatihErdemKzlkaya]

It seems like mod 7 of the fibonacci series repeats every 16 elements, if so the answer is 6. Can anybody explain me why, if it is so?

[Monadoabyss]

6, write down the fibonacci sequence in mod 7 and you quickly see the sequence repeats itself every 16 numbers (F_n=F_(n+16) mod7). Work out 2010 mod 16 (10) and pick the 10th number of the repeating sequence of 16 numbers, which happens to be 6.

In the actual competition you want to prove the sequence does in fact repeat via (strong) induction though.

[aymaniqachaden]

You can notice that in the fibonnaci sequence, from the 16th term, the sequence kinda tend to repeat itself with 1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0, 1, 1... and so on.
Therefor F2010 mod 7 = F(2010 mod 16) mod 7 = F(10) mod 7 = 6.
For a minute there i was about to try to get the real number of F2010 and actually divide it by 7, but the question is what is the remainder so the answer is 6 !

[user]

calculating F3, F4, ..., Fn till you find the last digit starts to repeat as a pattern. Assume there are x numbers in the pattern. Then do a mod x...

[litojonny]

yes but i'm not going to tell you.

[klapaucius-dkopf]

It's 6! The remainder of the numbers also have perform the fibonacci sequence, where the sequence repeats itself in every 16 numbers.

[abdelmoniemkhider]

can u do a video explaining the mathematical sequence in a less complicated way 🙏🙏🙏

[DarkLordAli]

im not doing it, but I'm guessing we could try to find the closed formula, sub 2010 in it, and divide by 7 or something?

[MultiPaulinator]

6
I had the program already written, so I just wrote, compiled and executed one line of code.

[bluekeybo]

Do a list of mod 7 results and you'll see that it's also like a fibonacci but with a period of 16. Then do 2010 mod 16 and you get 10, and the 10th element in that mod 7 list is 6. The answer is 6

[zombify]

I got 6 :) the mod 7 of the fibanci sequence repeats every 16 numbers.

[Veexliat]

I know the answer, but i don't know ho to prove it :/

[Hogdriva]

I am going for a BS in software engineering. I understand (to a point) how this math applies to programming but NOT how calculus applies. One of my professors said the only time you'll use Calculus in programming is if you are writing a program that does calculus, lol. Triggers me that it's required.