:

Fibonacci and Mod

Added by: ~Majje, 2011 VI 07

Added by: ~Majje, 2011 VI 07

So I want to do a challenge, which is

"What is the smallest value of x>0 such that F[x]=0 mod 2^32"
F[x] is the fibonacci sequence.

So I cooked this up.
And I got the wrong answer... any of you see anything wrong with it?

[code]#include <ttmath\ttmath.h>
#include <cmath>
#include <iostream>
#include <fstream>

using namespace std;
typedef ttmath::Big<1,2> MyBig;

void main (){

bool done = false;
int i;

MyBig fib [150];
fib [0] = 0;
fib [1] = 1;

MyBig divi = 4294967296;
MyBig rem;

for (i = 1; i <= 145; i++){
fib [i+1] = fib [i] + fib [i-1];
rem = fib [i];
rem.Mod(divi);
if( rem ==0){
cout <<"value: " << fib [i] <<endl;
cout << "Step: " << i << endl;
cout << "Divider: " << divi << endl << endl;
}

}

cin.get();
return;
}[/code]

Added by: ~petro, 2011 VI 08

the mantissa seems to be too small for such values, check this:
typedef ttmath::Big<1,6> MyBig;

Added by: ~Majje, 2011 VI 08

Wonderful, thanks. Found out that I will have to read up on number theory on this one. Find an easier method than bruting it. If anyone got any good ideas do let me know, anyways thanks for the help..