853 Pisano Periods 1

对于每一个正整数 $n$ ，斐波那契数列模 $n$ 后都会循环起来，周期依赖于 $n$ 。这个周期称为 Pisano period，记作 $\pi(n)$ 。

有三个 $n$ 使得 $\pi(n)$ 是 18:19, 38 和 76. 小于 50 的和是 57。

求小于 1'000'000'000 的 $n$ 的和，这里的 $n$ 满足 $\pi(n)=120$ 。

1'000'000'000 非常大，所以逐个尝试肯定不可取，而需要想办法构造满足条件的数，然后求和。

我们先看下 $n\leq 20$ 时 $\pi(n)$ 的情况，看看能不能找到一些规律和提示。

$n$	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
Period	3	8	6	20	24	16	12	24	60	10	24	28	48	40	24	72	24	18	60

14 是 2 和 7 的积，恰好 2 对应的周期 3 和 7 对应的周期 16 公约数为 1，14 对应的周期恰好是 3 和 16 的乘积。两者的周期没有大于 1 的公约数，周期也就是最小公倍数，即两者乘积。

6 和 12 的周期一样，都是 24，两者相差 1 倍，而 2 的周期是 3，是 24 的因数，所以不会影响周期。

20 是互斥对 4 和 5 的乘积，周期也是对应周期的最小公倍数。

泛化上述观察，一个质数的周期是由自己决定的，而合数的周期是由质因数确定。所以选择一些质数，由这些质数的幂次组成的数 $n$ ，其 $\pi(n)$ 有可能是 120。

选择哪些质数呢？2 3 5 对应的周期是可能配合其他合适的数，使得 $\pi(n)=120$ ，而 13 对应的周期包含质数 7，那么显然 13 不是候选质数。这并没有回答问题本身。

我的做法是从实践中得到真相。把 100 以内的使得 $\pi(n)=120$ 的 $n$ 都分析下，看看它们由哪些质数组成。

稍微岔开点话题。

题目中的数字 1'000'000'000 很大，但是 100, 1'000, 10'0000, 甚至 1'000'000 不大，可以暴力求解，作为新方法是否正确的验证，最重要的是，令 $N=100$ 可以得到上面需要的质数列表。

下面的函数可以用于判断 $\pi(n)$ 是否等于 120：

private static readonly long[] f100 = new long[125];
private static readonly long[] m100 = new long[125];

// init in main function
m100[0] = 1;
m100[1] = 1;
f100[0] = 1;
f100[1] = 1;

private static bool Period200(long n)
{
    for (int p = 2; p < 125; p++)
    {
        f100[p] = (f100[p - 1] + f100[p - 2]) % n;
        m100[p] = f100[p];
    }

    for (int i = 2; i < 122; i++)
    {
        if (m100[i] == 1 && m100[i + 1] == 1 && m100[i + 2] == 2)
        {
            if (i == 120)
            {
                return true;
            }

            break;
        }
    }

    return false;
}

那么写一个 for 循环，就可以得到 100 以内满足条件的数了。经过分析，有这些质数：2, 3, 5, 7, 11, 31, 41, 61。

有了候选的质数列表。我们可以使用如下函数计算可能满足条件的数。方法很简单。最开始只有 2 的指数是 1，其余指数是 0。和数数一样，从最低位加 1，如果加 1 之后使得结果大于了 $N$ ，那么这一位清零，让高一位加 1，相当于进位操作。如果最高位也清零了，意味着已经遍历了所有可能的数了。

private static readonly int[] bases = new int[] { 2, 3, 5, 7, 11, 31, 41, 61 };

private static long ToLong(int[] power)
{
    long p = 1;
    for (int i = 0; i < power.Length; i++)
    {
        for (int j = 0; j < power[i]; j++)
        {
            p *= bases[i];
        }
    }

    return p;
}

private static bool Next(int[] power, ref long n)
{
    for (int i = 0; i < power.Length; i++)
    {
        power[i]++;
        n = ToLong(power);
        if (n > N)
        {
            power[i] = 0;
            if (i == power.Length - 1)
            {
                return false;
            }
        }
        else
        {
            break;
        }
    }

    return true;
}

使用两种方法计算了当 $N=10000$ 时，满足条件的 $n$ 的和。这种快速的方法少了一些。没办法，打印 debug 法。将 10000 以内满足条件的数都打印出来看看，经过对比，后者少了几个，最小的一个值是 2521，这是一个质数，能够使得周期是 120。

将这个质数补充到 bases 之后，对于 $N=1'000'000$ 得到的结果和暴力法是一致的。大差不差，这种方法可以得到正确结果，而且只需要 100ms 的时间，很快！

能得到正确结果，说明 2521 之后就没有质数的周期是 120 了。分析这一点超出我的认知范围了。