Eulerproj01

p002

题目

Problem 2: Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with $1$ and $2$, the first $10$ terms will be: $$1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots$$

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

这道题目的要求是算出Fibonacci数列的前4000000个数字中的偶数之和。

解答

这题如果直接做，可以直接根据Fibonacci数列的规律，直接while循环判断。

$$ F(n) = F(n-1)+F(n-2) $$

代码如下

fn solve2() -> u64 {
    let mut a = 1;
    let mut b = 2;
    let mut sum = 0;
    while a <= 4_000_000 {
        if a % 2 == 0 {
            sum += a;
        }
        let next = a + b;
        a = b;
        b = next;
    }
    sum
}

很明显，这样是能算到最终结果的，最终的结果就是4613732，但这个太暴力很明显不值得我特地写一篇博客。

此时，我们好好回顾一下这个问题，要求一个fibonacci数列的所有偶数，我们在写这个数列的时候会发现数列中的偶数是隔着两个奇数就有一个偶数，如果把所有偶数剔出来，会发现满足一下的规律。

$$ F(n) = 4*F(n-1) + F(n-2) $$

自此可以看出来时间复杂度从O(n)->O(n/3)。 rust代码如下

fn solve1() -> u64 {
    let mut a = 2;
    let mut b = 8;
    let mut sum = 0;

    while a <= 4_000_000 {
        sum += a;
        let next = 4 * b + a;
        a = b;
        b = next;
    }
    sum
}

计算时间上面呢也就减少了20ns，但是这样的降低时间复杂度的操作还是很有意义的。从中我们也可以得到启发，当程序无法进行优化时，可以从数学的角度入手。下面是运行时间对比图片(我把测试增加了)。

p004

题目

Problem 4: Largest Palindrome Product

题目链接题目描述:

A palindromic number reads the same both ways. The largest palindrome made from the product of two $2$-digit numbers is $9009 = 91 \times 99$.

问题:

Find the largest palindrome made from the product of two $3$-digit numbers.

解答a

同样，这题可以直接设定i和j代表两个数。直接开始循环，然后通过一个函数判断乘积是否是回文数。代码如下：

fn is_palindrome(n: u64) -> bool {
    let s = n.to_string();
    s.chars().eq(s.chars().rev())
}
fn baolisolve() -> u64 {
    let mut max_palindrome = 0;
    for i in 100..999 {
        for j in 100..999 {
            let x = i * j;
            if is_palindrome(x) && x >= max_palindrome {
                max_palindrome = x;
            }
        }
    }
    max_palindrome
}

最后得到的计算时间也是相当可观了（计算时间很长）

解答b

此时可以观察到，要求出最大的回文数，往往两个数字都需要大概900多的样子，我们可以直接从后向前循环，这样的话时间就能减少很多。

解答c

首先引入一个结论，任何一个偶数位数的回文数都可以被11整除。在本题目中，要求最大的六位回文数，则该回文数必然有一个因数也可以被11整除。于是便可以减少部分循环次数，进一步降低时间消耗。代码如下

fn mathsolve() -> u64 {
    let mut max_palindrome = 0;
    for i in (100..999).rev() {
        let start = if i % 11 == 0 { 999 } else { 990 };
        let step = if i % 11 == 0 { 1 } else { 11 };
        let mut j = start;
        while j >= 100 {
            let n = i * j;
            if n <= max_palindrome {
                break;
            }
            if is_palindrome(n) {
                max_palindrome = n;
            }
            j -= step;
        }
    }
    max_palindrome
}

最后可以看到消耗时间被降低到了微秒级别

简单证明一下上面这个结论。设一个 6 位回文数写成：

[ N = \overline{abccba} ]

其中 (a,b,c) 都是数字，且 (a \neq 0)。

把它按十进制展开：

[ N = 100000a + 10000b + 1000c + 100c + 10b + a ]

整理同类项可得：

[ N = 100001a + 10010b + 1100c ]

接下来把每一项提取出 11：

[ 100001 = 11 \times 9091 ]

[ 10010 = 11 \times 910 ]

[ 1100 = 11 \times 100 ]

所以：

[ N = 11(9091a + 910b + 100c) ]

因此，(N) 一定能被 11 整除。

任意 6 位回文数都可以写成 11 的倍数，因此：

[ \boxed{\text{任意 6 位回文数一定能被 11 整除}} ] 数学博大精深～～！

p005

题目

Problem 5: Smallest Multiple

题目链接

题目描述:

$2520$ is the smallest number that can be divided by each of the numbers from $1$ to $10$ without any remainder.

问题:

What is the smallest positive number that is evenly divisibledivisible with no remainder by all of the numbers from $1$ to $20$?

解答

这题需要求出1-20所有数字的lcm(最小公倍数)。

$$ lcm(a,b) = \frac{a * b}{gcd(a , b)} $$

代码如下

fn gcd(mut a: u64, mut b: u64) -> u64 {
    while b != 0 {
        let temp = b;
        b = a % b;
        a = temp;
    }
    a
}

fn lcm(a: u64, b: u64) -> u64 {
    a / gcd(a, b) * b
}

fn solve() -> u64 {
    (1..20).reduce(|acc, c| lcm(acc, c)).unwrap()
}