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

发表于 2019-12-21 分类于数学 Disqus：

正整数方程$\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$有多少种方式分解成两数之积。

欧拉项目 | 95题 | 因数之和形成的链

发表于 2019-11-03 分类于数学 Disqus：

28有4个不包含自身的因数1 2 4 7，其和恰好是28，我们称之为完美数。
220不包含自身的的因数之和是284，284不包含自身的因数之和是220，形成了一个长度为2的链，也称之为亲和数。
从12496能形成一个长度为5的链：12496 -> 14288 -> 15472 -> 14536 -> 14264 (-> 12496 -> …)。
找到一个所有数值都不超过一百万的最长的链，问其中最小的数。

首先，我们要快速找到每个数对应的因数之和。

var numberToDivisorSum = new List<int>(MAX + 1);
for (int i = 0; i <= MAX; i++)
{
    // 1 is divisor
    numberToDivisorSum.Add(1);
}

// i is a factor
for (int i = 2; i <= MAX / 2; i++)
{
    // excluding the number itself, so j starts from 2
    for (int j = 2; j <= MAX / 2; j++)
    {
        if (i * j > MAX)
        {
            break;
        }

        numberToDivisorSum[i * j] += i;
    }
}

接下来计算每个数开始能够形成的链的长度，找到最长链所对应的最小的数字。

var numberToLength = new List<int>(MAX + 1) { 0 };
int longest = -1;
int index = -1;
for (int i = 1; i <= MAX; i++)
{
    numberToLength.Add(0);
    if (numberToDivisorSum[i] != -1)
    {
        int length = GetChainLength(i, numberToDivisorSum);
        numberToLength[i] = length;
        if (length > longest)
        {
            index = i;
            longest = length;
        }
    }
}

private static int GetChainLength(int number, List<int> numberToDivisorSum)
{
    var chain = new List<int>();
    int cur = number;
    while (true)
    {
        chain.Add(cur);
        int next = numberToDivisorSum[cur];
        if (next > MAX || next == -1)
        {
            foreach (var s in chain)
            {
                if (s > number)
                {
                    numberToDivisorSum[s] = -1;
                }
            }
            return -1;
        }

        if (chain.Contains(next) && number != next)
        {
            return -1;
        }

        if (next == number)
        {
            foreach (var s in chain)
            {
                if (s > number)
                {
                    numberToDivisorSum[s] = -1;
                }
            }

            return chain.Count;
        }

        cur = next;
    }
}

这里有一个有点trick的地方，如果一个链形成了（已经知道最小数了），或者因数之和比MAX要大导致无法形成一个链，那么把当前number之后的数都标记一下，在外层调用函数的for循环里面跳过，这样子大概能节省10%的时间吧。

欧拉项目 | 145题 | 可逆数的数量

发表于 2019-10-12 分类于数学 Disqus：

145题链接

有这样一些数n，和所以数字逆着写的数reverse(n)之和的所有数字都是奇数。比如36+63=99，409+904=1313等等，这些数我们称之为可逆数。有一个限制条件就是开头不能是0。
问题是，小于十亿（1,000,000,000)的数中有多个可逆数。

这道题可以通过分类讨论来解决。
首先n的长度是奇数和偶数明显是两类，因为这意味着有没有正好居于中间的数，对于奇数长度来说，有，且反过来还是该数字。

我们先来考虑长度是偶数的时候。

长度为2的时候，不妨把该数写作AB，其逆就是BA。以A+B是否大于等于10来讨论。
大于等于10的情况，不妨令A+B=1C，那么AB+BA=1(C+1)C，C和C+1奇偶性必然不同，不可能数字都是奇数。
小于10的情况，那么A+B是奇数。A是偶数，可选2,4,6,8，B是奇数，可选1,3,5,7,9，之和小于10的情况一共10种可能性。反之，A是奇数，B是偶数，也是10种。
所以长度为2的可逆数一共20个。

长度为4的时候，该数可写作ABCD，其逆就是DCBA。以A+D是否大于等于10来讨论。
大于等于10的情况，不妨令A+B=1E。若B+C大于等于10，和最后一位是E，右起第四位是1+E，不可能都是奇数；若B+C小于10，不能是9，否则和的右起第二位是0，不满足题意，如果是其他奇数，右起第二位和1+B+C，而右起第三位是B+C，也不可能同时是奇数。
小于10的情况，A和D的取值可能性有20种，中间的BC退化为长度为2的情况，取值的可能性有30种（偶数可以为0，因为不打头了），利用乘法原则，共有600个可逆数。
所以长度为4的可逆数一共600个。

长度为6的时候，该数可以写作ABCDEF，其逆就是FEDCBA。以A+F是否可以大于等于10来讨论。
大于等于10的情况，原理和4位时一样，B+E不能大于等于10。能小于10吗？为了保证B+E得到的值和E+B+1得到的值一样，那么C+D就要大于10。但是E+B不进位，而D+C进位，导致右起3，4位一定不能同时是奇数。
小于10的情况，中间4个数回到了上一种情况，所以可能性是20*30*30=18,000。
所以长度为6的可逆数一共是18,000个。

长度为8的时候，该数可以写作ABCDEFGH，其逆就是HGFEDCBA。同样，以A+H是否可以大于等于10来讨论。
在大于等于10的情况下，原理同上，B+G不能大于等于10，那么B+G就只能小于10了。同上，C+F就要大于等于10。为了使得中间两位的奇偶性一致，那么E+D要大于10，结果就是右起第三位数字是C+F模10（因为B+G小于10），而右起第六位数字是C+F+1模10，这俩不可能同时是奇数。
小于10的情况，中间六个数字回到了上一种情况，所以可逆数是20*30*30*30=540,000。
所以长度为8的可逆数一共是540,000个。

现在来讨论n的长度为奇数。
如果长度是1，反过来是其本身，那么和是偶数，不符合题意。

长度是3，可写作ABC，可逆数是CBA。中间数字的和是偶数，那么A+C必须大于10，为了右起第一位和第三位奇偶性相同，那么2B不能进位，所以B要小于等于4，那么B有五种可取值；我们现在讨论A和C，A是奇数1,3,5,7,9，C是偶数2,4,6,8，其和大于10的可能性有10中可能性，A是偶数C是奇数也有10种，那么可逆数是5*(10+10)=100。

长度是5时，可写作ABCDE，可逆数是EDCBA。中间是2C，所以B+D是大于等于10的，右起第一位是E+A，但是右起第五位是A+E+1，不可能同时是奇数，所以n的长度不可能是5。

长度为7时，可写作ABCDEFG，可逆数时GFEDCBA。中间是2D，所以C+E时大于等于10的。根据前面的分析，B+F必须小于10；进而2D要小于10。右起第六位会接受来此C+E的进位，那么右起第二位也必须接受一个进位，所以A+G必须大于10。2D小于10得出D有5种可能性，A+G大于10且和为奇数共有20种可能性，C+E大于10且和为奇数也有20种，B+F小于10且为偶数的可能性有25种。所以可逆数是5*20*20*25=50,000。

长度为9的时候，可写作ABCDEFGHI，其可逆数是IHGFEDCBA。由前面的分析可知D+F要大于等于10，那么为了让右起第三位G+C和右起第七位C+G同时为奇数，那么H+B也必须大于10，那么A+I得到B+H的进位，无法和右起第一位I+A同奇偶，矛盾，所以长度不能是9。

综上，小于十亿的可逆数是608720个。

欧拉项目 | 348题 | 一个平方数和一个立方数之和是回文数

发表于 2019-08-10 分类于数学 Disqus：

Problem 348

很多数能够写成一个平方数和一个立方数之和的形式，其中一些可能会有多种组合形式。
有一些数有4种组合形式，且它是一个回文数。比如5229225是一个回文数，能写成四种组合形式：

2285^2 + 20^3
2223^2 + 66^3
1810^2 + 125^3
1197^2 + 156^3

找到前五小的这种数，求和。

一个数是否能拆解成一个平方数和一个立方数之和是比较难的问题，但是构造一个这样的数就比较简单了。我开始假设在int范围内就至少有五个满足题意的数。
下面这段代码就会找出所有是一个平方数和一个立方数之和的回文数，并且统计了它们出现的次数。

var counts = new Dictionary<int, int>();
for (int i = 2; i < Math.Sqrt(int.MaxValue); i++)
{
    for (int j = 2; j < 1291; j++)
    {
        long sum = i * i + j * j * j;
        if (sum > int.MaxValue)
        {
            break;
        }

        int s = (int)sum;
        if (Utils.IsPalindrome(s.ToString()))
        {
            if (counts.ContainsKey(s))
            {
                counts[s]++;
            }
            else
            {
                counts[s] = 1;
            }
        }
    }
}

然后找出出现次数为4的回文数，排序，取前五，求和。

var candidates = counts.Where(pair => pair.Value == 4).Select(pair => pair.Key).ToList();
candidates.Sort();

return candidates.Take(5).Sum();

欧拉项目 | 203题 | Squarefree的二项式系数

发表于 2019-06-23 分类于数学 Disqus：

Problem 203

二项式系数可以写成如下帕斯卡三角的形式

前八排有12个不同的数：1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21 和 35。
Squarefree的意思是不能被任何质数的平方整除。前八排的数字里面，4和20不是Squarefree的，因为它们能被质数2的平方整除。
求帕斯卡三角前51排不重复的Squarefree的数之和。

我们先来估计下最大的数是多少，然后考虑用什么类型表示，第五十一行其实是n=50，那么最大的是数$$C_n^k=C_{50}^{25}=\frac{50!}{25!25!}=126,410,606,437,752$$，long就足够了。
首先我们拿到前51排的数。

var rows = new List<long[]>();
for (int i = 0; i < 51; i++)
{
    long[] row = new long[i + 1];
    for (int j = 0; j < row.Length; j++)
    {
        if (j == 0 || j == row.Length - 1)
        {
            row[j] = 1;
        }
        else
        {
            var lastRow = rows[i - 1];
            row[j] = lastRow[j - 1] + lastRow[j];
        }
    }

    rows.Add(row);
}

下一步去重。

1	var candidates = rows.SelectMany(l => l).Distinct().ToList();

要考虑那些质数的平方呢？仔细想下前51排数的性质，只需要考虑很少几个数就足够了。

1	var smallPrimeSquare = new int[] { 4, 9, 25, 49 };

如果某个数能被下一个质数的平方121整除，那么n至少要是22，这样子二项式系数的分子上才会出现2个11，但是不管k怎么取，分母上都至少有一个11这个因数。那么n至少要是33了，不管k怎么取，分子上都至少有两个11这个因数。那么n至少要是44了，同理，也无法被121整除。总结下，分母上11的因数的个数至少是分子上11的因数的个数减一。其实，结论很容易直接证明的。
那么为什么需要考虑49呢？很简单，49包含了两个7，那么n取49和50的时候，有可能分子因数7的个数能够比分母多两个。那么该数就能被49整除，进而不是Squarefree的。
最后，排除Squarefree的数字再求和即可。

candidates = candidates.Where(l =>
{
    foreach (var square in smallPrimeSquare)
    {
        if (l % square == 0)
        {
            return false;
        }
    }

    return true;
}).ToList();

return candidates.Sum();

欧拉项目 | 179题 | 连续有相同个数正因数的整数

发表于 2019-05-08 分类于数学 Disqus：

179题链接

14和15有同样个数的正因数，14有四个，1,2,7,14；15也有四个，1,3,5,15。求在1到10的7次方之间，有多少个有相同个数正因数的连续的整数？

正向求解的方式就是分解质因数，然后计算得到因数个数，这个操作看似很快，但是还是稍微有点耗时，感觉不太行。
于是乎，走向另外一条路，每找到一个因数，就加一。

int[] numberOfDivisors = new int[N + 1];
for (int i = 1; i <= N; i++)
{
    for (int j = i; j <= N; j += i)
    {
        numberOfDivisors[j]++;
    }
}

i就是因数，若干倍的j就包含一个因数i了。

知道了每个数的因数个数就简单了，看连续两个数的因数个数是否相等即可。

int count = 0;
for (int i = 2; i < N; i++)
{
    if (numberOfDivisors[i] == numberOfDivisors[i + 1])
    {
        count++;
    }
}

return count;

欧拉项目 | 125题 | 可分解成连续数字的平方和的回文数之和

发表于 2019-04-06 分类于数学 Disqus：

Problem 125

回文数595能够被写成连续几个数字的平方的和：
$$
595=6^2+7^2+8^2+9^2+10^2+11^2+12^2
$$

连续数字必须是正数，所以1=0+1被排除在外。
题目告诉我们小于1000的数字中，有11个满足题目所述条件，其之和是4164，这可以用来检测我们的程序是否正确。

求小于10^8的数中，所以能够写成连续数字平方和的回文数之和。

欧拉里面这种题目的套路就是正向构造符合题意的数字。因为想要判定一个数能否写成连续数字之后比较困难，但是构造一个连续数字平方和的数就容易多了。
我们先计算出一系列的平方数，多少个呢？由于连续数字之和，那么最少也要两个数字，所以我们构造的最大平方数是MAX的一半就足够了。

1 2	int MAX = 100000000; var squars = Enumerable.Range(1, (int)Math.Sqrt(MAX / 2)).Select(i => i * i).ToArray();

两层for循环来构造连续数字之和。

var candidates = new List<long>();
for (int i = 0; i < squars.Length - 1; i++)
{
    long sum = squars[i];
    for (int j = i + 1; j < squars.Length; j++)
    {
        if (sum + squars[j] < MAX)
        {
            sum += squars[j];
            candidates.Add(sum);
        }
        else
        {
            break;
        }
    }
}

这里面有一小撮重复的数字，去重，然后判断是否是回文数字，求和。

1	return candidates.Distinct().Where(l => Utils.IsPalindrome(l.ToString())).Sum();

欧拉项目 | 83题 | 最短路径

发表于 2019-03-10 分类于数学 Disqus：

Problem 83

一个整数矩阵，从左上角到右下角，存在一条最短路径。走的方式没有要求，在某个点，可以往四个方向走；之前有两个题目，一个是限制只能往右或者往下，稍微复杂点的另一个题目的限制是不能往左。

我的想法很直接，构造一个矩阵，是从左上角到该点的最短路径，每个点的初始值都是int.MaxValue。
用一个queue来保存被更新的点，然后看看其周围的点是否可以被更新。
从左上角的点开始，赋值成给定矩阵左上角的值。该值被更新了，把(0, 0)点放入queue里，因为周围的点可能会被更新。
然后从queue拿出一个点，看看周围的值是否能被更新，如果是，也放到queue里。
循环往复，直到queue为空，没有需要被更新的点了。
此时，每个点上的值都是从左上角开始到该点的最短路径。

代码直接反应了上述的过程，data就是题目总给出的80 * 80的矩阵。

private const int N = 80;

public static int GetAnswer()
{
    int[,] sum = new int[N, N];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            sum[i, j] = int.MaxValue;
        }
    }
    sum[0, 0] = data[0, 0];
    Queue<Tuple<int, int>> pointsToBeUpdated = new Queue<Tuple<int, int>>();
    pointsToBeUpdated.Enqueue(new Tuple<int, int>(0, 0));
    while (pointsToBeUpdated.Count != 0)
    {
        var point = pointsToBeUpdated.Dequeue();
        if (CanMoveToLeft(point))
        {
            int newValue = sum[point.Item1, point.Item2] + data[point.Item1 - 1, point.Item2];
            if (newValue < sum[point.Item1 - 1, point.Item2])
            {
                sum[point.Item1 - 1, point.Item2] = newValue;
                pointsToBeUpdated.Enqueue(new Tuple<int, int>(point.Item1 - 1, point.Item2));
            }
        }

        if (CanMoveToRight(point))
        {
            int newValue = sum[point.Item1, point.Item2] + data[point.Item1 + 1, point.Item2];
            if (newValue < sum[point.Item1 + 1, point.Item2])
            {
                sum[point.Item1 + 1, point.Item2] = newValue;
                pointsToBeUpdated.Enqueue(new Tuple<int, int>(point.Item1 + 1, point.Item2));
            }
        }

        if (CanUp(point))
        {
            int newValue = sum[point.Item1, point.Item2] + data[point.Item1, point.Item2 - 1];
            if (newValue < sum[point.Item1, point.Item2 - 1])
            {
                sum[point.Item1, point.Item2 - 1] = newValue;
                pointsToBeUpdated.Enqueue(new Tuple<int, int>(point.Item1, point.Item2 - 1));
            }
        }

        if (CanDown(point))
        {
            int newValue = sum[point.Item1, point.Item2] + data[point.Item1, point.Item2 + 1];
            if (newValue < sum[point.Item1, point.Item2 + 1])
            {
                sum[point.Item1, point.Item2 + 1] = newValue;
                pointsToBeUpdated.Enqueue(new Tuple<int, int>(point.Item1, point.Item2 + 1));
            }
        }
    }

    return sum[N - 1, N - 1];
}

private static bool CanMoveToLeft(Tuple<int, intpoint)
{
    return point.Item1 > 0;
}

private static bool CanMoveToRight(Tuple<int, intpoint)
{
    return point.Item1 < N - 1;
}

private static bool CanUp(Tuple<int, int> point)
{
    return point.Item2 > 0;
}

private static bool CanDown(Tuple<int, int> point)
{
    return point.Item2 < N - 1;
}

欧拉项目 | 119题 | 某数各数字之和的若干次幂等于该数本

发表于 2019-03-03 分类于数学 Disqus：

Problem 119

512是一个很有意思的数字，5+1+2=8，8^3=512
614656 = 28^4
an是满足这些条件的数列：
至少有两位数
各个数字之和的若干次幂等于该数
求a30

对于这种题目，欧拉项目有个套路，你不太可能遍历每个数字去检查它是否满足条件的时候，就要换种思路，快速构造满足题目的集合，然后按照题目找到答案。
回到这个题目，我个人感觉a30不会超过long能表示的范围，所以我只要看long以内的就可以了。
第一步，找到数字之和s的范围。最小值是2，因为至少有两位数；最大值是9*19，因为long.MaxValue有19位数字。其实这个范围比实际范围大一些，但是无所谓了，多的不多，不会影响程序效率。
第二步，求s的若干次幂，从2次幂开始，3次幂，4次幂等等，直到超出long的范围。这些都是可能的值n。满足这一步的n不到1700个。
第三步，求n的各个数字之和sum，如果sum等于s，那么这个n就是满足题意的。
第四步，把所有的n排序，找出第三十个即可。很幸运，long以内有34个满足题目的数。

下面是代码

var candidates = new List<long>();
for (int i = 2; i < 9 * long.MaxValue.ToString().Length; i++)
{
    int power = 2;
    while (true)
    {
        var ret = BigInteger.Pow(i, power);
        if (ret > long.MaxValue)
        {
            break;
        }

        long number = (long)ret;
        long candidate = number;

        long sum = 0;
        while (number != 0)
        {
            sum += number % 10;
            number /= 10;
        }

        if (sum == i)
        {
            candidates.Add(candidate);
        }

        power++;
    }
}

candidates.Sort();

return candidates[29];

欧拉项目 | 104题 | 头尾是不重复数字组成的斐波那契数

发表于 2018-12-18 分类于数学 Disqus：

104题链接

这里就不赘述什么是斐波那契数列了。
f(541)包含113个数字，最后九个数字恰好是由数字1-9组成的；f(2749)包含575个数字，前九个数字恰好是由数字1-9组成的。
求k，f(k)的前九个数字和最后九个数字都是由数字1-9组成的。

我一开始的思路是使用BigInteger来存放斐波那契数，逐个计算上去，判断前九个数字和最后九个数字是否是由1-9组成的。
不过我发现程序很慢，用Visual Studio分析了一下程序的性能，发现BigInteger.Log10和BigInteger.Pow非常耗时。我用BigInteger.Log10计算出数字的长度L，然后除以BigInteger.Pow(10, L - 9)得到最前面的九个数字。
稍微改变了一下策略，先判断最后九个数字，后判断前九个数字。速度提高很多，因为判断最后九个数字，只要模10的九次方就行了，比计算长度再除快非常多，而需要进行后一个判断的几率很小。于是乎，大约30s能解决。
能不能再快一点呢？我发现BigInteger的模运算也挺慢的。其实我可以用一个长度为九的数组进行最后九位的加法，然后判断是否是由1-9九个数字组成就好。

private static int[] Add(int[] fn_1, int[] fn_2)
{
    int[] ret = new int[9];
    int n1 = fn_1.Length - 1;
    int n2 = fn_2.Length - 1;
    int nr = ret.Length - 1;
    int carry = 0;
    for (; nr >= 0; n1--, n2--, nr--)
    {
        int a = n1 >= 0 ? fn_1[n1] : 0;
        int b = n2 >= 0 ? fn_2[n2] : 0;
        int sum = a + b + carry;
        ret[nr] = sum % 10;
        carry = sum / 10;
    }

    return ret;
}

判断是否是由数字1-9组成也很简单。

private static bool IsPandigitalFibonacci(int[] fn)
{
    int[] digitalCounts = new int[10];
    for (int i = 0; i < 9; i++)
    {
        digitalCounts[fn[i]]++;
    }

    for (int i = 1; i < 10; i++)
    {
        if (digitalCounts[i] != 1)
        {
            return false;
        }
    }

    return true;
}

使用这个方式来代替原来的想法，得到了完整的算法。

int[] fn_2 = new int[] { 1 };
int[] fn_1 = new int[] { 1 };
BigInteger f1 = 1;
BigInteger f2 = 1;
int i = 3;
while (true)
{
    BigInteger fnBig = f1 + f2;
    int[] fn = Add(fn_1, fn_2);
    if (IsPandigitalFibonacci(fn))
    {
        int digits = (int)Math.Floor(BigInteger.Log10(fnBig) + 1);
        var dividend = BigInteger.Pow(10, digits - 9);
        var firstNineDigits = fnBig / dividend;
        if (Utils.IsPandigital(firstNineDigits.ToString(), false))
        {
            return i;
        }
    }

    fn_2 = fn_1;
    fn_1 = fn;
    f2 = f1;
    f1 = fnBig;
    i++;
}

这比以前又快了很多，大约5s就能搞定。
分析下程序的瓶颈，发现最耗时的是BigInteger.Add，这个没办法优化了，除非能有个算法能够直接得到前九个数字是啥，这样就不要BigInteger来保存结果，我觉得没有这种算法了；次耗时的是BigInteger.Pow，它的调用次数已经优化了，而且我也没有想到更好的构造被除数的方式。
其实五秒已经挺快的了，很满意。