用欧拉计划学Rust编程语言（第700题：Eulercoin）

问题描述：
欧拉诞生于1707年4月15日，对于序列(1504170715041707 * n) mod 4503599627370517，如果一个元素小于前面发现的所有Eulercoin，则其称为Eulercoin。

例如，第一个元素是1504170715041707，为第一个Eulercoin，第二个元素为3008341430083414，由于它大于1504170715041707，所以不是Eulercoin。然而，第三个元素为8912517754604，比前面的数都小，被称为Eulercoin。前两个Eulercoins之和是1513083232796311。

求所有Eulercoin之和。

解题过程：

第一步，先根据题意暴力求解

这个代码非常容易写出来。

const INC: u64 = 1504170715041707_u64;
const MOD: u64 = 4503599627370517_u64;

let mut x = 0_u64;
let mut min = INC;
for n in 1_u64.. {
    x = (x + INC) % MOD;
    if x <= min {
        min = x;
        println!("{:20} {:20}", n, x);
    }
}

运行这个程序，可以输出如下结果。

1504170715041707
       8912517754604
       2044785486369
       1311409677241
        578033868113
        422691927098
        267349986083
        112008045068
         68674149121
         25340253174
          7346610401
          4046188430
           745766459
           428410324
           111054189
            15806432
            15397267
            14988102
            14578937
            14169772
            13760607
            13351442
            12942277
            12533112
            12123947
            11714782
            11305617
            10896452
            10487287
            10078122
             9668957
             9259792
             8850627
             8441462
             8032297
             7623132
             7213967
             6804802
             6395637
             5986472
             5577307
             5168142
             4758977
             4349812
             3940647
             3531482
             3122317
             2713152
             2303987
             1894822
             1485657
             1076492
              667327
              258162
             … … … …              … … … …

越往后，想找到一个Eulercoin愈发困难，必须得改进算法。

第二步，找规律

在n=2527之后，后一个eulercoin与前一个eulercoin有着递推的关系，补上一些数字之后，就能发现更为明显的关系。比如，n=2021, 6569, 30824, 116727…时，得到的数虽然不是eulercoin，但数值非常大，与4503599627370517越来越接近。

根据发现的规律，需要保存好最小的数和最大的数，不用一个数一个数的计算，效率非常高，不到1秒计算完成。

let mut sum = 1504170715041707_u64 + 8912517754604_u64 + 2044785486369_u64 + 1311409677241_u64;
let mut n_max = 2021_u64;
let mut max = 4502866251561389_u64;
let mut n = 2527_u64;
let mut x = 1311409677241_u64;
let mut min = x;

while min > 0 {
    let temp_n = n + n_max;
    let temp_x = (x + max) % 4503599627370517_u64;
    if temp_x <= min {
        n = temp_n;
        x = temp_x;
        min = x;
        sum += x;
        println!("{:20} {:12} {:20}", n, x, sum);
    }
    if temp_x > max {
        n_max = temp_n;
        max = temp_x;
        //println!("max: {} {} ", n_max, max);
    }
}

?

再优化

看了欧拉论坛中的优秀贴子，发现n的索引值并不需要记录，代码还可以更优美一些。

let inc = 1504170715041707_u64;
let modular = 4503599627370517_u64;
let mut low = inc;
let mut high = inc;
let mut sum = inc;
while low > 0 {
    let next = (low + high) % modular;
    if next < low {
        low = next;
        sum += low;
        println!("{:20} {:20}", low, sum);
    } else {
        high = next;
    }
}
println!("{}", sum);