欧拉项目 | 110题 | 丢番图倒数

正整数方程$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$。如果$n=1260$，那么有113个不同的解，这个解的数量超过100的最小的$n$值。
求不通解的数量超过4百万的$n$的最小值。

$x$和$y$必须大于$n$，否则$1/x$或$1/y$就比$1/n$大了。所以不妨令$x=n+a,y=n+b$，其中$a,b$也都是整数。带入原式，我们可以得到$n^2=ab$。所以原方程就变成了$n^2$有多少种方式分解成两数之积。

$n$可以写作$p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$，$n^2$可以写作$p_1^{2k_1}p_2^{2k_2}\cdots p_m^{2k_m}$，因数的个数是$(2k_1+1)(2k_m+1)\cdots(2k_m+1)$，那么解的个数就是因数个数加一除以二。

我们可以找到一个数，满足题意，但不一定最小。
假设$k_i$取值都是1，那么前十五个质数(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47)乘积组成的$n$就有超过4百万个解了($(3^{15}+1)/2=7,174,454$)。
能不能让这个数再小一点呢？
去掉尾部的一个质数，因数会小三倍，那么前面某个质数对应的$k$从1到4，那么指数从3到9，刚好弥补三倍，2的三次方是8，3的三次方是27，比43和47小，所以可以去掉，然后$k_1$和$k_2$升到4。
上面我们推测的数对应的因子比四百万大很多，能不能去掉41呢？5和7对应的$k$从1到2，那么指数涨了5/3倍，两个数就是25/9倍，再除以三，是25/27倍，得到的因数还是远远大于四百万的。

综上，我们只需要前十二个质数即可。对应的k的取值分别是{4,4,2,2,1,1,1,1,1,1,1,1}。这些值的上限是多少呢？
17对应的$k$值上限就是1。如果是2，那么相比1，因数个数增长了5/3倍，那么2从4到6，3从4到5，增长143/81，比5/3要大，但是其乘积是12，比17小。17之后的也上限也只能是1。
其他数字的上限怎么确定呢？我们用5做例子。假设对应的$k$最大是5，那么考虑把它减到2，因数少了11/5倍，我们增加一个质数比如41，能增加三倍的因数，同时41比125小很多。所以5太宽松了，最大值取4即可。
经过一系列的分析，可以得出对应的最大值分别是{ 9, 5, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1 }。

下面是代码，从取值为0开始，一直循环到最大值，然后看因数个数是否大于四百万，然后在所有满足题意的数字中选择最小的。

private readonly int MAX = 4_000_000;
private readonly int[] Primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
private readonly int[] MaxPower = new int[] { 9, 5, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1 };

private BigInteger min = long.MaxValue;

private void Check(int[] power, int index)
{
    if (index == power.Length)
    {
        int count = 1;
        foreach (var item in power)
        {
            count *= (1 + item * 2);
        }
        count++;
        count /= 2;

        if (count > MAX)
        {
            var n = Primes.Zip(power, (i, j) => (long)Math.Pow(i, j))
                .Select(l => (BigInteger)l).Aggregate(BigInteger.Multiply);
            if (n < min)
            {
                min = n;
            }
        }
    }
    else
    {
        for (int i = 0; i <= MaxPower[index]; i++)
        {
            var copy = power.ToArray();
            copy[index] = i;
            Check(copy, index + 1);
        }
    }
}

1	Check(new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 0);