projecteuler.net : Problem 25

피보나치 수열이 천자리수가 되는 첫번 째 항은 무엇인가? 가 문제인데

음...... 생각 많이 하다가 도저히 안되겠어서 시간이 느리더라도 프로그램으로 구해보려고 했다.

하지만 예상밖으로 1초만에 항을 구할 수 있었고, 답은 4000항 정도쯤.

근데 자리수가 바뀔려면 몇번째 항을 넘어가야 바뀌는걸까 궁금해서 코딩을 해봤다.

BigInteger fibo[] = new BigInteger[10000];
  fibo[1] = new BigInteger("1");
  fibo[2] = new BigInteger("1");
  BigInteger cmp = new BigInteger("1");
  
  for(int j=1; j<=20; j++)
  {
   cmp = new BigInteger("1");
   for(int i=1; i<=j; i++)
    cmp = cmp.multiply(new BigInteger("10"));
   
   
   for(int i=3; i<10000; i++)
   {
    fibo[i] = fibo[i-1].add(fibo[i-2]);
    if(fibo[i].compareTo(cmp) == 1)
    {
     System.out.println(i + "항에서 자리수가 바뀜");
     //System.out.println(fibo[i].toString());
     break;
    }
    
   } 
  }

결과는
7항에서 자리수가 바뀜
12항에서 자리수가 바뀜5
17항에서 자리수가 바뀜5
21항에서 자리수가 바뀜4
26항에서 자리수가 바뀜5
31항에서 자리수가 바뀜5
36항에서 자리수가 바뀜5
40항에서 자리수가 바뀜4
45항에서 자리수가 바뀜5
50항에서 자리수가 바뀜5
55항에서 자리수가 바뀜5
60항에서 자리수가 바뀜5
64항에서 자리수가 바뀜4
69항에서 자리수가 바뀜5
74항에서 자리수가 바뀜5
79항에서 자리수가 바뀜5
84항에서 자리수가 바뀜5
88항에서 자리수가 바뀜4
93항에서 자리수가 바뀜5
98항에서 자리수가 바뀜5

잘 보시라 대부분 4항이나 5항째에서 바뀌는것을 알 수 있다. 왜 그런걸까?

작은 수 뿐만 아니라 큰수에도 똑같이 적용이 되던데, 이건 예외가 있는건가?

또 하나의 규칙을 발견할 수 있다. 바뀔 때 네번혹은 다섯번마다 4의 항간격이 나타난다는 것이다.

이게 사실인가? 사실이면 증명을 어떻게 할까?