is fibo

주어진 숫자가 fibonacci number인지를 알아보는 것이 목표인데, 처음부터 조금 쉽게 해보려고 삽질을 하다가 괜한 시간만 보냈다.

위키에도 있지만 \(5x^2 + 4\)나 \(5x^2 -4\)중 하나만 perfect square여도 \(x\)가 fibonacci number이다. 문제는 이런식으로 하려면 data type때문에 숫자가 조금만 커져도 풀 수가 없어진다는 점. 주어진 열자리 수가 fibonacci number인줄 알기 위해서는 \(5\times x \times x\)를 계산해야 하는데 금방 스무자리가 넘어간다. 아주 큰 수의 square root를 어떻게 계산해야 하는지는 좀 더 찬찬히 생각해 봐야 할 것 같다.

이 문제가 의외였던 점은, brutal force로 해도 열자리 정도에는 금방 도달한다는 점. 1,1,2,3,...으로 진행되는 squence에서 99번째면 서른자리¹⁾에 도달하고 996번째면 300자리²⁾에 도달한다. 

위키페이지를 보다가, ‘The Fibonacci Quarterly’라는 저널이 있다는 것도 알았다. 세상엔 참 별의별 저널이 다 있다.

---

1) 118842243771396506390315925504
2) 125567414904640701673643560436718962175164626371742219622314498637150513803703451854671685017464358374327500732525759393576618588167068051984194268453498923483608216111221456860403218028074661818882275572106013378713850874227329307333971218118090581030131208722889166027270662089679192033248503922688