Problem 69 - Fibonacci Divisibility - are input values valid?
Back to Problem Solutions forum
Language - C#.
My algorithm is rather simple:
1) make list of Fibonacci numbers (only 0 and 1 at start)
2) try every number in the list if it's divisible by input number
3) if no such number found, count next Fibonacci number, add to the list and check it.
4) repeat step 3 until divider is found.
5) repeat from step 2 for every input divider.
My input:
17
4275 6825 8102 2852 8926 8850 2625 3828 3377 7129 6677 7352 7953 3900 8703 9226 9604
Problem: Right now (after ~10 minutes) my list is 41377 numbers long (41376th number is 8647 symbols long) and counting - nothing is divisible by 8102.
I'm pretty sure that my list of Fibonacci numbers is valid and method that checks for divisibility works as it should.
Are my input values even valid, or should I try and look for another approach?
"Problem: Right now (after ~10 minutes) my list is 41377 numbers long (41376th number is 8647 symbols long) "
Btw, you don't need to wait for 10 minutes to generate answers. You can use generators instead of iterators. Generator functions for fibonacci uses Yield, so it remembers previous value but without having to store an entire list. This makes your computation much faster.
In Python, it's called generator functions with yield instead of return. Look up if there is something equivalent in C#. Maybe Quandray can phrase it exactly since she/he programs in C/C++.
My code for that input runs in less than a second and all the answers are less than 9000. If you are going past the 9000th fibonacci number, I think something isn't right.
I made a mistake in my division method.
Since C# can't handle really big numbers with precision and making Int1024 or something like that is too long, I made two methods (add and divide) which worked with strings. I guess I've f-cked up the division somewhere.
I used another approach from one of the earlier problems (with remainder in division) and it worked a lot better.