Question

斐波那契数列定义如下：前两个数都是1，从第三个数起，每个数是前面两个数的和，于是它的前面几个数是1，

斐波那契数列定义如下：前两个数都是1，从第三个数起，每个数是前面两个数的和，于是它的前面几个数是1，1，2，3，5，8，13，21，34，55，89.... （1）求其中2007个数除以3的余数。 （2）如果在前n个数中恰好有500个数是3的倍数，n是多少？

Answer 1

（1）求其中2007个数除以3的余数。余数是0 （2）如果在前n个数中恰好有500个数是3的倍数，n是多少？n可以是2000，2001，2002，2003

1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2 0 这是前22位
注意到 8个一循环
故第2007 个是1 ，因为2007除8余 7，是第7个。
然后每八个有两个0， 等价于4个一个0， 500个--0，500*4=2000，n可以是2000，2001，2002，2003

编程检验：
public class Main {

public static void main(String[] args) {
int[] fib = new int[4000];
int count = 0;
fib[0] = 1; fib[1] = 1;
for (int i = 2; i < fib.length; i++) {
fib[i] = (fib[i-1] + fib[i-2]) % 3;
if (fib[i] == 0) {
count++;
}
if (count == 500) {
System.out.print("need to count to ");
System.out.println(i+1);
break;
}
}
System.out.println("2007 is " + fib[2006]);
}
}

public class Main {

public static void main(String[] args) {
int[] fib = new int[4000];
int count = 0;
fib[0] = 1; fib[1] = 1;
for (int i = 2; i < 20; i++) {
fib[i] = (fib[i-1] + fib[i-2]) % 3;
System.out.print(fib[i]+" ");
}
}

Answer 2

(1)斐波那契数列各数被3除的余数的规律（可以证明）：
1,1,2,0,2,2,1,0,
8个数一循环，2007÷8余数为7，第7个余数为1，
所以，2007个数除以3的余数为1.
（2）每8个数中，有2个是3的倍数，n=500×8/2=2000.
即 n=2000 或2001 或2002 或2003